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.  
  45. 	node(){}
  46. 	friend void downit(node* ,int rev,int add);
  47.  
  48. 	void down()
  49. 	{
  50. 		if(lc)downit(lc,rev,add);
  51. 		if(rc)downit(rc,rev,add);
  52. 		add=0;rev=0;
  53. 	}
  54.  
  55. 	void update()
  56. 	{
  57. 		size=1;
  58. 		ma=key;
  59. 		if(lc)
  60. 		{
  61. 			size+=lc->size;
  62. 			if(lc->ma<ma)
  63. 				ma=lc->ma;
  64. 		}
  65. 		if(rc)
  66. 		{
  67. 			size+=rc->size;
  68. 			if(rc->ma<ma)
  69. 				ma=rc->ma;
  70. 		}
  71. 	}
  72. }tree[MAX*NUM];
  73. int cnt;
  74.  
  75. node* mynew()
  76. {
  77. 	return tree+(cnt++);
  78. }
  79.  
  80. node* newnode(int _key,int _weight,node* _lc,node* _rc)
  81. {
  82. 	node* p=mynew();
  83. 	p->key=p->ma=_key;
  84. 	p->weight=_weight;
  85. 	p->lc=_lc;
  86. 	p->rc=_rc;
  87. 	p->rev=0;
  88. 	p->add=0;
  89. 	p->size=1;
  90. 	return p;
  91. }
  92.  
  93. void down(node* u)
  94. {
  95. 	if(!u)return;
  96. 	u->down();
  97. }
  98.  
  99. void downit(node* np,int rev,int add)
  100. {
  101. 	if(!np)return;
  102. 	if(rev)
  103. 	{
  104. 		swap(np->lc,np->rc);
  105. 		np->rev^=rev;
  106. 	}
  107. 	if(add)
  108. 	{
  109. 		np->key+=add;
  110. 		np->add+=add;
  111. 		np->ma+=add;
  112. 	}
  113. }
  114.  
  115. node* merge(node* a,node* b)
  116. {
  117. 	if(!b)return a;
  118. 	if(!a)return b;
  119. 	down(a);
  120. 	down(b);
  121. 	if( a->weight > b->weight )
  122. 	{
  123. 		a->rc=merge(a->rc,b);
  124. 		a->update();
  125. 		return a;
  126. 	}
  127. 	else
  128. 	{
  129. 		b->lc=merge(a,b->lc);
  130. 		b->update();
  131. 		return b;
  132. 	}
  133. }
  134.  
  135. pair<node*,node*> spilt_l(node* a,int left)
  136. {
  137. 	if(!a)
  138. 		return mp((node*)0,(node*)0);
  139. 	down(a);
  140. 	int size_l=(a->lc?a->lc->size:0)+1;
  141. 	pair<node* ,node* > tmp;
  142. 	if(size_l<=left)
  143. 	{
  144. 		tmp=spilt_l(a->rc,left-size_l);
  145. 		a->rc=tmp.x;
  146. 		a->update();
  147. 		return mp(a,tmp.y);
  148. 	}
  149. 	else
  150. 	{
  151. 		tmp=spilt_l(a->lc,left);
  152. 		a->lc=tmp.y;
  153. 		a->update();
  154. 		return mp(tmp.x,a);
  155. 	}
  156. }
  157.  
  158. node* insert(node* a,int left,node* p)
  159. {
  160. 	if(!a)return p;
  161. 	down(a);
  162. 	int size_l=(a->lc?a->lc->size:0)+1;
  163. 	if(p->weight<a->weight)
  164. 	{ 
  165. 		if(size_l<=left)
  166. 		{
  167. 			a->rc=insert(a->rc,left-size_l,p);
  168. 			a->update();
  169. 		}
  170. 		else 
  171. 		{
  172. 			a->lc=insert(a->lc,left,p);
  173. 			a->update();
  174. 		}
  175. 		return a;
  176. 	}
  177. 	else
  178. 	{
  179. 		pair<node* ,node* > tmp=spilt_l(a,left);
  180. 		p->lc=tmp.x;
  181. 		p->rc=tmp.y;
  182. 		p->update();
  183. 		return p;
  184. 	}
  185. }
  186.  
  187. int n,m;
  188. int a[MAX];
  189. node* root;
  190.  
  191. void doit(node*& ll,node*& mid,node*& rr,int a,int b)
  192. {
  193. 	pair<node*,node*> tmp;
  194. 	tmp=spilt_l(root,a-1);
  195. 	ll=tmp.x;
  196. 	tmp=spilt_l(tmp.y,b-a+1);
  197. 	mid=tmp.x;
  198. 	rr=tmp.y;
  199. }
  200.  
  201. int main()
  202. {
  203. #ifndef ONLINE_JUDGE
  204. 	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  205. #endif
  206. 	int i;
  207. 	scanf("%d",&n);
  208. 	REP(i,1,n)
  209. 	{
  210. 		scanf("%d",&a[i]);
  211. 		root=insert(root,i-1,newnode(a[i],ran(),0,0));
  212. 	}
  213. 	scanf("%d",&m);
  214. 	REP(i,1,m)
  215. 	{
  216. 		char Q[100];
  217. 		scanf("%s",Q);
  218. 		int a,b,c;
  219. 		node* ll(0),*rr(0),*mid(0);
  220. 		if(Q[0]=='A')
  221. 		{
  222. 			scanf("%d%d%d",&a,&b,&c);
  223. 			doit(ll,mid,rr,a,b);
  224. 			downit(mid,0,c);
  225. 			root=merge( merge(ll,mid) , rr );
  226. 		}
  227. 		else if(Q[0]=='R' && Q[3]=='E')
  228. 		{
  229. 			scanf("%d%d",&a,&b);
  230. 			doit(ll,mid,rr,a,b);
  231. 			downit(mid,1,0);
  232. 			root=merge( merge(ll,mid) , rr );
  233. 		}
  234. 		else if(Q[0]=='R' && Q[3]=='O')
  235. 		{
  236. 			scanf("%d%d%d",&a,&b,&c);
  237. 			c=c%(b-a+1);
  238. 			if(!c)continue;
  239. 			doit(ll,mid,rr,a,b);
  240. 			pair<node*,node*> tmp=spilt_l(mid,mid->size-c);
  241. 			root=merge( merge(ll,merge(tmp.y,tmp.x)) , rr );
  242. 		}
  243. 		else if(Q[0]=='I')
  244. 		{
  245. 			scanf("%d%d",&a,&b);
  246. 			root=insert(root,a,newnode(b,ran(),0,0));
  247. 		}
  248. 		else if(Q[0]=='D')
  249. 		{
  250. 			scanf("%d",&a);
  251. 			pair<node*,node*> tmp=spilt_l(root,a-1);
  252. 			root=merge(tmp.x,spilt_l(tmp.y,1).y);
  253. 		}
  254. 		else if(Q[0]=='M')
  255. 		{
  256. 			scanf("%d%d",&a,&b);
  257. 			doit(ll,mid,rr,a,b);
  258. 			printf("%d\n",mid->ma);
  259. 			root=merge( merge(ll,mid) ,rr);
  260. 		}
  261. 	}
  262. 	return 0;
  263. }
  264.  
Success #stdin #stdout 0s 12624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9Cz07b
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!