BZOJ 3787: Gty的文艺妹子序列

BZOJ 3787: Gty的文艺妹子序列

自闭了很久，代码看了一遍又一遍，终于把过程想清楚了

其实还是太着急了，过程都没有想完整

分块做

$g[i][j] 表示 第j块对第i块的逆序对个数，i <= j$

第一位暴力，第二位树状数组维护

$smaller[i][j] 表示前i块中j的个数，第二维树状数组维护$

$这样我们就可以以log的时间求出前i块中 任意区间范围的数的个数$

$考虑把查询分成A, B, C 三块 A和C和两侧的散块，B为中间的整块$

$B块可以用g[][]得到答案$

$再考虑A和C 把A 和 C 放在一起跑一遍逆序对 就得到 AA ，CC， AC$

$再考虑 AB 和 BC 怎么做  AB 就是对于A中每个元素 找到B中有多少个比它小的$

$BC 就是 在B中对于C的每个元素找到有多少个比它大的$

再考虑 修改

$g[][] 每一块都是要修改的 $

$smaller[][] 修改当前块后面的所有块都要修改$

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define N 50010
  5 #define unit 300
  6 int n, q, a[N], lastans; 
  7 
  8 struct BIT
  9 {
 10     int a[N];
 11     void update(int x, int val)
 12     {
 13         for (; x <= n; x += x & -x)
 14             a[x] += val; 
 15     }
 16     int query(int x)
 17     {
 18         int res = 0;
 19         for (; x > 0; x -= x & -x)
 20             res += a[x]; 
 21         return res;
 22     }
 23     int query(int l, int r) 
 24     {
 25         return query(r) - query(l - 1);  
 26     }
 27 }g[unit], smaller[unit], bit;
 28 
 29 int pos[N], posl[unit], posr[unit];
 30 void init()
 31 {
 32     for (int i = 1; i <= n; ++i)
 33     {
 34         posr[pos[i]] = i;
 35         if (i == 1 || pos[i] != pos[i - 1])  
 36             posl[pos[i]] = i;
 37     }
 38     for (int i = 1; i <= pos[n]; ++i)
 39     {
 40         for (int j = posl[i]; j <= posr[i]; ++j)
 41         {
 42             bit.update(a[j], 1);
 43             g[i].update(i, bit.query(a[j] + 1, n));
 44         }
 45         for (int j = i + 1; j <= pos[n]; ++j)
 46             for (int k = posl[j]; k <= posr[j]; ++k)
 47                 g[j].update(i, bit.query(a[k] + 1, n));
 48         for (int j = posl[i]; j <= posr[i]; ++j)
 49             bit.update(a[j], -1);
 50     }
 51     for (int i = 1; i <= n; ++i)
 52     {
 53         for (int j = pos[i]; j <= pos[n]; ++j)   
 54             smaller[j].update(a[i], 1);  
 55     }
 56 }
 57 
 58 void update(int x, int y)
 59 {
 60     for (int i = pos[x] + 1; i <= pos[n]; ++i)  
 61         g[i].update(pos[x], -smaller[i].query(a[x] - 1) + smaller[i - 1].query(a[x] - 1));
 62     int tot = 0;
 63     for (int i = posl[pos[x]]; i < x; ++i) tot += a[i] > a[x];
 64     for (int i = x + 1; i <= posr[pos[x]]; ++i) tot += a[i] < a[x];
 65     g[pos[x]].update(pos[x], -tot);
 66     for (int i = 1; i < pos[x]; ++i)
 67         g[pos[x]].update(i, -smaller[i].query(a[x] + 1, n) + smaller[i - 1].query(a[x] + 1, n));
 68     for (int i = pos[x]; i <= pos[n]; ++i)
 69         smaller[i].update(a[x], -1);
 70     a[x] = y;
 71     for (int i = pos[x] + 1; i <= pos[n]; ++i)
 72         g[i].update(pos[x], smaller[i].query(a[x] - 1) - smaller[i - 1].query(a[x] - 1));
 73     tot = 0;
 74     for (int i = posl[pos[x]]; i < x; ++i) tot += a[i] > a[x];
 75     for (int i = x + 1; i <= posr[pos[x]]; ++i) tot += a[i] < a[x];
 76     g[pos[x]].update(pos[x], tot);
 77     for (int i = 1; i < pos[x]; ++i)
 78         g[pos[x]].update(i, smaller[i].query(a[x] + 1, n) - smaller[i - 1].query(a[x] + 1, n));
 79     for (int i = pos[x]; i <= pos[n]; ++i)
 80         smaller[i].update(a[x], 1); 
 81 }
 82 
 83 int query(int l, int r)
 84 {
 85     int res = 0; 
 86     if (pos[l] == pos[r])   
 87     {
 88         for (int i = l; i <= r; ++i) 
 89         {
 90             bit.update(a[i], 1);
 91             res += bit.query(a[i] + 1, n);                      
 92         }
 93         for (int i = l; i <= r; ++i)
 94             bit.update(a[i], -1);
 95         return res;
 96     }
 97     for (int i = l; i <= posr[pos[l]]; ++i)
 98     {
 99         bit.update(a[i], 1);
100         res += bit.query(a[i] + 1, n);
101         res += smaller[pos[r] - 1].query(a[i] - 1) - smaller[pos[l]].query(a[i] - 1);  
102     }
103     for (int i = posl[pos[r]]; i <= r; ++i)
104     {
105         bit.update(a[i], 1); 
106         res += bit.query(a[i] + 1, n);
107         res += smaller[pos[r] - 1].query(a[i] + 1, n) - smaller[pos[l]].query(a[i] + 1, n);
108     }
109     for (int i = l; i <= posr[pos[l]]; ++i) bit.update(a[i], -1);
110     for (int i = posl[pos[r]]; i <= r; ++i) bit.update(a[i], -1); 
111     for (int i = pos[l] + 1; i < pos[r]; ++i)  
112         res += g[i].query(pos[l] + 1, i);  
113     return res;
114 }
115 
116 void Run()
117 {
118     while (scanf("%d", &n) != EOF)
119     {
120         for (int i = 1; i <= n; ++i) scanf("%d", a + i), pos[i] = (i - 1) / unit + 1;   
121         lastans = 0; scanf("%d", &q); init();
122         for (int qq = 1, op, x, y; qq <= q; ++qq)
123         {
124             scanf("%d%d%d", &op, &x, &y);
125             x ^= lastans, y ^= lastans;
126             if (op) update(x, y);  
127             else printf("%dn", lastans = query(x, y));
128         }
129     }
130 }
131 
132 int main()
133 {
134     #ifdef LOCAL
135         freopen("Test.in", "r", stdin);
136     #endif 
137 
138     Run();
139     return 0;
140 }

转载于:.html