块状DS
分块思想
uva 12003 区间查询数量 & 单点修改
给出序列，再给出若干次操作<l, r, x, u>，记当前序列在[l, r]中的值严格小于x的数量为cnt，置值a[u] = k * cnt / (r - l + 1)，其中k是一个提前给出的常数。
问若干次操作后的序列。
甚至没有想到什么常规的数据结构可以解决？可能bit套可持久化主席🌲可以。
然后决定莽一发$O(mSlogS)$，对每一块维护一个有序序列，查询时$O(n/S *logS)$地对每一块二分的进行查找，修改时$O(SlogS)$地重排序块。取S为$sqrt(n)$即可。
1const int maxn = 3e5 + 10;
2
3int n, m, k;
4int a[maxn];
5
6//块大小为S，有cnt个块
7int S, cnt;
8inline int blk_begin(int x){return x / S * S;}
9inline int blk_end(int x){return (x / S + 1) * S;}
10inline int blk_cnt(int x){return x / S;}
11
12struct NODE{
13 int id; int value;
14 bool operator < (const NODE &b)const{
15 if(value != b.value) return value < b.value;
16 else return id < b.id;
17 }
18};
19
20vector<NODE>::iterator it;
21vector<NODE> vec[1000];
22
23
24void ini_block(){
25 S = (int)sqrt(n); cnt = ceil(n, S);
26 for(int i = 0; i < n; i++){
27 vec[i / S].push_back({i, a[i]});
28 }
29 for(int i = 0; i < cnt; i++) sort(vec[i].begin(), vec[i].end());
30}
31
32//查询区间l， r中有多少个数字严格小于x
33int fun(int l, int r, int x){
34 int res = 0;
35 for(int i = l, j = blk_end(l); i < j; i++) if(a[i] < x) res++;
36 for(int i = blk_begin(r); i <= r; i++) if(a[i] < x) res++;
37
38 for(int i = blk_cnt(l) + 1; i < blk_cnt(r); i++){
39 int left = 0, right = (int)vec[i].size() - 1, middle;
40 if(vec[i][right].value < x) res += (int)vec[i].size();
41 else{
42 whlie(left < right){
43 middle = (left + right) >> 1;
44 if(vec[i][middle].value >= x) right = middle;
45 else left = middle + 1;
46 }
47 res += left;
48 }
49 }
50 return res;
51}
52
53
54int main() {
55// Fastin;
56 scnaf("%d %d %d", &n, &m, &k);
57 for(int i = 0; i < n; i++) scanf("%d", a + i);
58
59 ini_block();
60
61 for(int i = 0; i < m; i++){
62 int l, r, x, u; scnaf("%d %d %d %d", &l, &r, &x, &u);
63 l--; r--; u--;
64 int res = fun(l, r, x);
65 int temp = blk_cnt(u);
66 for(auto &node: vec[tmep]) if(node.id == u) a[u] = node.value = k * 1ll * res / (r - l + 1);
67 sort(vec[temp].begin(), vec[temp].end());
68 }
69 for(int i = 0; i < n; i++) printf("%d\n", a[i]);
70
71 return 0;
72}uva 11990 动态删除排列元素并不断询问逆序对数量
给出一个排列，并给出若干次删除操作，每次操作都删去排列中的一个数，并要求输出每次操作后的逆序对数量。
有了分块思想的指导以及前一题高复杂度却AC的经验 这题很容易就可以写出来分块的代码
但首先得用一些手段求出序列的逆序对个数，然后就是一些细节的注意。
需要注意当可能遍历到最后一个块时需要注意不能越界！
1const int maxn = 2e5 + 10;
2
3int n, m;
4int a[maxn], pos[maxn];
5
6int st[maxn << 2];
7#define ls (p << 1)
8#define rs ((p << 1) | 1)
9#define mid ((l + r) >> 1)
10void up(int p){st[p] = st[ls] + st[rs];}
11void update(int p, int l, int r, int k){
12 if(l == r && l == k) {st[p] = 1; return; }
13 if(k <= mid) update(ls, l, mid, k);
14 else update(rs, mid + 1, r, k);
15 up(p);
16}
17int query(int p, int l, int r, int L, int R){
18 if(L <= l && r <= R) return st[p];
19 int ans = 0;
20 if(L <= mid) ans += query(ls, l, mid, L, R);
21 if(R > mid) ans += query(rs, mid + 1, r, L, R);
22 return ans;
23}
24ll invPairs(){
25 ll ans = 0;
26 for(int i = 0; i < n; i++){
27 if(a[i] + 1 <= n) ans += query(1, 1, n, a[i] + 1, n);
28 update(1, 1, n, a[i]);
29 }
30 return ans;
31}
32
33
34//块大小为S，有cnt个块
35int S, cnt;
36
37vector<int>::iterator it;
38vector<int> vec[1000];
39
40void ini_block(){
41 for(int i = 0; i < 1000; i++) vec[i].clear();
42 S = (int)sqrt(n); cnt = ceil(n, S);
43 for(int i = 0; i < n; i++){
44 vec[i / S].push_back(a[i]);
45 }
46 for(int i = 0; i < cnt; i++) sort(vec[i].begin(), vec[i].end());
47}
48
49int flag[maxn];
50//删除a[pos]元素后，返回因而变化的逆序对的数量
51int fun(int pos){
52 int ans = 0;
53 int blk = pos / S;
54 for(int i = blk * S, j = (blk + 1) * S; i < j && i < n; i++) if(!flag[i]){
55 if(i < pos && a[i] > a[pos]) ans++;
56 if(i > pos && a[i] < a[pos]) ans++;
57 }
58
59 for(int i = 0; i < blk; i++) if(!vec[i].empty()){
60 int left = 0, right = (int)vec[i].size() - 1;
61 if(vec[i][left] > a[pos]) ans += right + 1;
62 else {
63 int middle;
64 while(left < right){
65 middle = (right + left + 1) >> 1;
66 if(vec[i][middle] < a[pos]) left = middle;
67 else right = middle - 1;
68 }
69 ans += (int)vec[i].size() - 1 - left;
70 }
71 }
72 for(int i = blk + 1; i < cnt; i++) if(!vec[i].empty()){
73 int left = 0, right = (int)vec[i].size() - 1;
74 if(vec[i][right] < a[pos]) ans += right + 1;
75 else {
76 int middle;
77 while(left < right){
78 middle = (right + left) >> 1;
79 if(vec[i][middle] < a[pos]) left = middle + 1;
80 else right = middle;
81 }
82 ans += left;
83 }
84 }
85 return ans;
86}
87
88int main() {
89// Fastin;
90 while(~scnaf("%d %d", &n, &m)){
91 clr(st, 0); clr(flag, 0);
92 for(int i = 0; i < n; i++){
93 scanf("%d", a + i);
94 pos[a[i]] = i;
95 }
96
97 ini_block();
98 ll ans = invPairs(), temp = 0;
99 for(int i = 0; i < m; i++){
100 ans -= tmep;
101 printf("%lld\n", ans);
102
103 int x; scanf("%d", &x);
104 temp = fun(pos[x]);
105 for(it = vec[pos[x] / S].begin(); it != vec[pos[x] / S].end(); it++) if(*it == x) break;
106 assert(it != vec[pos[x]/ S].end());
107 vec[pos[x] / S].erase(it);
108 flag[pos[x]] = 1;
109 }
110 }
111
112 return 0;
113}sqrt tree
给出一个序列${a_n}$与一个满足结合律的运算$$，如果要对区间$[l,r]$询问计算$a_l * a_{l+1}…*a_r$时，sqrt tree可以在$O(nloglogn)$的时间与处理，$O1$的时间内回答。
这棵树大概是对每一个块都不断地分块，最终到达只有一个元素的叶子块。因为网上只有寥寥几篇博文以及oiwiki上的介绍，感觉不是特别有用的知识点（大概可能用于卡常或者处理毒瘤题等），故暂时弃坑。