<更新提示>
<第一次更新>
<第二次更新>更新了三维偏序问题的拓展
<正文>
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:)((HLOJ)炉石传说)
#include <bits/stdc++.h>
using 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
",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:)((HLOJ)数列求和)
#include <bits/stdc++.h>
using 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
",ans[i]);
return 0;
}
三维偏序
二维偏序的问题同样有升级版，只不过换成了三元组而已。
同样地，我们先排序保证第一维的有序性，然后对第二维进行(cdq)分治，只不过在更新的时候出了点问题：满足前两维(a,b)有序是还需满足第三维(c)有序，那么我们在值域范围上建立一个树状数组，统计每个(c)值的出现次数，然后查询前缀和就可以了。
回顾二维偏序问题，如果不用(cdq)分治，树状数组也能直接解决，在这题中，如果不用(cdq)分治，可以用树状数组套平衡树做。其实，(cdq)分治的好处就在于顶替了一层数据结构，这样就可以大大减少代码量和时间常数。
(Code:)((BZOJ)陌上花开)
#include <bits/stdc++.h>
using 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<p;i++) tree.insert(f[i].c,-1);
while ( p <= mid ) cur[++t] = f[p++];
for (register int i=l;i<=r;i++) f[i] = cur[i];
}
int main(void)
{
input();
sort( f+1 , f+n+1 , compare );
init();
cdq(1,n);
for (register int i=1;i<=n;i++)
bucket[ ans[i] ]++;
for (register int i=0;i<n;i++)
printf("%d
",bucket[i]);
return 0;
}
三维偏序问题的拓展
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:)((HLOJ)好朋友的题)
#include <bits/stdc++.h>
using 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<p;i++)
if ( a[i].flag == 1 )
tree.insert(a[i].y,-a[i].val);
while ( p <= mid ) cur[++t] = a[p++];
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("%d
",ans[i]);
return 0;
}
<后记>