fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=100000+10;
  27. const int NUM=3;
  28.  
  29. int ran()
  30. {
  31. 	static int seed=222313214;
  32. 	seed+=(seed<<2)+1;
  33. 	return seed;
  34. }
  35.  
  36. struct node
  37. {
  38. 	int key,weight;//weight值大的在上面
  39. 	node *lc,*rc;
  40. 	bool rev;
  41. 	int add;
  42. 	int size;//记录子树大小
  43. 	int ma;//记录子树中的最小值
  44. 	int cnt;//引用计数
  45.  
  46. 	node(){}
  47. 	friend node* downit(node* ,int rev,int add);
  48.  
  49. 	void down()
  50. 	{
  51. 		if(lc)lc=downit(lc,rev,add);
  52. 		if(rc)rc=downit(rc,rev,add);
  53. 		add=0;rev=0;
  54. 	}
  55.  
  56. 	void update()
  57. 	{
  58. 		size=1;
  59. 		ma=key;
  60. 		if(lc)
  61. 		{
  62. 			size+=lc->size;
  63. 			if(lc->ma<ma)
  64. 				ma=lc->ma;
  65. 		}
  66. 		if(rc)
  67. 		{
  68. 			size+=rc->size;
  69. 			if(rc->ma<ma)
  70. 				ma=rc->ma;
  71. 		}
  72. 	}
  73. }tree[MAX*NUM];
  74. int pool[MAX*NUM+100],top;
  75.  
  76. node* mynew()
  77. {
  78. 	return tree+pool[top--];
  79. }
  80.  
  81. void mydelete(node* p)
  82. {
  83. 	pool[++top]=p-tree;
  84. }
  85.  
  86. node* newnode(int _key,int _weight,node* _lc,node* _rc)
  87. {
  88. 	node* p=mynew();
  89. 	p->key=p->ma=_key;
  90. 	p->weight=_weight;
  91. 	p->lc=_lc;
  92. 	p->rc=_rc;
  93. 	p->rev=0;
  94. 	p->add=p->cnt=0;
  95. 	p->size=1;
  96. 	if(p->lc)++p->lc->cnt;
  97. 	if(p->rc)++p->rc->cnt;
  98. 	return p;
  99. }
  100.  
  101. node* newnode(node* c)
  102. {
  103. 	node* p=mynew();
  104. 	*p=*c;
  105. 	p->cnt=0;
  106. 	if(p->lc)++p->lc->cnt;
  107. 	if(p->rc)++p->rc->cnt;
  108. 	return p;
  109. }
  110.  
  111. void delthem(node* u)
  112. {
  113. 	if(!u)
  114. 		return;
  115. 	--u->cnt;
  116. 	if(u->cnt==0)
  117. 	{
  118. 		delthem(u->lc);
  119. 		delthem(u->rc);
  120. 		mydelete(u);
  121. 	}
  122. }
  123.  
  124. void relax(node* u)
  125. {
  126. 	if(!u || u->cnt>0)
  127. 		return;
  128. 	delthem(u->lc);
  129. 	delthem(u->rc);
  130. 	mydelete(u);
  131. }
  132.  
  133. node* down(node* u)
  134. {
  135. 	if(!u)return u;
  136. 	node* p=newnode(u);
  137. 	if(!p->add && !p->rev)
  138. 		return p;
  139. 	p->down();
  140. 	return p;
  141. }
  142.  
  143. node* downit(node* p,int rev,int add)
  144. {
  145. 	if(!p)return 0;
  146. 	node* np=newnode(p);
  147. 	if(rev)
  148. 	{
  149. 		swap(np->lc,np->rc);
  150. 		np->rev^=rev;
  151. 	}
  152. 	if(add)
  153. 	{
  154. 		np->key+=add;
  155. 		np->add+=add;
  156. 		np->ma+=add;
  157. 	}
  158. 	--p->cnt;
  159. 	relax(p);
  160. 	++np->cnt;
  161. 	return np;
  162. }
  163.  
  164. node* merge(node* a,node* b)
  165. {
  166. 	if(!b)return newnode(a);
  167. 	if(!a)return newnode(b);
  168. 	a=down(a);
  169. 	b=down(b);
  170. 	node* np;
  171. 	if( a->weight > b->weight )
  172. 		np=newnode( a->key,a->weight,a->lc,merge(a->rc,b) );
  173. 	else
  174. 		np=newnode( b->key,b->weight,merge(a,b->lc),b->rc );
  175. 	np->update();
  176. 	relax(a);
  177. 	relax(b);
  178. 	return np;
  179. }
  180.  
  181. node* spilt_l(node* a,int left)
  182. {
  183. 	if(!a || left==0)
  184. 		return 0;
  185. 	a=down(a);
  186. 	int size_l=(a->lc?a->lc->size:0)+1;
  187. 	node* np;
  188. 	if(size_l<=left)
  189. 	{
  190. 		np=newnode(a->key,a->weight,a->lc,spilt_l(a->rc,left-size_l));
  191. 		np->update();
  192. 	}
  193. 	else np=spilt_l(a->lc,left);
  194. 	relax(a);
  195. 	return np;
  196. }
  197.  
  198. node* spilt_r(node* a,int right)
  199. {
  200. 	if(!a || right==0)
  201. 		return 0;
  202. 	a=down(a);
  203. 	int size_r=(a->rc?a->rc->size:0)+1;
  204. 	node* np;
  205. 	if(size_r<=right)
  206. 	{
  207. 		np=newnode(a->key,a->weight,spilt_r(a->lc,right-size_r),a->rc);
  208. 		np->update();
  209. 	}
  210. 	else np=spilt_r(a->rc,right);
  211. 	relax(a);
  212. 	return np;
  213. }
  214.  
  215. node* insert(node* a,int left,node* p)
  216. {
  217. 	if(!a)return p;
  218. 	a=down(a);
  219. 	int size_l=(a->lc?a->lc->size:0)+1; node* np;
  220. 	if(p->weight<a->weight)
  221. 	{ 
  222. 		if(size_l<=left) np=newnode( a->key , a->weight , a->lc,insert(a->rc,left-size_l,p) );
  223. 		else np=newnode( a->key , a->weight , insert(a->lc,left,p) ,a->rc );
  224. 	}
  225. 	else
  226. 		np=newnode(p->key,p->weight,spilt_l(a,left),spilt_r(a,a->size-left));
  227. 	np->update();
  228. 	relax(a);
  229. 	return np;
  230. }
  231.  
  232. node* get_tree(node* Root,int a,int b)
  233. {
  234. 	node* tmp=spilt_l(Root,b);
  235. 	node* p=spilt_r(tmp,b-a+1);
  236. 	relax(tmp);
  237. 	return p;
  238. }
  239.  
  240. int n,m;
  241. int a[MAX];
  242. node* root;
  243.  
  244. void doit(node*& ll,node*& mid,node*& rr,int a,int b)
  245. {
  246. 	ll=spilt_l(root,a-1);
  247. 	rr=spilt_r(root,root->size-b);
  248. 	mid=get_tree(root,a,b);
  249. }
  250.  
  251. int main()
  252. {
  253. #ifndef ONLINE_JUDGE
  254. 	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  255. #endif
  256. 	int i;
  257. 	REP2(i,0,MAX*NUM-10)
  258. 		pool[++top]=i;
  259. 	scanf("%d",&n);
  260. 	REP(i,1,n)
  261. 	{
  262. 		scanf("%d",&a[i]);
  263. 		node* tmp=root;
  264. 		root=insert(root,i-1,newnode(a[i],ran(),0,0));
  265. 		relax(tmp);
  266. 	}
  267. 	scanf("%d",&m);
  268. 	REP(i,1,m)
  269. 	{
  270. 		char Q[100];
  271. 		scanf("%s",Q);
  272. 		int a,b,c;
  273. 		node* ll(0),*rr(0),*mid(0),*tmp;
  274. 		if(Q[0]=='A')
  275. 		{
  276. 			scanf("%d%d%d",&a,&b,&c);
  277. 			doit(ll,mid,rr,a,b);
  278. 			mid=downit(mid,0,c);--mid->cnt;
  279. 			relax(root);
  280. 			root=merge( tmp=merge(ll,mid) , rr );
  281. 			relax(ll);relax(mid);relax(rr);
  282. 			relax(tmp);
  283. 		}
  284. 		else if(Q[0]=='R' && Q[3]=='E')
  285. 		{
  286. 			scanf("%d%d",&a,&b);
  287. 			doit(ll,mid,rr,a,b);
  288. 			mid=downit(mid,1,0);--mid->cnt;
  289. 			relax(root);
  290. 			root=merge( tmp=merge(ll,mid) , rr );
  291. 			relax(ll);relax(mid);relax(rr);
  292. 			relax(tmp);
  293. 		}
  294. 		else if(Q[0]=='R' && Q[3]=='O')
  295. 		{
  296. 			scanf("%d%d%d",&a,&b,&c);
  297. 			c=c%(b-a+1);
  298. 			if(!c)continue;
  299. 			doit(ll,mid,rr,a,b);
  300. 			node* e=spilt_r(mid,c);
  301. 			node* f=spilt_l(mid,mid->size-c);
  302. 			relax(root);
  303. 			node* tmp2;
  304. 			root=merge( tmp=merge(ll,tmp2=merge(e,f)) , rr );
  305. 			relax(ll);relax(mid);relax(rr);
  306. 			relax(e);relax(f);
  307. 			relax(tmp);relax(tmp2);
  308. 		}
  309. 		else if(Q[0]=='I')
  310. 		{
  311. 			scanf("%d%d",&a,&b);
  312. 			tmp=root;
  313. 			root=insert(root,a,newnode(b,ran(),0,0));
  314. 			relax(tmp);
  315. 		}
  316. 		else if(Q[0]=='D')
  317. 		{
  318. 			scanf("%d",&a);
  319. 			ll=spilt_l(root,a-1);
  320. 			rr=spilt_r(root,root->size-a);
  321. 			relax(root);
  322. 			root=merge(ll,rr);
  323. 			relax(ll);relax(rr);
  324. 		}
  325. 		else if(Q[0]=='M')
  326. 		{
  327. 			scanf("%d%d",&a,&b);
  328. 			node* p=get_tree(root,a,b);
  329. 			printf("%d\n",p->ma);
  330. 			relax(p);
  331. 		}
  332. 	}
  333. 	return 0;
  334. }
  335.  
Success #stdin #stdout 0s 15008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kbSjPp
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!