fork download 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2025-04-11 18:09:51
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2025-04-11 18:53:43
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  16. // #define int long long
  17. #define ll long long 
  18. #define ull unsigned long long
  19. #define sz(x) x.size()
  20. #define sqr(x) (1LL * (x) * (x))
  21. #define all(x) x.begin(), x.end()
  22. #define fill(f,x) memset(f,x,sizeof(f))
  23. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  24. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  25. #define debug(x) cout << #x << " = " << x << '\n'
  26. #define ii pair<int,int>
  27. #define iii pair<int,ii>
  28. #define di pair<ii,ii>
  29. #define vi vector<int>
  30. #define vii vector<ii>
  31. #define mii map<int,int>
  32. #define fi first
  33. #define se second
  34. #define pb push_back
  35. #define MOD 1000000007
  36. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  37. #define YES cout << "YES\n"
  38. #define NO cout << "NO\n"
  39. #define MASK(i) (1LL << (i))
  40. #define c_bit(i) __builtin_popcountll(i)
  41. #define BIT(x,i) ((x) & MASK(i))
  42. #define SET_ON(x,i) ((x) | MASK(i))
  43. #define SET_OFF(x,i) ((x) & ~MASK(i))
  44. #define oo 1e18
  45. #define name ""
  46. #define endl '\n'
  47. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms.";
  48. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  49. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  50. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  51. const int N = (int)5e5+10;
  52. int q;
  53.  
  54. struct Query {
  55. 	char type;
  56. 	int u;
  57. } query[N];
  58.  
  59. namespace hungeazy {
  60.  
  61. 	int n = 1,sz[N],par[N],h[N];
  62. 	int head[N],id[N],pos[N],arr[N],cur=1,curPos=1;
  63. 	vi g[N];
  64. 	bool check[N];
  65.  
  66. 	void DFS(int u)
  67. 	{
  68. 		sz[u] = 1;
  69. 		for (int v : g[u])
  70. 		{
  71. 			h[v] = h[u]+1;
  72. 			par[v] = u;
  73. 			DFS(v);
  74. 			sz[u] += sz[v];
  75. 		}
  76. 	}
  77.  
  78. 	void HLD(int u)
  79. 	{
  80. 		if (!head[cur]) head[cur] = u;
  81. 		id[u] = cur;
  82. 		pos[u] = curPos;
  83. 		arr[curPos++] = u;
  84. 		int nxt = 0;
  85. 		for (int v : g[u])
  86. 			if (sz[v] > sz[nxt]) nxt = v;
  87. 		if (nxt) HLD(nxt);
  88. 		for (int v : g[u])
  89. 			if (v != nxt) cur++, HLD(v);
  90. 	}
  91.  
  92. 	int LCA(int x, int y)
  93. 	{
  94. 		while (id[x] != id[y])
  95. 		{
  96. 			if (id[x] < id[y]) y = par[head[id[y]]];
  97. 			else x = par[head[id[x]]];
  98. 		}
  99. 		if (h[x] > h[y]) swap(x,y);
  100. 		return x;
  101. 	}
  102.  
  103. 	struct SegmentTreeSum {
  104. 		int st[N<<2],lazy[N<<2];
  105.  
  106. 		void down(int id, int l, int r)
  107. 		{
  108. 			if (!lazy[id]) return;
  109. 			int mid = (l+r)>>1, &k = lazy[id];
  110. 			st[id<<1] += (mid-l+1)*k;
  111. 			st[id<<1|1] += (r-mid)*k;
  112. 			lazy[id<<1] += k;
  113. 			lazy[id<<1|1] += k;
  114. 			k = 0;
  115. 		}
  116.  
  117. 		void update(int id, int l, int r, int u, int v, int val)
  118. 		{
  119. 			if (l > v or r < u) return;
  120. 			if (l >= u and r <= v) 
  121. 			{
  122. 				st[id] += (r-l+1)*val;
  123. 				lazy[id] += val;
  124. 				return;
  125. 			}
  126. 			int mid = (l+r)>>1; down(id,l,r);
  127. 			update(id<<1,l,mid,u,v,val);
  128. 			update(id<<1|1,mid+1,r,u,v,val);
  129. 			st[id] = st[id<<1]+st[id<<1|1];
  130. 		}
  131.  
  132. 		int get(int id, int l, int r, int u, int v)
  133. 		{
  134. 			if (l > v or r < u) return 0;
  135. 			if (l >= u and r <= v) return st[id];
  136. 			int mid = (l+r)>>1; down(id,l,r);
  137. 			return get(id<<1,l,mid,u,v)+get(id<<1|1,mid+1,r,u,v);
  138. 		}
  139. 	} IT_Sum;
  140.  
  141. 	struct SegmentTreeCut {
  142. 		int st[N<<2],lazy[N<<2];
  143.  
  144. 		void down(int id)
  145. 		{
  146. 			if (!lazy[id]) return;
  147. 			int &k = lazy[id];
  148. 			st[id<<1] = st[id<<1|1] = k;
  149. 			lazy[id<<1] = lazy[id<<1|1] = k;
  150. 			k = 0;
  151. 		}
  152.  
  153. 		void update(int id, int l, int r, int u, int v, int val)
  154. 		{
  155. 			if (l > v or r < u) return;
  156. 			if (l >= u and r <= v) 
  157. 			{
  158. 				st[id] = val;
  159. 				lazy[id] = val;
  160. 				return;
  161. 			}
  162. 			int mid = (l+r)>>1; down(id);
  163. 			update(id<<1,l,mid,u,v,val);
  164. 			update(id<<1|1,mid+1,r,u,v,val);
  165. 			st[id] = max(st[id<<1],st[id<<1|1]);
  166. 		}
  167.  
  168. 		int find(int id, int l, int r, int u, int v)
  169. 		{
  170. 			if (l > v or r < u or st[id] <= 0) return -1;
  171. 			if (l == r) return l;
  172. 			int mid = (l+r)>>1; down(id);
  173. 			int x = find(id<<1|1,mid+1,r,u,v);
  174. 			if (x == -1) return find(id<<1,l,mid,u,v);
  175. 			return x;
  176. 		}
  177. 	} IT_Cut;
  178.  
  179. 	void updatePath(int u)
  180. 	{
  181. 		bool ok = true;
  182. 		while (id[u] != id[1])
  183. 		{
  184. 			int far = IT_Cut.find(1,1,n,pos[head[id[u]]],pos[u]);
  185. 			if (far != -1)
  186. 			{
  187. 				ok = false;
  188. 				IT_Sum.update(1,1,n,far,pos[u],1);
  189. 				break;
  190. 			}
  191. 			IT_Sum.update(1,1,n,pos[head[id[u]]],pos[u],1);
  192. 			u = par[head[id[u]]];
  193. 		}
  194. 		if (ok and pos[u] >= pos[1])
  195. 		{
  196. 			int far = IT_Cut.find(1,1,n,pos[1],pos[u]);
  197. 			IT_Sum.update(1,1,n,far,pos[u],1);
  198. 		}
  199. 	}
  200.  
  201. 	void cutEdge(int u)
  202. 	{
  203. 		int val = IT_Sum.get(1,1,n,pos[u],pos[u]);
  204. 		int v = par[u];
  205. 		if (!v) return;
  206. 		bool ok = true;
  207. 		while (id[v] != id[1])
  208. 		{
  209. 			int far = IT_Cut.find(1,1,n,pos[head[id[v]]],pos[v]);
  210. 			if (far != -1)
  211. 			{
  212. 				ok = false;
  213. 				IT_Sum.update(1,1,n,far,pos[v],-val);
  214. 				break;
  215. 			}
  216. 			IT_Sum.update(1,1,n,pos[head[id[v]]],pos[v],-val);
  217. 			v = par[head[id[v]]];
  218. 		}
  219. 		if (ok and pos[v] >= pos[1])
  220. 		{
  221. 			int far = IT_Cut.find(1,1,n,pos[1],pos[v]);
  222. 			IT_Sum.update(1,1,n,far,pos[v],-val);
  223. 		}
  224. 		IT_Cut.update(1,1,n,pos[u],pos[u],1);
  225. 	}
  226.  
  227. 	void solve(void)
  228. 	{
  229. 		FOR(i,1,q)
  230. 			if (query[i].type == 'A')
  231. 				g[query[i].u].pb(++n);
  232. 		DFS(1);
  233. 		HLD(1);
  234. 		IT_Sum.update(1,1,n,pos[1],pos[1],1);
  235. 		int node = 1;
  236. 		FOR(i,1,q)
  237. 		{
  238. 			char type = query[i].type;
  239. 			int u = query[i].u;
  240. 			if (type == 'A')
  241. 			{
  242. 				updatePath(node+1);
  243. 				node++;
  244. 			}
  245. 			else if (type == 'C')
  246. 			{
  247. 				if (check[u]) continue;
  248. 				check[u] = true;
  249. 				cutEdge(u);
  250. 			}
  251. 			else cout << IT_Sum.get(1,1,n,pos[u],pos[u]) << endl;
  252. 		}
  253. 	}
  254.  
  255. }
  256.  
  257. signed main()
  258. {
  259.     fast;
  260.     if (fopen(name".inp","r"))
  261.     {
  262.     	freopen(name".inp","r",stdin);
  263.     	freopen(name".out","w",stdout);
  264.     }
  265.     cin >> q;
  266.     FOR(i,1,q) cin >> query[i].type >> query[i].u;
  267.     hungeazy::solve();
  268.     time();
  269.     return 0;
  270. }
  271. // ██░ ██  █    ██  ███▄    █   ▄████
  272. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  273. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  274. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  275. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  276. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  277. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  278. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  279. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 24412KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
-------------Time:9.06ms.
https://ideone.com/FSu4Yl
language:
C++14 (gcc 8.3)
created:
11 days 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!