Guest User

Untitled

a guest
Mar 13th, 2019
981
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. Code for problem E by cookiedoth
  4. Generated 23 Feb 2019 at 02.32 P
  5.  
  6.  
  7. ▅███████ ]▄▄▄▄▄▄▄
  8. █████████▅▄▃
  9. Il████████████████]
  10. ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤
  11.  
  12. ~_^
  13. =_=
  14. ¯\_(ツ)_/¯
  15.  
  16. */
  17.  
  18. #include <iostream>
  19. #include <fstream>
  20. #include <vector>
  21. #include <set>
  22. #include <map>
  23. #include <bitset>
  24. #include <algorithm>
  25. #include <iomanip>
  26. #include <cmath>
  27. #include <ctime>
  28. #include <functional>
  29. #include <unordered_set>
  30. #include <unordered_map>
  31. #include <string>
  32. #include <queue>
  33. #include <deque>
  34. #include <stack>
  35. #include <complex>
  36. #include <cassert>
  37. #include <random>
  38. #include <cstring>
  39. #include <numeric>
  40. #define ll long long
  41. #define ld long double
  42. #define null NULL
  43. #define all(a) a.begin(), a.end()
  44. #define debug(a) cerr << #a << " = " << a << endl
  45. #define forn(i, n) for (int i = 0; i < n; ++i)
  46. #define sz(a) (int)a.size()
  47.  
  48. using namespace std;
  49.  
  50. template<class T> int chkmax(T &a, T b) {
  51. if (b > a) {
  52. a = b;
  53. return 1;
  54. }
  55. return 0;
  56. }
  57.  
  58. template<class T> int chkmin(T &a, T b) {
  59. if (b < a) {
  60. a = b;
  61. return 1;
  62. }
  63. return 0;
  64. }
  65.  
  66. template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
  67. while (begin != end) {
  68. out << (*begin) << " ";
  69. begin++;
  70. }
  71. out << endl;
  72. }
  73.  
  74. template<class T> void output(T x, ostream& out = cerr) {
  75. output(x.begin(), x.end(), out);
  76. }
  77.  
  78. void fast_io() {
  79. ios_base::sync_with_stdio(0);
  80. cin.tie(0);
  81. cout.tie(0);
  82. }
  83.  
  84. const ll DEFAULT = -1e18;
  85.  
  86. struct st {
  87. vector<ll> t, len, sum, add_mod, set_mod;
  88. int n;
  89.  
  90. void build(vector<ll> &a, int v, int tl, int tr) {
  91. if (tl == tr) {
  92. t[v] = sum[v] = a[tl];
  93. len[v] = 1;
  94. }
  95. else {
  96. int tm = (tl + tr) >> 1;
  97. build(a, v * 2, tl, tm);
  98. build(a, v * 2 + 1, tm + 1, tr);
  99. t[v] = max(t[v * 2], t[v * 2 + 1]);
  100. sum[v] = sum[v * 2] + sum[v * 2 + 1];
  101. len[v] = (tr - tl + 1);
  102. }
  103. }
  104.  
  105. st(vector<ll> &a) {
  106. n = a.size();
  107. t.resize(4 * n);
  108. sum.resize(4 * n);
  109. add_mod.resize(4 * n);
  110. set_mod.resize(4 * n, DEFAULT);
  111. len.resize(4 * n);
  112. build(a, 1, 0, n - 1);
  113. }
  114.  
  115. st() {}
  116.  
  117. void apply_add_mod(int v, ll val) {
  118. if (set_mod[v] != DEFAULT) {
  119. set_mod[v] += val;
  120. }
  121. else {
  122. add_mod[v] += val;
  123. }
  124. }
  125.  
  126. void apply_set_mod(int v, ll val) {
  127. add_mod[v] = 0;
  128. set_mod[v] = val;
  129. }
  130.  
  131. void push(int v) {
  132. assert(add_mod[v] == 0 || set_mod[v] == DEFAULT);
  133. if (add_mod[v]) {
  134. t[v] += add_mod[v];
  135. sum[v] += add_mod[v] * len[v];
  136. apply_add_mod(v * 2, add_mod[v]);
  137. apply_add_mod(v * 2 + 1, add_mod[v]);
  138. add_mod[v] = 0;
  139. }
  140. if (set_mod[v] != DEFAULT) {
  141. t[v] = set_mod[v];
  142. sum[v] = set_mod[v] * len[v];
  143. apply_set_mod(v * 2, set_mod[v]);
  144. apply_set_mod(v * 2 + 1, set_mod[v]);
  145. set_mod[v] = DEFAULT;
  146. }
  147. }
  148.  
  149. ll get_sum(int v) {
  150. if (set_mod[v] != DEFAULT) {
  151. return set_mod[v] * len[v];
  152. }
  153. if (add_mod[v]) {
  154. return add_mod[v] * len[v] + sum[v];
  155. }
  156. return sum[v];
  157. }
  158.  
  159. ll get_t(int v) {
  160. if (set_mod[v] != DEFAULT) {
  161. return set_mod[v];
  162. }
  163. if (add_mod[v]) {
  164. return add_mod[v] + t[v];
  165. }
  166. return t[v];
  167. }
  168.  
  169. void recalc(int v) {
  170. t[v] = max(get_t(v * 2), get_t(v * 2 + 1));
  171. sum[v] = get_sum(v * 2) + get_sum(v * 2 + 1);
  172. }
  173.  
  174. void add_update(int l, int r, ll val, int v, int tl, int tr) {
  175. if (l > r) {
  176. return;
  177. }
  178. if (l == tl && r == tr) {
  179. apply_add_mod(v, val);
  180. return;
  181. }
  182. int tm = (tl + tr) >> 1;
  183. push(v);
  184. add_update(l, min(r, tm), val, v * 2, tl, tm);
  185. add_update(max(l, tm + 1), r, val, v * 2 + 1, tm + 1, tr);
  186. recalc(v);
  187. }
  188.  
  189. void set_update(int l, int r, ll val, int v, int tl, int tr) {
  190. if (l > r) {
  191. return;
  192. }
  193. if (l == tl && r == tr) {
  194. apply_set_mod(v, val);
  195. return;
  196. }
  197. int tm = (tl + tr) >> 1;
  198. push(v);
  199. set_update(l, min(r, tm), val, v * 2, tl, tm);
  200. set_update(max(l, tm + 1), r, val, v * 2 + 1, tm + 1, tr);
  201. recalc(v);
  202. }
  203.  
  204. ll get_sum(int l, int r, int v, int tl, int tr) {
  205. if (l > r) {
  206. return 0;
  207. }
  208. if (l == tl && r == tr) {
  209. return get_sum(v);
  210. }
  211. int tm = (tl + tr) >> 1;
  212. push(v);
  213. ll res_l = get_sum(l, min(r, tm), v * 2, tl, tm);
  214. ll res_r = get_sum(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr);
  215. return res_l + res_r;
  216. }
  217.  
  218. int lower_bound(ll val, int v, int tl, int tr) {
  219. if (tl == tr) {
  220. return tl;
  221. }
  222. push(v);
  223. int tm = (tl + tr) >> 1;
  224. if (get_t(v * 2) >= val) {
  225. return lower_bound(val, v * 2, tl, tm);
  226. }
  227. else {
  228. return lower_bound(val, v * 2 + 1, tm + 1, tr);
  229. }
  230. }
  231.  
  232. //interface
  233.  
  234. void add_update(int l, int r, ll val) {
  235. add_update(l, r, val, 1, 0, n - 1);
  236. }
  237.  
  238. void set_update(int l, int r, ll val) {
  239. set_update(l, r, val, 1, 0, n - 1);
  240. }
  241.  
  242. ll get_sum(int l, int r) {
  243. ll res = get_sum(l, r, 1, 0, n - 1);
  244. return res;
  245. }
  246.  
  247. int lower_bound(ll val) {
  248. if (get_t(1) < val) {
  249. return n;
  250. }
  251. else {
  252. return lower_bound(val, 1, 0, n - 1);
  253. }
  254. }
  255. };
  256.  
  257. int n;
  258. vector<ll> a, k, prefK, b;
  259.  
  260. signed main() {
  261. fast_io();
  262.  
  263. cin >> n;
  264. a.resize(n);
  265. k.resize(n - 1);
  266. prefK.resize(n);
  267. for (int i = 0; i < n; ++i) {
  268. cin >> a[i];
  269. }
  270. for (int i = 0; i < n - 1; ++i) {
  271. cin >> k[i];
  272. }
  273. for (int i = 1; i < n; ++i) {
  274. prefK[i] = prefK[i - 1] + k[i - 1];
  275. }
  276.  
  277. b.resize(n);
  278. for (int i = 0; i < n; ++i) {
  279. b[i] = a[i] - prefK[i];
  280. }
  281. st t(b), t1(prefK);
  282.  
  283. int q;
  284. cin >> q;
  285. for (int i = 0; i < q; ++i) {
  286. char type;
  287. cin >> type;
  288. if (type == 's') {
  289. int l, r;
  290. cin >> l >> r;
  291. l--;
  292. r--;
  293. cout << t.get_sum(l, r) + t1.get_sum(l, r) << '\n';
  294. }
  295. if (type == '+') {
  296. int pos;
  297. ll val;
  298. cin >> pos >> val;
  299. pos--;
  300. val += t.get_sum(pos, pos);
  301. int pos1 = t.lower_bound(val);
  302. t.set_update(pos, pos1 - 1, val);
  303. }
  304. }
  305. }
RAW Paste Data