fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. class bit{
  11. public:
  12. 	int n;
  13. 	ll* d;
  14.  
  15. 	void init(int nw){
  16. 		n = nw;
  17. 		d = new ll[n];
  18. 		for (int i = 0; i < n; i++) d[i] = 0;
  19. 	}
  20.  
  21. 	void add(int a, ll x){
  22. 		for (int i = a + 1; i <= n; i += (i & -i)) d[i - 1] += x;
  23. 	}
  24.  
  25. 	ll sum(int a){
  26. 		ll all = 0;
  27. 		for (int i = a + 1; i > 0; i -= (i & -i)) all += d[i - 1];
  28. 		return all;
  29. 	}
  30. };
  31.  
  32. class rmq{
  33. public:
  34. 	int n;
  35. 	ll* d;
  36.  
  37. 	void init(int nw){
  38. 		for (n = 1; n <= nw; n *= 2){}
  39. 		d = new ll[n * 2];
  40. 		for (int i = 0; i < n * 2; i++) d[i] = 0;
  41. 	}
  42.  
  43. 	void setw(int a, ll x, int nb, int ne, int p){
  44. 		if (a < nb || ne <= a) return;
  45. 		if (ne - nb == 1){
  46. 			d[p] = x;
  47. 			return;
  48. 		}
  49. 		setw(a, x, nb, (nb + ne) / 2, p * 2 + 1);
  50. 		setw(a, x, (nb + ne) / 2, ne, p * 2 + 2);
  51. 		d[p] = max(d[p * 2 + 1], d[p * 2 + 2]);
  52. 	}
  53.  
  54. 	void set(int a, ll x){
  55. 		setw(a, x, 0, n, 0);
  56. 	}
  57.  
  58. 	ll getw(int a, int nb, int ne, int p){
  59. 		if (a < nb || ne <= a) return d[p];
  60. 		if (ne - nb == 1) return -1;
  61. 		return max(getw(a, nb, (nb + ne) / 2, p * 2 + 1), getw(a, (nb + ne) / 2, ne, p * 2 + 2));
  62. 	}
  63.  
  64. 	ll get(int a){
  65. 		return getw(a, 0, n, 0);
  66. 	}
  67.  
  68. 	ll all(){
  69. 		return d[0];
  70. 	}
  71. };
  72.  
  73. class seg{
  74. public:
  75. 	class node{
  76. 	public:
  77. 		ll m;
  78. 		ll a;
  79. 	};
  80.  
  81. 	node nadd(node a, ll x){
  82. 		a.a += x;
  83. 		a.m += x;
  84. 		return a;
  85. 	}
  86.  
  87. 	node unit(node a, node b){
  88. 		node w;
  89. 		w.a = 0;
  90. 		w.m = max(a.m, b.m);
  91. 		return w;
  92. 	}
  93.  
  94. 	int n;
  95. 	node* d;
  96.  
  97. 	void init(int nw){
  98. 		for (n = 1; n <= nw; n *= 2){}
  99. 		d = new node[n * 2];
  100. 		for (int i = 0; i < n * 2; i++){
  101. 			d[i].a = 0;
  102. 			d[i].m = 0;
  103. 		}
  104. 	}
  105.  
  106. 	void addw(int a, ll x, int nb, int ne, int p){
  107. 		if (ne <= a) return;
  108. 		if (a <= nb){
  109. 			d[p] = nadd(d[p], x);
  110. 			return;
  111. 		}
  112. 		d[p * 2 + 1] = nadd(d[p * 2 + 1], d[p].a);
  113. 		d[p * 2 + 2] = nadd(d[p * 2 + 2], d[p].a);
  114. 		addw(a, x, nb, (nb + ne) / 2, p * 2 + 1);
  115. 		addw(a, x, (nb + ne) / 2, ne, p * 2 + 2);
  116. 		d[p] = unit(d[p * 2 + 1], d[p * 2 + 2]);
  117. 	}
  118.  
  119. 	void add(int a, ll x){
  120. 		addw(a, x, 0, n, 0);
  121. 	}
  122.  
  123. 	ll getw(int a, int nb, int ne, int p){
  124. 		if (a < nb || ne <= a) return d[p].m;
  125. 		if (ne - nb == 1) return -1;
  126. 		d[p * 2 + 1] = nadd(d[p * 2 + 1], d[p].a);
  127. 		d[p * 2 + 2] = nadd(d[p * 2 + 2], d[p].a);
  128. 		d[p].a = 0;
  129. 		return max(getw(a, nb, (nb + ne) / 2, p * 2 + 1), getw(a, (nb + ne) / 2, ne, p * 2 + 2));
  130. 	}
  131.  
  132. 	ll get(int a){
  133. 		return getw(a, 0, n, 0);
  134. 	}
  135. };
  136.  
  137. class seg2{
  138. public:
  139. 	bit b;
  140. 	seg s;
  141.  
  142. 	void init(int n){
  143. 		b.init(n);
  144. 		s.init(n);
  145. 	}
  146.  
  147. 	void add1(int a, ll x){
  148. 		s.add(a, x);
  149. 		s.add(a + 1, -x);
  150. 	}
  151.  
  152. 	void add2(int a, ll x){
  153. 		b.add(a, x);
  154. 		s.add(a, x);
  155. 	}
  156.  
  157. 	ll get(int a){
  158. 		ll w1 = s.get(a);
  159. 		ll w2 = b.sum(a);
  160. 		return w1 - w2;
  161. 	}
  162. };
  163.  
  164. class point{
  165. public:
  166. 	int o, ob1, ob2;
  167. 	int de;
  168.  
  169. 	int n;
  170. 	ll* m1;
  171. 	ll* m2;
  172.  
  173. 	rmq* r;
  174. 	seg2 s1, s2;
  175.  
  176. 	void init(int nw){
  177. 		n = nw;
  178. 		m1 = new ll[n];
  179. 		for (int i = 0; i < n; i++) m1[i] = 0;
  180. 		m2 = new ll[n];
  181. 		for (int i = 0; i < n; i++) m2[i] = 0;
  182. 		r = new rmq[n];
  183. 		s1.init(n);
  184. 		s2.init(n);
  185. 	}
  186.  
  187. 	void set1(int b1, int b2, ll x){
  188. 		r[b1].set(b2, x);
  189. 		ll w = r[b1].all();
  190. 		s1.add1(b1, w - m1[b1]);
  191. 		s2.add1(n - 1 - b1, w - m1[b1]);
  192. 		m1[b1] = w;
  193. 	}
  194.  
  195. 	void set2(int b, ll x){
  196. 		s1.add2(b, x - m2[b]);
  197. 		s2.add2(n - b, x - m2[b]);
  198. 		m2[b] = x;
  199. 	}
  200.  
  201. 	ll all(){
  202. 		return s1.get(0);
  203. 	}
  204.  
  205. 	ll get(int b1, int b2){
  206. 		ll w1 = s1.get(b1);
  207. 		ll w2 = s2.get(n - 1 - b1);
  208. 		ll w3 = r[b1].get(b2);
  209. 		return max(max(w1, w2), w3);
  210. 	}
  211.  
  212. 	ll tot(int a){
  213. 		return s1.b.sum(a);
  214. 	}
  215. };
  216.  
  217. class rnode{
  218. public:
  219. 	int o;
  220. 	vector<int> k;
  221. 	int s, sb;
  222. 	int km, kmb;
  223. };
  224.  
  225. rnode nn[555555];
  226. point hlp[555555];
  227. int hlpn;
  228.  
  229. int dfs1(int n){
  230. 	int l = nn[n].k.size();
  231. 	nn[n].km = 0;
  232. 	int all = 0;
  233. 	for (int i = 0; i < n; i++){
  234. 		int w = dfs1(nn[n].k[i]);
  235. 		if (nn[n].km < w){
  236. 			nn[n].km = w;
  237. 			nn[n].kmb = i;
  238. 		}
  239. 		all += w;
  240. 	}
  241. 	return all + 1;
  242. }
  243.  
  244. void dfs2(int n, int s, int sb){
  245. 	nn[n].s = s;
  246. 	nn[n].sb = sb;
  247. 	int l = nn[n].k.size();
  248. 	if (l == 0){
  249. 		hlp[s].init(sb + 1);
  250. 		hlp[s].r[sb].init(1);
  251. 	}
  252. 	else{
  253. 		int w = 0;
  254. 		for (int i = 0; i < l; i++){
  255. 			if (i == nn[n].kmb) dfs2(nn[n].k[i], s, sb + 1);
  256. 			else{
  257. 				hlp[hlpn].o = s;
  258. 				hlp[hlpn].ob1 = sb;
  259. 				hlp[hlpn].ob2 = w++;
  260. 				dfs2(nn[n].k[i], hlpn++, 1);
  261. 			}
  262. 		}
  263. 		hlp[s].r[sb].init(l);
  264. 	}
  265. }
  266.  
  267. void hl(){
  268. 	dfs1(0);
  269. 	hlpn = 1;
  270. 	hlp[0].o = -1;
  271. 	dfs2(0, 0, 0);
  272. }
  273.  
  274. class query{
  275. public:
  276. 	int s;
  277. 	int a;
  278. 	ll c;
  279. };
  280.  
  281. query qu[555555];
  282.  
  283. void qu12(int a, ll x){
  284. 	int now = nn[a].s;
  285. 	hlp[now].set2(nn[a].sb, x);
  286. 	int b1 = hlp[now].ob1;
  287. 	int b2 = hlp[now].ob2;
  288. 	ll all = hlp[now].all();
  289. 	now = hlp[now].o;
  290. 	while (now >= 0){
  291. 		hlp[now].set1(b1, b2, all);
  292. 		b1 = hlp[now].ob1;
  293. 		b2 = hlp[now].ob2;
  294. 		all = hlp[now].all();
  295. 		now = hlp[now].o;
  296. 	}
  297. }
  298.  
  299. ll qu3(int a){
  300. 	int now = nn[a].s;
  301. 	ll ma = hlp[now].get(nn[a].sb, -1);
  302. 	ll all = hlp[now].tot(nn[a].sb);
  303. 	int b1 = hlp[now].ob1;
  304. 	int b2 = hlp[now].ob2;
  305. 	now = hlp[now].o;
  306. 	while (now >= 0){
  307. 		ma = max(ma, all + hlp[now].get(b1, b2));
  308. 		all += hlp[now].tot(b1);
  309. 		b1 = hlp[now].ob1;
  310. 		b2 = hlp[now].ob2;
  311. 		now = hlp[now].o;
  312. 	}
  313. 	return ma;
  314. }
  315.  
  316. int main(){
  317. 	int n;
  318. 	scanf("%d", &n);
  319. 	for (int i = 0; i < n; i++) scanf("%d%d%lld", &qu[i].s, &qu[i].a, &qu[i].c);
  320. 	int allk = 1;
  321. 	for (int i = 0; i < n; i++){
  322. 		if (qu[i].s == 1){
  323. 			nn[allk].o = qu[i].a;
  324. 			nn[qu[i].a].k.push_back(allk++);
  325. 		}
  326. 	}
  327. 	hl();
  328. 	long amw = 1;
  329. 	for (int i = 0; i < n; i++){
  330. 		switch (qu[i].s){
  331. 		case 1:
  332. 			qu12(amw++, qu[i].c);
  333. 			break;
  334. 		case 2:
  335. 			qu12(qu[i].a, qu[i].c);
  336. 			break;
  337. 		case 3:
  338. 			printf("%lld\n", qu3(qu[i].a));
  339. 			break;
  340. 		}
  341. 	}
  342. 	return 0;
  343. }
  344.  
Success #stdin #stdout 0.01s 64264KB
comments (?)
stdin
copy 
6
1 0 10
1 1 7
3 1 0
2 2 5
1 0 17
3 0 0
stdout
copy 
10
17
https://ideone.com/3R073J
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!