Advertisement
haufont

Untitled

Mar 9th, 2017
398
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <time.h>
  4. #include <stdlib.h>
  5. #include <string>
  6. #include <algorithm>
  7. #include <queue>
  8.  
  9. using namespace std;
  10.  
  11. const long long INF = 1e17;
  12.  
  13. #define mINF -10000000000
  14. #define pb push_back
  15. #define mp make_pair
  16.  
  17. struct Treap {
  18. long long x, y, cnt, summ;
  19. pair<bool, int> usdd;
  20. Treap* leftp;
  21. Treap* rightp;
  22. }; // Treap* nw = new Treap({ value, rand(), 1, mINF, 0, value, NULL, NULL });
  23.  
  24. long long cnt(Treap* Treap) {
  25. if (Treap == NULL)
  26. return 0;
  27. else
  28. return Treap->cnt;
  29. }
  30.  
  31. long long summ(Treap* Treap) {
  32. if (Treap == NULL)
  33. return 0;
  34. else
  35. return Treap->summ;
  36. }
  37.  
  38. void pushg2(Treap* root, pair<bool, int> sd)
  39. {
  40. if (!sd.first)
  41. {
  42. root->usdd.second += sd.second;
  43. }
  44. else
  45. {
  46. root->usdd.first = sd.first;
  47. root->usdd.second = sd.second;
  48. }
  49. }
  50.  
  51. void pushg(Treap* root, pair<bool, int> sd)
  52. {
  53. if (!sd.first)
  54. {
  55. root->usdd.second += sd.second;
  56. root->summ += root->cnt * sd.second;
  57. }
  58. else
  59. {
  60. root->usdd.first = sd.first;
  61. root->usdd.second = sd.second;
  62. root->summ = root->cnt * sd.second;
  63. }
  64. }
  65.  
  66. void push_summ(Treap* Treap) {
  67. if (Treap != NULL)
  68. {
  69. if (!Treap->usdd.first)
  70. {
  71. Treap->summ += Treap->cnt * Treap->usdd.second;
  72. Treap->x += Treap->usdd.second;
  73. }
  74. else
  75. {
  76. Treap->summ = Treap->cnt * Treap->usdd.second;
  77. Treap->x = Treap->usdd.second;
  78. }
  79. if (Treap->leftp != NULL)
  80. {
  81. pushg(Treap->leftp, Treap->usdd);
  82. }
  83. if (Treap->rightp != NULL)
  84. {
  85. pushg(Treap->rightp, Treap->usdd);
  86. }
  87. Treap->usdd = mp(0,0);
  88. }
  89. }
  90.  
  91. void upd_cnt(Treap* Treap)
  92. {
  93. if (Treap != NULL) Treap->cnt = 1 + cnt(Treap->rightp) + cnt(Treap->leftp);
  94. }
  95.  
  96. void upd_summ(Treap* Treap)
  97. {
  98. if (Treap != NULL) Treap->summ = summ(Treap->rightp) + summ(Treap->leftp) + Treap->x;
  99. }
  100.  
  101. void recalc(Treap* Treap) {
  102. push_summ(Treap);
  103. upd_cnt(Treap);
  104. upd_summ(Treap);
  105. }
  106.  
  107. pair<Treap*, Treap*> split(Treap *root, long long x, long long summ = 0)
  108. {
  109. recalc(root);
  110. if (root == NULL) {
  111. return{ NULL, NULL };
  112. }
  113. long long id = summ + cnt(root->leftp);
  114. if (id < x) {
  115. auto res = split(root->rightp, x, id + 1);
  116. root->rightp = res.first;
  117. recalc(root);
  118. return{ root, res.second };
  119. }
  120. else {
  121. auto res = split(root->leftp, x, summ);
  122. root->leftp = res.second;
  123. recalc(root);
  124. return{ res.first, root };
  125. }
  126. }
  127.  
  128. Treap* Merge(Treap* l, Treap* r) {
  129. recalc(l);
  130. recalc(r);
  131. if (l == NULL) {
  132. return r;
  133. }
  134. if (r == NULL) {
  135. return l;
  136. }
  137. if (l->y > r->y) {
  138. l->rightp = Merge(l->rightp, r);
  139. recalc(l);
  140. return l;
  141. }
  142. else {
  143. r->leftp = Merge(l, r->leftp);
  144. recalc(r);
  145. return r;
  146. }
  147. }
  148.  
  149. Treap* Insert(Treap* root, long long value, long long x) {
  150. auto spl = split(root, x);
  151. pair <bool, int> d;
  152. Treap* nw = new Treap({ value, rand(), 1, value, d, NULL, NULL });
  153. auto a = Merge(Merge(spl.first, nw), spl.second);
  154. recalc(a);
  155. return a;
  156. }
  157.  
  158. Treap* del(Treap* root, long long l, long long r) {
  159. auto spl1 = split(root, l);
  160. auto spl2 = split(spl1.second, r - l);
  161. auto a = Merge(spl1.first, spl2.second);
  162. recalc(a);
  163. return a;
  164. }
  165.  
  166. Treap* get_sumd(Treap* root, long long l, long long r, long long x) {
  167. auto spl1 = split(root, l);
  168. auto spl2 = split(spl1.second, r - l);
  169. pushg2(spl2.first, mp(0, x));
  170. auto a = Merge(spl1.first, Merge(spl2.first, spl2.second));
  171. push_summ(a);
  172. recalc(a);
  173. return a;
  174. }
  175.  
  176. Treap* get_vd(Treap* root, long long l, long long r, long long x) {
  177. auto spl1 = split(root, l);
  178. auto spl2 = split(spl1.second, r - l);
  179. pushg2(spl2.first, mp(1, x));
  180. auto a = Merge(spl1.first, Merge(spl2.first, spl2.second));
  181. recalc(a);
  182. return a;
  183. }
  184.  
  185. long long get_sum(Treap* root, long long l, long long r) {
  186. auto spl1 = split(root, l);
  187. auto spl2 = split(spl1.second, r - l);
  188. auto ans = summ(spl2.first);
  189. root = Merge(spl1.first, Merge(spl2.first, spl2.second));
  190. return ans;
  191. }
  192.  
  193. Treap* sdv(Treap* root, long long l, long long r, long long q)
  194. {
  195. recalc(root);
  196. auto spl1 = split(root, l);
  197. auto spl2 = split(spl1.second, r - l);
  198. auto spl3 = split(spl2.first, r - l - q);
  199. auto a = Merge(spl1.first, Merge(Merge(spl3.second, spl3.first), spl2.second));
  200. recalc(a);
  201. return a;
  202. }
  203.  
  204. void output(Treap* t) {
  205. if (!t) return;
  206. push_summ(t);
  207. output(t->leftp);
  208. cout << t->x << " ";
  209. output(t->rightp);
  210. }
  211.  
  212. int main()
  213. {
  214. ios_base::sync_with_stdio(false);
  215. cin.tie(NULL);
  216. srand(time(NULL));
  217. long long n, h;
  218. char rt;
  219. cin >> n;
  220. Treap* root = NULL;
  221. long long l, r;
  222.  
  223. for (int i = 0; i < n; i++)
  224. {
  225. cin >> rt;
  226. if (rt == '0')
  227. {
  228. cin >> l >> r >> h;
  229. l--;
  230. root = get_vd(root, l, r, h);
  231. //output(root);
  232. //cout << endl;
  233. }
  234. if (rt == '1')
  235. {
  236. cin >> l >> r >> h;
  237. l--;
  238. root = get_sumd(root, l, r, h);
  239. //output(root);
  240. //cout << endl;
  241. }
  242. if (rt == '2')
  243. {
  244. cin >> l >> h;
  245. l--;
  246. root = Insert(root, h, l);
  247. //output(root);
  248. //cout << endl;
  249. }
  250. if (rt == '3')
  251. {
  252. cin >> l >> r;
  253. l--;
  254. cout << get_sum(root, l, r) << "\n";
  255. //output(root);
  256. //cout << endl;
  257. }
  258. if (rt == 'X')
  259. {
  260. cin >> l >> r >> h;
  261. l--;
  262. root = sdv(root, l, r, h % abs(r - l));
  263. //output(root);
  264. //cout << endl;
  265. }
  266. }
  267. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement