Stikked

Untitled

From Soiled Crow, 3 Years ago, written in Plain Text, viewed 389 times.
URL http://axuhongbo.top/paste/view/3a775c27 Embed
Download Paste or View Raw
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 112345;
  5.  
  6. struct Node {
  7.     int minn;
  8.     int lazy;
  9.     int sum;
  10. } tree[MAX * 4];
  11.  
  12. int data[MAX];
  13.  
  14. #define lson (o<<1)
  15. #define rson (o<<1|1)
  16. #define MID int m = (l + r) / 2
  17.  
  18. void push_down(int o) {
  19.     if (tree[o].lazy) {
  20.         int &lazy = tree[o].lazy;
  21.         tree[lson].minn -= lazy;
  22.         tree[rson].minn -= lazy;
  23.         tree[lson].lazy += lazy;
  24.         tree[rson].lazy += lazy;
  25.         lazy = 0;
  26.     }
  27. }
  28.  
  29. void build(int o, int l, int r) {
  30.     tree[o].lazy = 0;
  31.     if (l == r) {
  32.         tree[o].minn = data[l];
  33.         tree[o].sum = 0;
  34.         return;
  35.     }
  36.     MID;
  37.     build(lson, l, m);
  38.     build(rson, m + 1, r);
  39.     tree[o].minn = min(tree[lson].minn, tree[rson].minn);
  40.     tree[o].sum = tree[lson].sum + tree[rson].sum;
  41. }
  42.  
  43. void update(int o, int l, int r, int ql, int qr) {
  44.     if (qr < l || r < ql) return;
  45.     if (ql <= l && r <= qr) {
  46.         tree[o].lazy += 1;
  47.         tree[o].minn -= 1;
  48.         return;
  49.     }
  50.     push_down(o);
  51.     MID;
  52.     update(lson, l, m, ql, qr);
  53.     update(rson, m + 1, r, ql, qr);
  54.     tree[o].minn = min(tree[lson].minn, tree[rson].minn);
  55.     tree[o].sum = tree[lson].sum + tree[rson].sum;
  56. }
  57.  
  58. int ans = 0;
  59.  
  60. void dfs(int o, int l, int r) {
  61.     if (l == r) {
  62.         tree[o].minn = data[l];
  63.         tree[o].sum++;
  64.         return;
  65.     }
  66.     push_down(o);
  67.     MID;
  68.     if (tree[lson].minn == 0) dfs(lson, l, m);
  69.     if (tree[rson].minn == 0) dfs(rson, m + 1, r);
  70.     tree[o].minn = min(tree[lson].minn, tree[rson].minn);
  71.     tree[o].sum = tree[lson].sum + tree[rson].sum;
  72. }
  73.  
  74. int query(int o, int l, int r, int ql, int qr) {
  75.     if (qr < l || r < ql) return 0;
  76.     if (ql <= l && r <= qr) {
  77.         return tree[o].sum;
  78.     }
  79.     push_down(o);
  80.     MID;
  81.     return query(lson, l, m, ql, qr) + query(rson, m + 1, r, ql, qr);
  82. }
  83.  
  84. int main() {
  85.     int n, m;
  86.     while(~scanf("%d %d", &n, &m)){
  87.         for (int i = 1; i <= n; i++) scanf("%d", data + i);
  88.         build(1, 1, n);
  89.         while (m--) {
  90.             char op[10];
  91.             int l, r;
  92.             scanf("%s %d %d", op, &l, &r);
  93.             if (op[0] == 'a') {
  94.                 update(1, 1, n, l, r);
  95.                 dfs(1, 1, n);
  96.             } else {
  97.                 printf("%d\n", query(1, 1, n, l, r));
  98.             }
  99.         }
  100.     }
  101.     return 0;
  102. }

Replies to Untitled rss

Title Name Language When
Re: Untitled Cobalt Panda text 3 Years ago.

Reply to "Untitled"

Here you can reply to the paste above

captcha
Powered by Stikked