fork download
copy 
  1. /*
  2. ・ビット列について
  3. 　ビット列は、一番左から0がいくつ連続するか、一番右から0がいくつ連続するか、ビット列の長さ、現在のビット列内に含まれる連続する0の長さの最大値の4つを持っておければ、結合も含めて管理できる。
  4. (ただし、32bit整数型に収まらない場合に注意せよ。)
  5. 　各タイプについて、セグメント木を用いれば求まる。
  6.  
  7. ・答えについて
  8. 　Undoするクエリがない場合、普通のUnionFindと同じである。
  9. 　ただしUndoするクエリがあるので、永続化する必要がある。
  10. 　セグメント木に各要素を持たせて永続unionfind木を実装すると、満点が得られる。
  11. */
  12.  
  13. //以下自分のコード
  14. //このくらいのメモリ使用は許容したいなあという感じで書いたので、もっとメモリ制限きつくても解けます
  15.  
  16.  
  17. #include <cstdio>
  18. #include <vector>
  19. #include <cstring>
  20. #include <functional>
  21. #include <algorithm>
  22. #include <math.h>
  23. #include <bitset>
  24. #include <set>
  25. #include <queue>
  26. #include <assert.h>
  27. #include <iostream>
  28. #include <string>
  29. #include <sstream>
  30. #include <stack>
  31. #include <complex>
  32. #include <numeric>
  33. #include <map>
  34. #include <time.h>
  35. using namespace std;
  36. typedef long double ld;
  37. typedef long long ll;
  38. typedef unsigned long long ull;
  39. typedef unsigned int uint;
  40. typedef pair<int,int> pii;
  41. typedef pair<int,ll> pil;
  42. typedef pair<int,ull> piu;
  43. typedef pair<ll,int> pli;
  44. typedef pair<ll,ll> pll;
  45. typedef pair<pii,ll> ppl;
  46. typedef pair<ll,pii> plp;
  47. typedef pair<ll,pll> plP;
  48. typedef pair<int,pii> pip;
  49. typedef pair<pii,int> ppi;
  50. typedef pair<pii,pii> ppp;
  51. typedef pair<double,int> pdi;
  52. typedef pair<int,double> pid;
  53. typedef pair<double,pii> pdp;
  54. typedef pair<double,double> pdd;
  55. typedef pair<pdd,double> pd3;
  56. typedef vector<int> vec;
  57. typedef vector<vec> mat;
  58. #define rep(i,n) for (int (i) = 0; (i) < (n); (i)++)
  59. #define repn(i,a,n) for (int (i) = (a); (i) < (n); (i)++)
  60. #define ALL(x) (x).begin(),(x).end()
  61. #define pb push_back
  62. #define SORT(x) sort((x).begin(),(x).end())
  63. #define SORTN(x,n) sort((x),(x)+(n))
  64. #define ERASE(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
  65. #define COUNT(x,c) count((x).begin(),(x).end(),(c))
  66. #define REMOVE(x,c) (x).erase(remove((x).begin(),(x).end(),(c)),(x).end())
  67. #define REVERSE(x) reverse((x).begin(),(x).end())
  68. #define FORIT(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
  69. #define LB(x,a) lower_bound((x).begin(),(x).end(),(a))-(x).begin()
  70. #define lb(x,a) lower_bound((x).begin(),(x).end(),(a))
  71. #define LBN(x,a,n) lower_bound((x),(x)+(n),(a))-(x)
  72. #define lbN(x,a,n) lower_bound((x),(x)+(n),(a))
  73. #define UB(x,a) upper_bound((x).begin(),(x).end(),(a))-(x).begin()
  74. #define ub(x,a) upper_bound((x).begin(),(x).end(),(a))
  75. #define BS(x,a) binary_search((x).begin(),(x).end(),(a))
  76. #define BS2(x,n,a) binary_search((x),(x)+(n),(a))
  77. #define NB(x) (((x)&~((x)+((x)&-(x))))/((x)&-(x))>>1)|((x)+((x)&-(x)))
  78. #define NP(x) next_permutation((x).begin(),(x).end())
  79. #define MM(x,p) memset((x),(p),sizeof(x))
  80. #define SQ(x) (x)*(x)
  81. #define SC(c1,c2) strcmp(c1,c2)==0
  82. #define mp make_pair
  83. #define INF (1<<28)
  84. #define INFL (1LL<<61)
  85. #define fi first
  86. #define se second
  87. #define MOD 1000000007
  88. #define EPS 1e-9
  89. #define MIN(x,a) x=min(x,a)
  90. #define MAX(x,a) x=max(x,a)
  91. #define madd(x,a) x=(x+a)%MOD
  92. #define msub(x,a) x=(x+MOD-a)%MOD
  93. #define OUTPUT(x) rep(__,x.size())printf("%d%c",x[__],__+1==x.size()?'\n':' ');
  94.  
  95. int T,Q,L,R;
  96. const int n=1<<17;
  97. char S[n];
  98. struct Query
  99. {
  100. 	ll lq,rq,sz,q;
  101. };
  102. Query merge(Query p1,Query p2)
  103. {
  104. 	Query res;
  105. 	if(p1.lq==-1)res=p2;
  106. 	else if(p2.lq==-1)res=p1;
  107. 	else
  108. 	{
  109. 		if(p1.lq==p1.sz)res.lq=p1.sz+p2.lq;
  110. 		else res.lq=p1.lq;
  111. 		if(p2.rq==p2.sz)res.rq=p1.rq+p2.sz;
  112. 		else res.rq=p2.rq;
  113. 		res.sz=p1.sz+p2.sz;
  114. 		res.q=max(p1.q,p2.q);
  115. 		MAX(res.q,p1.rq+p2.lq);
  116. 		MAX(res.q,res.lq);
  117. 		MAX(res.q,res.rq);
  118. 	}
  119. 	return res;
  120. }
  121. struct Node
  122. {
  123. 	int l,r,par,ra;
  124. 	Query q;
  125. 	Node(){par=-1,ra=0,l=r=-1;}
  126. }nd[5000000];
  127. int pos[5000000];
  128. int ndptr=n+n-1;
  129.  
  130. struct SegTree
  131. {
  132. 	SegTree()
  133. 	{
  134. 		rep(i,n-1)nd[i].l=i*2+1,nd[i].r=i*2+2;
  135. 	}
  136. 	int gt(int a,int b,int k,int l,int r)
  137. 	{
  138. 		if(r<=a||b<=l)return -1;
  139. 		if(a<=l&&r<=b)return k;
  140. 		return max(gt(a,b,nd[k].l,l,(l+r)/2),gt(a,b,nd[k].r,(l+r)/2,r));
  141. 	}
  142. 	int update(int a,int b,int k,int l,int r,Node sss)
  143. 	{
  144. 		if(r<=a||b<=l)return k;
  145. 		if(a<=l&&r<=b)
  146. 		{
  147. 			pos[ndptr]=l;
  148. 			nd[ndptr++]=sss;
  149. 			return ndptr-1;
  150. 		}
  151. 		int x=ndptr++;
  152. 		nd[x].l=update(a,b,nd[k].l,l,(l+r)/2,sss);
  153. 		nd[x].r=update(a,b,nd[k].r,(l+r)/2,r,sss);
  154. 		return x;
  155. 	}
  156. }seg;
  157. struct SegDat
  158. {
  159. 	Query q[n*2-1];
  160. 	void init()
  161. 	{
  162. 		rep(i,n)
  163. 		{
  164. 			if(S[i]=='0')q[i+n-1].lq=q[i+n-1].rq=q[i+n-1].q=1;
  165. 			else q[i+n-1].lq=q[i+n-1].rq=q[i+n-1].q=0;
  166. 			q[i+n-1].sz=1;
  167. 		}
  168. 		for(int i=n-2;i>=0;i--)q[i]=merge(q[i*2+1],q[i*2+2]);
  169. 	}
  170. 	Query query(int a,int b,int k,int l,int r)
  171. 	{
  172. 		if(r<=a||b<=l)
  173. 		{
  174. 			Query res;
  175. 			res.lq=-1;
  176. 			return res;
  177. 		}
  178. 		if(a<=l&&r<=b)return q[k];
  179. 		return merge(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
  180. 	}
  181. }ss;
  182. int root[1000001];
  183. int t,a,b;
  184.  
  185. int main()
  186. {
  187. 	scanf("%d",&T);
  188. 	scanf("%s",&S);
  189. 	ss.init();
  190. 	rep(i,T)
  191. 	{
  192. 		scanf("%d%d",&L,&R);L--;
  193. 		nd[i+n-1].q=ss.query(L,R,0,0,n);
  194. 		nd[i+n-1].par=i;
  195. 		nd[i+n-1].ra=1;
  196. 		pos[i+n-1]=i;
  197. 	}
  198. 	scanf("%d",&Q);
  199. 	repn(i,1,Q+1)
  200. 	{
  201. 		scanf("%d",&t);
  202. 		if(t==0)
  203. 		{
  204. 			scanf("%d",&a);a--;
  205. 			root[i]=root[i-1];
  206. 			int p1=seg.gt(a,a+1,root[i],0,n);
  207. 			if(nd[p1].par!=pos[p1])
  208. 			{
  209. 				vector<int> lis;
  210. 				lis.pb(p1);
  211. 				while(nd[lis.back()].par!=pos[lis.back()])
  212. 				{
  213. 					int tt=lis.back();
  214. 					lis.pb(seg.gt(nd[tt].par,nd[tt].par+1,root[i],0,n));
  215. 				}
  216. 				rep(j,lis.size()-2)
  217. 				{
  218. 					Node tmp=nd[lis[j]];
  219. 					tmp.par=pos[lis.back()];
  220. 					root[i]=seg.update(pos[lis[j]],pos[lis[j]]+1,root[i],0,n,tmp);
  221. 				}
  222. 				p1=lis.back();
  223. 			}
  224. 			printf("%lld\n",nd[p1].q.q);
  225. 		}
  226. 		else if(t==1)
  227. 		{
  228. 			scanf("%d",&a);
  229. 			root[i]=root[a];
  230. 		}
  231. 		else
  232. 		{
  233. 			scanf("%d%d",&a,&b);a--,b--;
  234. 			root[i]=root[i-1];
  235. 			int p1=seg.gt(a,a+1,root[i],0,n);
  236. 			if(nd[p1].par!=pos[p1])
  237. 			{
  238. 				vector<int> lis;
  239. 				lis.pb(p1);
  240. 				while(nd[lis.back()].par!=pos[lis.back()])
  241. 				{
  242. 					int tt=lis.back();
  243. 					lis.pb(seg.gt(nd[tt].par,nd[tt].par+1,root[i],0,n));
  244. 				}
  245. 				rep(j,lis.size()-2)
  246. 				{
  247. 					Node tmp=nd[lis[j]];
  248. 					tmp.par=pos[lis.back()];
  249. 					root[i]=seg.update(pos[lis[j]],pos[lis[j]]+1,root[i],0,n,tmp);
  250. 				}
  251. 				p1=lis.back();
  252. 			}
  253. 			int p2=seg.gt(b,b+1,root[i],0,n);
  254. 			if(nd[p2].par!=pos[p2])
  255. 			{
  256. 				vector<int> lis;
  257. 				lis.pb(p2);
  258. 				while(nd[lis.back()].par!=pos[lis.back()])
  259. 				{
  260. 					int tt=lis.back();
  261. 					lis.pb(seg.gt(nd[tt].par,nd[tt].par+1,root[i],0,n));
  262. 				}
  263. 				rep(j,lis.size()-2)
  264. 				{
  265. 					Node tmp=nd[lis[j]];
  266. 					tmp.par=pos[lis.back()];
  267. 					root[i]=seg.update(pos[lis[j]],pos[lis[j]]+1,root[i],0,n,tmp);
  268. 				}
  269. 				p2=lis.back();
  270. 			}
  271. 			if(p1==p2)continue;
  272. 			Query tt=merge(nd[p1].q,nd[p2].q);
  273. 			if(nd[p1].ra<nd[p2].ra)swap(p1,p2),swap(a,b);
  274. 			a=pos[p1],b=pos[p2];
  275. 			Node res=nd[p1];
  276. 			res.q=tt;
  277. 			if(nd[p1].ra==nd[p2].ra)res.ra++;
  278.  
  279. 			root[i]=seg.update(a,a+1,root[i],0,n,res);
  280.  
  281. 			Node nw=nd[p2];
  282. 			nw.par=a;
  283.  
  284. 			root[i]=seg.update(b,b+1,root[i],0,n,nw);
  285. 		}
  286. 	}
  287. }
Success #stdin #stdout 0.18s 269632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HQagcD
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!