fork download
copy 
  1. #include <cstring>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <fstream>
  7. #include <iostream>
  8.  
  9. #define rep(i, l, r) for(int i = l; i <= r; i++)
  10. #define down(i, l, r) for(int i = l; i >= r; i--)
  11. #define MS 567890
  12. #define MAX 1037471823
  13. #define Q 1
  14.  
  15. using namespace std;
  16.  
  17. int n, m, a, b, s[MS], h[MS], l[MS], r[MS], k[MS], next[MS], last;
  18. long long sum[MS], lm[MS], mm[MS], rm[MS];
  19. bool rev[MS], e[MS];
  20. char q[10];
  21.  
  22. void Cal(int o)
  23. {
  24. 	if (!o) return;
  25. 	s[o] = s[r[o]] + s[l[o]] + 1;
  26. 	if (e[o]) 
  27. 		{ sum[o] = lm[o] = rm[o] = mm[o] = k[o] * s[o]; if (k[o] < 0) lm[o] = rm[o] = 0, mm[o] = k[o]; return; }
  28. 	sum[o] = sum[r[o]] + sum[l[o]] + k[o];
  29. 	if (rev[o]) 
  30. 		{ lm[o] = max(rm[r[o]], sum[r[o]]+k[o]+rm[l[o]]), rm[o] = max(lm[l[o]], sum[l[o]]+k[o]+lm[r[o]]), mm[o] = max(rm[l[o]]+k[o]+lm[r[o]], max(mm[l[o]], mm[r[o]])); }
  31. 	else
  32. 		{ lm[o] = max(lm[l[o]], sum[l[o]]+k[o]+lm[r[o]]), rm[o] = max(rm[r[o]], sum[r[o]]+k[o]+rm[l[o]]), mm[o] = max(rm[l[o]]+k[o]+lm[r[o]], max(mm[l[o]], mm[r[o]])); }
  33. }
  34.  
  35. int New(int x) { int o = last; last = next[last]; s[o] = 1, h[o] = 0, l[o] = r[o] = 0, k[o] = sum[o] = x, e[o] = rev[o] = false, lm[o] = mm[o] = rm[o] = x>0?x:0; return o; }
  36.  
  37. void Down(int o)
  38. {
  39. 	if (rev[o])
  40. 		{ int a; a = r[o], r[o] = l[o], l[o] = a; rev[r[o]] ^= 1, rev[l[o]] ^= 1, rev[o] ^= 1; Cal(r[o]); Cal(l[o]); Cal(o); }
  41. 	if (e[o])
  42. 		{ e[o] = false; e[r[o]] = e[l[o]] = true; k[r[o]] = k[l[o]] = k[o]; Cal(r[o]); Cal(l[o]); Cal(o); }
  43. }
  44.  
  45. void Splay(int x)
  46. {
  47. 	if (!x) return; int o = h[x]; Down(x);
  48. 	while (o)
  49. 	{
  50. 		if (l[o] == x) { l[h[o]] == o ? l[h[o]] = x : r[h[o]] = x; h[x] = h[o], h[r[x]] = o, l[o] = r[x], h[o] = x, r[x] = o; Cal(o); } 
  51. 		else { l[h[o]] == o ? l[h[o]] = x : r[h[o]] = x; h[x] = h[o], h[l[x]] = o, r[o] = l[x], h[o] = x, l[x] = o; Cal(o); } 
  52. 		o = h[x];
  53. 	}
  54. 	Cal(x);
  55. }
  56.  
  57. void Insert(int rr, int x)
  58. {
  59. 	if (!l[0]) { int now = New(x); l[0] = now; Cal(now); return; } 
  60. 	int o = l[0]; Down(o); while (rr <= s[l[o]]?l[o]:r[o]) { if (rr <= s[l[o]]) o = l[o]; else rr -= s[l[o]]+1, o = r[o]; Down(o); }
  61. 	int now = New(x); if (rr <= s[l[o]]) l[o] = now; else r[o] = now; h[now] = o;
  62. 	Splay(now); Cal(now);
  63. }
  64.  
  65. int FindRW(int rr)
  66. {
  67. 	int o = l[0]; Down(o); while (rr != s[l[o]]) { if (rr < s[l[o]]) o = l[o]; else rr -= s[l[o]]+1, o = r[o]; Down(o); } 
  68. 	return o;
  69. }
  70.  
  71. void InsertP(int o, int n)
  72. {
  73. 	int ln = (n-1)/2, rn = n-1-ln;
  74. 	if (ln) { int now = New(0); l[o] = now, h[now] = o; InsertP(now, ln); }
  75. 	scanf("%d", &k[o]);
  76. 	if (rn) { int now = New(0); r[o] = now, h[now] = o; InsertP(now, rn); }
  77. 	Cal(o);
  78. }
  79.  
  80. void InsertQ(int b, int n)
  81. {
  82. 	Splay(FindRW(b-1)); Splay(FindRW(b)); int now = New(0); r[l[l[0]]] = now, h[now] = l[l[0]]; InsertP(now, n); Splay(r[l[l[0]]]);
  83. }
  84.  
  85. void DeleteP(int o)
  86. {
  87. 	if (l[o]) DeleteP(l[o]); if (r[o]) DeleteP(r[o]); next[o] = last, last = o;
  88. }
  89.  
  90. void Delete(int b, int n) { Splay(FindRW(b-1)); Splay(FindRW(b+n)); DeleteP(r[l[l[0]]]); r[l[l[0]]] = 0; Cal(l[l[0]]); Cal(l[0]); }
  91.  
  92. void Edit(int b, int n, int x) { Splay(FindRW(b-1)); Splay(FindRW(b+n)); int o = r[l[l[0]]]; k[o] = x; e[o] = true; Splay(o); }
  93.  
  94. void Rev(int b, int n) { Splay(FindRW(b-1)); Splay(FindRW(b+n)); int o = r[l[l[0]]]; rev[o] ^= 1; Splay(o); }
  95.  
  96. void QSum(int b, int n) { Splay(FindRW(b-1)); Splay(FindRW(b+n)); printf("%lld\n", sum[r[l[l[0]]]]); }
  97.  
  98. void QMaxSum() { Splay(FindRW(0)); Splay(FindRW(s[l[0]]-1)); printf("%lld\n", mm[r[l[l[0]]]]); }
  99.  
  100. int main()
  101. {
  102. 	scanf("%d%d", &n, &m); mm[0] = -MAX; 
  103. 	l[0] = 1, l[1] = 2, h[2] = 1, s[1] = 2, s[2] = 1;
  104. 	last = 3; rep(i, 3, MS-1) next[i] = i+1;
  105. 	InsertQ(1, n);
  106. 	rep(i, 1, m)
  107. 	{
  108. 		scanf("%s", q);
  109. 		if (q[2] == 'S')
  110. 			{ scanf("%d%d", &b, &n); InsertQ(b+1, n); }
  111. 		else if (q[2] == 'L') 
  112. 			{ scanf("%d%d", &b, &n); Delete(b, n); }
  113. 		else if (q[2] == 'K')
  114. 			{ scanf("%d%d%d", &b, &n, &a); Edit(b, n, a); }
  115. 		else if (q[2] == 'V')
  116. 			{ scanf("%d%d", &b, &n); Rev(b, n); }
  117. 		else if (q[2] == 'T')
  118. 			{ scanf("%d%d", &b, &n); QSum(b, n); }
  119. 		else if (q[2] == 'X') QMaxSum();
  120. 	}
  121. 	return 0;
  122. }
Success #stdin #stdout 0s 35512KB
comments (?)
stdin
copy 
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
stdout
copy 
-1
10
1
10
https://ideone.com/aWqiz7
BZOJ 1500
language:
C++ (gcc 8.3)
created:
10 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!