ICPC南昌网络赛I题Yukino With Subinterval

带修改的一个区间分成几个极大连续区间

CDQ分治
  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 2e5 + 10;
  6 
  7 struct query{
  8     int x, y, val, op;
  9 }q[N * 5], tmp[N * 5];
 10 int tot;
 11 
 12 int n, m;
 13 int a[N];
 14 int ans[N], idx;
 15 int c[N];
 16 
 17 int lowbit(int x)
 18 {
 19     return x &(-x);
 20 }
 21 
 22 void add(int x, int y)
 23 {
 24     for (; x < N; x += lowbit(x))
 25         c[x] += y;
 26 }
 27 
 28 int ask(int x)
 29 {
 30     int res = 0;
 31     for (; x; x -= lowbit(x))
 32         res += c[x];
 33     return res;
 34 }
 35 void clear(int x){
 36   for (; x < N; x += lowbit(x))
 37       c[x] = 0;
 38 }
 39 
 40 void cdq(int l, int r)
 41 {
 42     if(l == r) return ;
 43     int mid = l + r >> 1;
 44     cdq(l, mid), cdq(mid + 1, r);
 45     int i = l, j = mid + 1, k = l;
 46     while(i <= mid && j <= r)
 47     {
 48         if(q[i].x <= q[j].x)
 49         {
 50             if(!q[i].op)
 51             {
 52                 add(q[i].y, q[i].val);
 53             }
 54             tmp[k ++] = q[i ++];
 55         }
 56         else
 57         {
 58             if(q[j].op) ans[q[j].op] += ask(q[j].y) * q[j].val;
 59             tmp[k ++] = q[j ++];
 60         }
 61     }
 62     while(i <= mid)
 63     {
 64         if(!q[i].op) add(q[i].y, q[i].val);
 65         tmp[k ++] = q[i ++];
 66     }
 67     while(j <= r)
 68     {
 69         if(q[j].op) ans[q[j].op] += ask(q[j].y) * q[j].val;
 70         tmp[k ++] = q[j ++];
 71     }
 72     for (int i = l; i <= r; i ++)
 73     {
 74         if(!q[i].op) clear(q[i].y);
 75         q[i] = tmp[i];
 76     }
 77 }
 78 
 79 int main()
 80 {
 81     scanf("%d%d", &n, &m);
 82     for (int i = 1; i <= n; i ++)
 83         scanf("%d", &a[i]);
 84     for (int i = 1; i <= n; i ++)
 85         if(a[i] != a[i - 1])
 86         q[++ tot] = {i, a[i], 1, 0};
 87     int op,pos, v, x, y, l, r;
 88     for (int i = 1; i <= m; i ++)
 89     {
 90         scanf("%d", &op);    
 91         if(op == 1)
 92         {
 93             scanf("%d%d", &pos, &v);
 94             if(a[pos] == v) continue;
 95             if(a[pos] != a[pos - 1]) 
 96             q[++ tot] = {pos, a[pos], -1, 0};
 97             if(a[pos] != a[pos + 1] && pos + 1 <= n)
 98             q[++ tot] = {pos + 1, a[pos + 1], -1, 0};
 99             a[pos] = v;
100             if(a[pos] != a[pos - 1])
101                 q[++ tot] = {pos, a[pos], 1, 0};
102             if(a[pos] != a[pos + 1] && pos + 1 <= n)
103                 q[++ tot] = {pos + 1, a[pos + 1], 1, 0};
104         }
105         else
106         {
107             scanf("%d%d%d%d", &l, &r, &x, &y);
108             ++ idx;
109             if(a[l] >= x && a[l] <= y) ++ ans[idx];
110             l ++;
111             if(l > r) continue;
112             q[++ tot] = {r, y, 1, idx};
113             q[++ tot] = {l - 1, y, -1, idx};
114             if(x > 1) q[++ tot] = {r, x - 1, -1, idx};
115             if(x > 1) q[++ tot] = {l - 1, x - 1, 1, idx};
116         }
117     }
118     cdq(1, tot);
119     for (int i = 1; i <= idx; i ++)
120         printf("%d
", ans[i]);        
121 }
View Code