更新了三维偏序问题的拓展
cdq分治
\(cdq\)分治是一种由\(IOI\ Au\)选手\(cdq\)提出的离线分治算法，又称基于时间的分治算法。
二维偏序问题
这是\(cdq\)分治最早提出的时候解决的问题，大意为：给定\(n\)对二元组\((a_{i},b_{i})\)，求\(cnt_i=\sum_{j=i+1}^n[a_j>a_i\ and \ b_j>b_i]\)。
这个和逆序对有点像，先将二元组按\(a\)为第一关键字排序，那么\(a\)就一定有序了，即求下标和数值(\(b\))都比当前二元组(\(b\))大的二元组数量，和逆序对相反，就是正序对。
逆序对有一个很高效的\(O(nlog_2n)\)的求法，就是归并排序。当然，正序对也可以用归并排序做，其原理是类似的。
其实，这就是\(cdq\)分治的原型了。从分治的角度考虑，\(solve(l,r)\)对序列\([l,r]\)的部分进行求解，首先我们将\([l,r]\)分治为\([l,mid]\)和\([mid+1,r]\)这两部分，这是可以递归求解的。那么，我们要考虑的就是分别在区间\([l,mid]\)和\([mid+1,r]\)两边的元素构成的正序对数量。
怎么求呢？归并就可以了。在把两边的元素归并排序的过程中，左边的二元组的第一维(\(a\))显然还小于右边，但是在归并的过程中我们可以得知第二维\(b\)的关系，这样就方便统计答案了。
所以，求解二维偏序问题的\(cdq\)分治算法就是以归并排序求逆序对为原型的。
\(Code:\)()
#includeusing namespace std;const int N=200020;int n,ans[N];struct node{int a,b,id;};node c[N],cur[N];inline void input(void){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d%d",&c[i].a,&c[i].b) , c[i].id = i;}inline bool compare(node x,node y){ return x.a == y.a ? x.b < y.b : x.a < y.a;}inline void cdq(int l,int r){ if ( l == r ) return; int mid = l+r >> 1 , p = l , q = mid+1 , t = l-1; cdq(l,mid); cdq(mid+1,r); while ( p <= mid && q <= r ) { if ( c[p].b <= c[q].b ) cur[++t] = c[p++]; if ( c[p].b > c[q].b ) ans[ c[q].id ] += p-l , cur[++t] = c[q++]; } while ( p <= mid ) cur[++t] = c[p++]; while ( q <= r ) ans[ c[q].id ] += mid-l+1 , cur[++t] = c[q++]; for (int i=l;i<=r;i++) c[i] = cur[i];}int main(void){ input(); sort( c+1 , c+n+1 , compare ); cdq(1,n); for (int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0;}
二维偏序问题的拓展
Describetion
假设有一列数\({A_i }(1 ≤ i ≤ n)\) ，支持如下两种操作：
(1)将\(A_k\)的值加\(D\)。(\(k\),\(D\)是输入的数)
(2) 输出\(A_s+A_{s+1}+…+A_t\)。(\(s\)，\(t\)都是输入的数，\(S≤T\))
根据操作要求进行正确操作并输出结果。
解析
这个很明显是线段树/树状数组模板题吧，当然，我们是可以转换为二维偏序问题来解决的。
我们将给出的指令分为两类：查询指令和修改指令。可以这样思考：对于一个查询指令，其结果等价于计算原始数列和之后一系列修改对该位置的影响。那么我们把它转换为二维偏序问题：二元组\((a,b)\)代表在时刻\(a\)，位置\(b\)进行的指令，我们要知道所有时刻\(a\)以前，位置\(b\)以前修改指令对查询指令的影响，这就类似于正序对了。
重新定义分治函数\(solve(l,r)\)为计算时间\([l,r]\)中所有修改指令对查询指令的影响，和归并排序一样计算就可以了。
敲代码时候的一点小技巧：将区间和查询\([l,r]\)改为两个前缀和查询，其中一个为正影响，一个为负影响，这样就方便上述方法修改操作对查询操作影响的计算了。
\(Code:\)()
#includeusing namespace std;const int N=100020,M=150020;int n,m,cnt,tot;long long ans[M];struct order{ int flag,pos; long long val; bool operator < (const order &t)const { return pos == t.pos ? flag < t.flag : pos < t.pos; }}a[N+2*M],cur[N+2*M];inline void input(void){ scanf("%d",&n); for (int i=1;i<=n;i++) { long long val;scanf("%lld",&val); a[++cnt] = (order){1,i,val}; } scanf("%d",&m); for (int i=1;i<=m;i++) { char op[5];long long k1,k2; scanf("%s%lld%lld",op,&k1,&k2); if (op[0]=='A') a[++cnt] = (order){1,k1,k2}; if (op[0]=='S') a[++cnt] = (order){2,k2,++tot} , a[++cnt] = (order){3,k1-1,tot}; }}inline void cdq(int l,int r){ if ( l == r ) return; int mid = l+r >> 1 , p = l , q = mid+1 , t = l-1 , sum = 0; cdq(l,mid); cdq(mid+1,r); while ( p <= mid && q <= r ) { if ( a[p] < a[q] ) { if ( a[p].flag == 1 ) sum += a[p].val; cur[++t] = a[p++]; } else { if ( a[q].flag == 2 ) ans[ a[q].val ] += sum; if ( a[q].flag == 3 ) ans[ a[q].val ] -= sum; cur[++t] = a[q++]; } } while ( p <= mid ) cur[++t] = a[p++]; while ( q <= r ) { if ( a[q].flag == 2 ) ans[ a[q].val ] += sum; if ( a[q].flag == 3 ) ans[ a[q].val ] -= sum; cur[++t] = a[q++]; } for (int i=l;i<=r;i++) a[i] = cur[i];}int main(void){ input(); cdq(1,cnt); for (int i=1;i<=tot;i++) printf("%lld\n",ans[i]); return 0;}
三维偏序
二维偏序的问题同样有升级版，只不过换成了三元组而已。
同样地，我们先排序保证第一维的有序性，然后对第二维进行\(cdq\)分治，只不过在更新的时候出了点问题：满足前两维\(a,b\)有序是还需满足第三维\(c\)有序，那么我们在值域范围上建立一个树状数组，统计每个\(c\)值的出现次数，然后查询前缀和就可以了。
回顾二维偏序问题，如果不用\(cdq\)分治，树状数组也能直接解决，在这题中，如果不用\(cdq\)分治，可以用树状数组套平衡树做。其实，\(cdq\)分治的好处就在于顶替了一层数据结构，这样就可以大大减少代码量和时间常数。
\(Code:\)()
#includeusing namespace std;const int N=102000,K=220000;int n,k,ans[N],bucket[N];struct BIT{ int p[K]; inline int lowbit(int x){return x&(-x);} inline void insert(int pos,int val) { for (;pos<=k;pos+=lowbit(pos)) p[pos] += val; } inline int query(int pos) { int res = 0; for (;pos;pos-=lowbit(pos)) res += p[pos]; return res; } }tree;struct flower{int a,b,c,id;};flower f[N],cur[N];inline bool compare(flower p1,flower p2){ if ( p1.a ^ p2.a ) return p1.a < p2.a; if ( p1.b ^ p2.b ) return p1.b < p2.b; return p1.c < p2.c;}inline bool equal(flower p1,flower p2){ return p1.a == p2.a && p1.b == p2.b && p1.c == p2.c;}inline int read(void){ int x = 0 , w = 0; char ch=' '; while (!isdigit(ch)) w |= ch=='-' , ch = getchar(); while (isdigit(ch)) x = (x<<1) + (x<<3) + (ch^48) , ch = getchar(); return w ? -x : x; }inline void input(void){ n = read() , k = read(); for (register int i=1;i<=n;i++) f[i].a = read() , f[i].b = read() , f[i].c = read() , f[i].id = i;}inline void init(void){ flower t;int cnt = 1; for (register int i=n;i>=1;i--) if (equal(t,f[i])) ans[ f[i].id ] += cnt , cnt++; else t = f[i] , cnt = 1;}inline void cdq(int l,int r){ if ( l == r ) return; int mid = l+r >> 1 , p = l , q = mid+1 , t = l-1 ; cdq(l,mid); cdq(mid+1,r); while ( p <= mid && q <= r ) { if ( f[p].b <= f[q].b ) { tree.insert(f[p].c,1); cur[++t] = f[p++]; } if ( f[p].b > f[q].b ) { ans[ f[q].id ] += tree.query(f[q].c); cur[++t] = f[q++]; } } while ( q <= r ) ans[ f[q].id ] += tree.query(f[q].c) , cur[++t] = f[q++]; for (register int i=l;i
三维偏序问题的拓展
Describetion
有一个\(N*N\)矩阵，给出一系列的修改和询问，修改是这样的：将\((x,y)\)中的数字加上\(k\)，而询问是这样的：求\((x_1,y_1)\)到\((x_2,y_2)\)这个子矩阵内所有数字的和。
解析
这个和二维偏序问题的拓展相似，将区间求和推广为了矩阵求和。但是其本质还是一样的，我们将一根矩阵求和的询问拆为四个二维前缀和的查询。对于二维前缀和的查询和单点的修改，我们将其转换为三维偏序问题：三元组\((t,x,y)\)代表在时刻\(t\)，位置\((x,y)\)执行的指令，显然，当修改操作\((t',x',y')\)对操作操作\((t,x,y)\)有影响时，\(t'<t,x'\leq x,y'\leq y\)，这就是经典的三维偏序问题。
我们结合上文"数列求和","陌上花开"两题的思路，利用\(cdq\)分治和树状数组就可以轻松的实现本题了。
\(Code:\)()
#includeusing namespace std;const int N=2000020,M=800020;int n,m,cnt,tot,ans[M];struct BIT{ int p[N]; inline int lowbit(int x){return x&(-x);} inline void insert(int pos,int val) { for (;pos<=n;pos+=lowbit(pos)) p[pos] += val; } inline int query(int pos) { int res = 0; for (;pos;pos-=lowbit(pos)) res += p[pos]; return res; } }tree;struct order{ int flag,x,y,val; bool operator < (order p) { if ( x ^ p.x ) return x < p.x; if ( y ^ p.y ) return y < p.y; return flag < p.flag; }}a[M],cur[M];inline void input(void){ int op,x1,y1,x2,y2,val; scanf("%d",&n); while (true) { scanf("%d",&op); if ( op == 1 ) { scanf("%d%d%d",&x1,&y1,&val); a[++cnt] = (order){1,x1,y1,val}; } if ( op == 2 ) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); a[++cnt] = (order){2,x2,y2,++tot}; a[++cnt] = (order){2,x1-1,y1-1,tot}; a[++cnt] = (order){3,x1-1,y2,tot}; a[++cnt] = (order){3,x2,y1-1,tot}; } if ( op == 3 ) break; }}inline void cdq(int l,int r){ if ( l == r ) return; int mid = l+r >> 1 , p = l , q = mid+1 , t = l-1; cdq(l,mid); cdq(mid+1,r); while ( p <= mid && q <= r ) { if ( a[p] < a[q] ) { if ( a[p].flag == 1 ) tree.insert(a[p].y,a[p].val); cur[++t] = a[p++]; } else { if ( a[q].flag == 2 ) ans[ a[q].val ] += tree.query(a[q].y); if ( a[q].flag == 3 ) ans[ a[q].val ] -= tree.query(a[q].y); cur[++t] = a[q++]; } } while ( q <= r ) { if ( a[q].flag == 2 ) ans[ a[q].val ] += tree.query(a[q].y); if ( a[q].flag == 3 ) ans[ a[q].val ] -= tree.query(a[q].y); cur[++t] = a[q++]; } for (int i=l;i