Warning: session_start(): open(/tmp/sess_bfbce3c5b73b74f231c4d7c3f241c003, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== CDQ 分治 ======
===== 算法简介 =====
一种利用分治解决问题的算法思想，时间复杂度一般为 $O(n\log^2 n)$。
===== 算法例题 =====
==== 点对统计 ====
[[https://www.luogu.com.cn/problem/P3810|洛谷p3810]]
=== 题意 ===
三维空间中给定 $n$ 个点，编号为 $1 \sim n$。
定义 $f[i]$ 表示恰好有 $i$ 个元素满足 $x_i\le x_j,y_i\le y_j,z_i\le z_j$ 且 $i\ne j$ 的 $j$ 的个数。
要求输出 $f[0 \sim n-1]$。
=== 题解 1 ===
先考虑所有元素互异的情况。
先将第一维作为第一关键字，第二维作为第二关键字，第三维作为第三关键字对序列进行第一轮排序。
排序后将第二维作为关键字进行归并排序，利用分治过程计算答案贡献。
分治过程中受第一轮排序结果影响，只有左区间元素能为右区间元素做贡献，而右区间不能为左区间做贡献。
同时受第二轮排序结果影响，左区间和右区间元素的第二维单调不减，于是考虑用树状数组来维护左区间的第三维对右区间的贡献。
需要注意每轮分治完成后需要重置树状数组，考虑再次减去左区间贡献，不能暴力重置。
最后也可以发现，这样不会遗漏任何贡献。关于重复元素，最后特殊处理一下即可。时间复杂度 $O(n\log n\log v)$。
const int MAXN=1e5+5,MAXV=2e5+5;
struct Node{
int a,b,c;
bool operator < (const Node &y)const{
if(a!=y.a)return a>1;
cdq(lef,mid);cdq(mid+1,rig);
int pos1=lef,pos2=mid+1,pos3=lef;
while(pos1<=mid&&pos2<=rig){
if(node2[Id[pos1]].b<=node2[Id[pos2]].b){
add(node2[Id[pos1]].c,cnt[Id[pos1]]);
temp[pos3++]=Id[pos1++];
}
else{
ans[Id[pos2]]+=query(node2[Id[pos2]].c);
temp[pos3++]=Id[pos2++];
}
}
while(pos1<=mid){
add(node2[Id[pos1]].c,cnt[Id[pos1]]);
temp[pos3++]=Id[pos1++];
}
while(pos2<=rig){
ans[Id[pos2]]+=query(node2[Id[pos2]].c);
temp[pos3++]=Id[pos2++];
}
_rep(i,lef,mid)add(node2[Id[i]].c,-cnt[Id[i]]);
_rep(i,lef,rig)Id[i]=temp[i];
}
int f[MAXN];
int main()
{
n=read_int(),m=read_int();
_for(i,0,n)
node[i].a=read_int(),node[i].b=read_int(),node[i].c=read_int();
sort(node,node+n);
memcpy(node2,node,sizeof(node2));
int t=unique(node2,node2+n)-node2;
for(int i=0,j=0;i
=== 题解 2 ===
考虑两次嵌套 $\text{CDQ}$ 分治来解决上述问题。
第一轮排序同样将第一维作为第一关键字，第二维作为第二关键字，第三维作为第三关键字。
第二轮排序将第二维作为关键字进行归并排序，同时标记每个元素第一轮排序后属于左区间还是右区间。
第三轮排序嵌套于第二轮排序。第三轮排序的任务是计算第一轮排序后属于左区间的元素对右区间的贡献。
(注意下文的左右区间如果没有特指则是指第三轮归并排序过程中的左右区间，是属于第二轮归并排序过程中的子区间)
考虑将第三维作为关键字进行归并排序，并计算归并排序过程中左区间对右区间贡献。
经过第二轮排序序列按第二维单调不减，同时已经标记了每个元素第一轮排序后属于的区间类别。
于是第三轮归并排序过程中一定满足左区间元素第二维不大于右区间第二维。
根据归并排序过程又可以快速维护第三维不大于右区间某个元素的左区间集合。
于是左区间对右区间的贡献恰为第一轮排序后被标记属于左区间的元素的个数，这个可以通过前缀和维护。
而只有右区间元素属于第一轮排序后被标记为属于右区间的元素才接受贡献。
总时间复杂度 $O(n\log^2 n)$。理论上该方法适用于任意维偏序问题，每多一次嵌套时间复杂度增加 $O(\log n)$。
const int MAXN=1e5+5,MAXV=2e5+5;
struct Node{
int a,b,c,id;
bool lower;
bool operator < (const Node &y)const{
if(a!=y.a)return a>1;
cdq2(lef,mid);cdq2(mid+1,rig);
int pos1=lef,pos2=mid+1,pos3=lef,s=0;
while(pos1<=mid&&pos2<=rig){
if(temp[pos1].c<=temp[pos2].c){
if(temp[pos1].lower)s+=cnt[temp[pos1].id];
temp2[pos3++]=temp[pos1++];
}
else{
if(!temp[pos2].lower)ans[temp[pos2].id]+=s;
temp2[pos3++]=temp[pos2++];
}
}
while(pos1<=mid){
if(temp[pos1].lower)s+=cnt[temp[pos1].id];
temp2[pos3++]=temp[pos1++];
}
while(pos2<=rig){
if(!temp[pos2].lower)ans[temp[pos2].id]+=s;
temp2[pos3++]=temp[pos2++];
}
_rep(i,lef,rig)temp[i]=temp2[i];
}
void cdq1(int lef,int rig){
if(lef==rig)return;
int mid=lef+rig>>1;
cdq1(lef,mid);cdq1(mid+1,rig);
int pos1=lef,pos2=mid+1,pos3=lef;
while(pos1<=mid&&pos2<=rig){
if(node2[pos1].b<=node2[pos2].b)
node2[pos1].lower=true,temp[pos3++]=node2[pos1++];
else
node2[pos2].lower=false,temp[pos3++]=node2[pos2++];
}
while(pos1<=mid)node2[pos1].lower=true,temp[pos3++]=node2[pos1++];
while(pos2<=rig)node2[pos2].lower=false,temp[pos3++]=node2[pos2++];
_rep(i,lef,rig)node2[i]=temp[i];
cdq2(lef,rig);
}
int f[MAXN];
int main()
{
n=read_int(),m=read_int();
_for(i,0,n)
node[i].a=read_int(),node[i].b=read_int(),node[i].c=read_int();
sort(node,node+n);
memcpy(node2,node,sizeof(node2));
int t=unique(node2,node2+n)-node2;
for(int i=0,j=0;i
==== DP优化 ====
[[https://www.luogu.com.cn/problem/P2487|洛谷p2487]]
=== 题意 ===
给定一个序列，每个元素有两个属性 $x,y$，求最长不增子序列长度。定义 $a\ge b\iff a_x\ge b_x \land a_y\ge b_y$。
假定存在若干个最长二维不增子序列，系统将从中随机选择一个序列，问每个元素被选取的概率。
=== 题解 ===
先考虑 $O(n^2)$ 算法。
容易想到 $\text{dp}$ 出以每个元素为结尾和每个元素为开头的最长不增子序列长度和方案数。
由此可以得到题目所求最长不增子序列长度和相应的方案数。
对某个元素，如果以其结尾的最长不增子序列长度 $+$ 以其开头的最长不增子序列长度 $-1\lt$ 答案，则该元素被选中概率为 $0$。
否则，该元素被选中的方案数为以其结尾的最长不增子序列方案数 $\times$ 以其开头的最长不增子序列方案数。
用该元素被选中的方案数除以总方案数即可得到该元素被选择概率。
先考虑 $\text{dp}$ 求以每个元素结尾的最长不增子序列的过程，发现这也是个偏序问题，可以转化为考虑左区间对右区间的贡献。
接下来考虑中序遍历方式使用 $\text{CDQ}$ 分治，这样可以保证按顺序递推出每个 $\text{dp}$ 值。
对于以每个元素开头的最长不增子序列，考虑颠倒序列，再次使用 $\text{CDQ}$ 分治。
时间复杂度优化为 $O(n\log^2 n)$。
typedef pair pr;
const int MAXN=5e4+5;
const pr zero=make_pair(0,0.0);
struct Node{
int a,b,id;
}node[MAXN],temp[MAXN];
int n,m;
pr dp[2][MAXN],c[MAXN];
pr Merge(const pr &a,const pr &b){
if(a.first!=b.first)return a.first>b.first?a:b;
return make_pair(a.first,a.second+b.second);
}
#define lowbit(x) ((x)&(-x))
void add(int pos,pr v){
while(pos<=m){
c[pos]=Merge(c[pos],v);
pos+=lowbit(pos);
}
}
void del(int pos){
while(pos<=m){
c[pos]=zero;
pos+=lowbit(pos);
}
}
pr query(int pos){
pr ans=zero;
while(pos){
ans=Merge(ans,c[pos]);
pos-=lowbit(pos);
}
return make_pair(ans.first+1,ans.second);
}
bool cmp1(const Node &x,const Node &y){
return x.ay.a;
}
void cdq1(int lef,int rig){
if(lef==rig)return;
int mid=lef+rig>>1;
cdq1(lef,mid);
_rep(i,lef,rig)temp[i]=node[i];
sort(temp+lef,temp+mid+1,cmp2);sort(temp+mid+1,temp+rig+1,cmp2);
int pos1=lef,pos2=mid+1;
while(pos1<=mid&&pos2<=rig){
if(temp[pos1].a>=temp[pos2].a)add(temp[pos1].b,dp[0][temp[pos1].id]),pos1++;
else dp[0][temp[pos2].id]=Merge(dp[0][temp[pos2].id],query(temp[pos2].b)),pos2++;
}
while(pos1<=mid)add(temp[pos1].b,dp[0][temp[pos1].id]),pos1++;
while(pos2<=rig)dp[0][temp[pos2].id]=Merge(dp[0][temp[pos2].id],query(temp[pos2].b)),pos2++;
_rep(i,lef,mid)del(temp[i].b);
cdq1(mid+1,rig);
}
void cdq2(int lef,int rig){
if(lef==rig)return;
int mid=lef+rig>>1;
cdq2(lef,mid);
_rep(i,lef,rig)temp[i]=node[i];
sort(temp+lef,temp+mid+1,cmp1);sort(temp+mid+1,temp+rig+1,cmp1);
int pos1=lef,pos2=mid+1;
while(pos1<=mid&&pos2<=rig){
if(temp[pos1].a<=temp[pos2].a)add(temp[pos1].b,dp[1][temp[pos1].id]),pos1++;
else dp[1][temp[pos2].id]=Merge(dp[1][temp[pos2].id],query(temp[pos2].b)),pos2++;
}
while(pos1<=mid)add(temp[pos1].b,dp[1][temp[pos1].id]),pos1++;
while(pos2<=rig)dp[1][temp[pos2].id]=Merge(dp[1][temp[pos2].id],query(temp[pos2].b)),pos2++;
_rep(i,lef,mid)del(temp[i].b);
cdq2(mid+1,rig);
}
int a[MAXN],b[MAXN];
int main()
{
n=read_int();
_for(i,0,n){
node[i].a=read_int(),node[i].b=read_int(),node[i].id=i;
a[i]=node[i].a,b[i]=node[i].b;
}
sort(a,a+n);sort(b,b+n);
int t1=unique(a,a+n)-a,t2=unique(b,b+n)-b;
_for(i,0,n)
node[i].a=upper_bound(a,a+t1,node[i].a)-a,node[i].b=upper_bound(b,b+t2,node[i].b)-b;
m=max(t1,t2)+1;
_for(i,0,n)dp[0][i]=dp[1][i]=make_pair(1,1.0);
_for(i,0,n)node[i].b=m-node[i].b;
cdq1(0,n-1);
for(int l=0,r=n-1;l
===== 算法练习 =====
==== 习题一 ====
[[https://www.luogu.com.cn/problem/P3157|洛谷p3157]]
=== 题意 ===
给定一个 $1\sim n$ 的排列，依次删除 $m$ 个元素，要求输出每次删除前序列中的逆序对数。
=== 题解 ===
考虑第一维为位置，第二维为权值，第三维为时间，$\text{CDQ}$ 分治维护即可。
需要注意左区间可以对右区间贡献，右区间也可以对左区间贡献，考虑在分治过程中同时维护。
const int MAXN=1e5+5,MAXV=5e4+5;
struct Node{
int a,b,id;
}node[MAXN],temp[MAXN];
int n,m,c[MAXN],ans[MAXN];
#define lowbit(x) (x)&(-x)
struct BIT{
int c[MAXV];
void add(int pos,int v){
while(pos<=m){
c[pos]+=v;
pos+=lowbit(pos);
}
}
int query(int pos){
int ans=0;
while(pos){
ans+=c[pos];
pos-=lowbit(pos);
}
return ans;
}
}tree1,tree2;
void cdq(int lef,int rig){
if(lef==rig)return;
int mid=lef+rig>>1;
cdq(lef,mid);cdq(mid+1,rig);
int pos1=lef,pos2=mid+1,pos3=lef;
while(pos1<=mid&&pos2<=rig){
if(node[pos1].a<=node[pos2].a){
tree1.add(node[pos1].b,1);
temp[pos3++]=node[pos1++];
}
else{
ans[node[pos2].id]+=tree1.query(node[pos2].b);
temp[pos3++]=node[pos2++];
}
}
while(pos1<=mid){
tree1.add(node[pos1].b,1);
temp[pos3++]=node[pos1++];
}
while(pos2<=rig){
ans[node[pos2].id]+=tree1.query(node[pos2].b);
temp[pos3++]=node[pos2++];
}
_rep(i,lef,mid)tree1.add(node[i].b,-1);
pos1=mid,pos2=rig;
while(pos1>=lef&&pos2>mid){
if(node[pos2].a>=node[pos1].a)tree2.add(node[pos2].b,1),pos2--;
else ans[node[pos1].id]+=tree2.query(node[pos1].b),pos1--;
}
while(pos2>mid)tree2.add(node[pos2].b,1),pos2--;
while(pos1>=lef)ans[node[pos1].id]+=tree2.query(node[pos1].b),pos1--;
_rep(i,mid+1,rig)tree2.add(node[i].b,-1);
_rep(i,lef,rig)node[i]=temp[i];
}
int pos[MAXN],t;
int main()
{
n=read_int(),m=read_int();
for(int i=n;i;i--)
node[i].a=read_int(),pos[node[i].a]=i;
LL sum=0;
_rep(i,1,n){
int k=node[i].a;
while(k)sum+=c[k],k-=lowbit(k);
k=node[i].a;
while(k<=n)c[k]++,k+=lowbit(k);
}
for(int i=m;i;i--){
t=read_int();
node[pos[t]].b=i,node[pos[t]].id=m+1-i;
}
_rep(i,1,n)node[i].b++;
m++;
cdq(1,n);
_for(i,1,m){
enter(sum);
sum-=ans[i];
}
return 0;
}
==== 习题二 ====
[[https://www.luogu.com.cn/problem/P4169|洛谷p4169]]
=== 题意 ===
二维空间，一开始 $n$ 个点， $m$ 个操作。
操作一：加入点 $(x,y)$。
操作二：询问当前点集中到给定点 $(x,y)$ 的最小哈密顿距离。
=== 题解 ===
将时间作为第一维，$x$ 坐标作为第二维，$y$ 坐标作为第三维，将插入的点和初始点记为第一类点，查询的点记为第二类点。
对每个第二类点 $(u_t,u_x,u_y)$，先考虑所有满足 $v_t\lt u_t,v_x\le u_x,v_y\le u_y$ 的第一类点。
显然这些点对答案的贡献为 $u_x+u_y-\max(v_x+v_y)$，问题转化为三维偏序问题，考虑使用树状数组维护。
而对于其他的第一类点，可以将坐标系分别翻转 $3$ 次，转化为上述情况。
另外发现一开始 $n$ 个第一类点一定满足 $v_t\lt u_t$，考虑单独处理优化算法效率。
时间复杂度 $O(4(n\log n+m\log m\log v))$。
const int MAXN=6e5+5,MAXV=1e6+5,Inf=1e9;
struct Node{
int a,b;bool flag;
bool operator < (const Node &y)const{
if(a!=y.a)return a>1;
cdq(lef,mid);cdq(mid+1,rig);
int pos1=lef,pos2=mid+1,pos3=lef;
while(pos1<=mid&&pos2<=rig){
if(node2[Id[pos1]].a<=node2[Id[pos2]].a){
if(node2[Id[pos1]].flag)add(node2[Id[pos1]].b,node2[Id[pos1]].a+node2[Id[pos1]].b);
temp[pos3++]=Id[pos1++];
}
else{
if(!node2[Id[pos2]].flag)ans[Id[pos2]]=max(ans[Id[pos2]],query(node2[Id[pos2]].b));
temp[pos3++]=Id[pos2++];
}
}
while(pos1<=mid){
if(node2[Id[pos1]].flag)add(node2[Id[pos1]].b,node2[Id[pos1]].a+node2[Id[pos1]].b);
temp[pos3++]=Id[pos1++];
}
while(pos2<=rig){
if(!node2[Id[pos2]].flag)ans[Id[pos2]]=max(ans[Id[pos2]],query(node2[Id[pos2]].b));
temp[pos3++]=Id[pos2++];
}
_rep(i,lef,mid)if(node2[Id[i]].flag)del(node2[Id[i]].b);
_rep(i,lef,rig)Id[i]=temp[i];
}
int f[MAXN];
void cal(int mid,int rig){
int pos1=0,pos2=mid+1;
sort(node2,node2+mid+1);
while(pos1<=mid&&pos2<=rig){
if(node2[pos1].a<=node2[Id[pos2]].a)
add(node2[pos1].b,node2[pos1].a+node2[pos1].b),pos1++;
else{
if(!node2[Id[pos2]].flag)ans[Id[pos2]]=max(ans[Id[pos2]],query(node2[Id[pos2]].b));
pos2++;
}
}
while(pos1<=mid)add(node2[pos1].b,node2[pos1].a+node2[pos1].b),pos1++;
while(pos2<=rig){
if(!node2[Id[pos2]].flag)ans[Id[pos2]]=max(ans[Id[pos2]],query(node2[Id[pos2]].b));
pos2++;
}
_rep(i,0,mid)del(node2[i].b);
_rep(i,0,rig){
if(ans[i])f[i]=min(f[i],node2[i].a+node2[i].b-ans[i]);
node2[i]=node[i],Id[i]=i,ans[i]=0;
}
}
int main()
{
int n=read_int(),nn=read_int()+n;
m=0;
_for(i,0,n){
node2[i].a=read_int()+1,node2[i].b=read_int()+1;
m=max(m,max(node2[i].a,node2[i].b));
}
_for(i,n,nn){
node2[i].flag=read_int()&1,node2[i].a=read_int()+1,node2[i].b=read_int()+1;
Id[i]=i,ans[i]=0,f[i]=Inf;
m=max(m,max(node2[i].a,node2[i].b));
}
m++;
_for(i,0,nn)node[i]=node2[i];
cdq(n,nn-1);cal(n-1,nn-1);
_for(i,0,nn)node2[i].a=m-node2[i].a;
cdq(n,nn-1);cal(n-1,nn-1);
_for(i,0,nn)node2[i].b=m-node2[i].b;
cdq(n,nn-1);cal(n-1,nn-1);
_for(i,0,nn)node2[i].a=m-node2[i].a,node2[i].b=m-node2[i].b;
cdq(n,nn-1);cal(n-1,nn-1);
_for(i,n,nn)if(f[i]!=Inf)enter(f[i]);
return 0;
}
==== 习题三 ====
[[https://www.luogu.com.cn/problem/P4093|洛谷p4093]]
=== 题意 ===
给定一个长度为 $n$ 的序列以及 $m$ 个变换。
每个变化可以将位置 $x$ 的数变成 $y$，求最长不降子序列，且该子序列满足最多一次变换下仍为不降子序列。
=== 题解 ===
考虑状态转移方程，记 $dp_i$ 表示以位置 $i$ 的数结尾的满足上述条件的最长子序列，$l_i$ 为位置 $i$ 的最小可能值，$r_i$ 为位置 $i$ 的最大可能值。
于是有 $dp_i=\max(dp_j+1)(j\lt i,r_j\le a_i,a_j\le l_i)$，$\text{CDQ}$ 分治即可。
const int MAXN=1e5+5;
struct Node{
int a,l,r,id;
}node[MAXN],temp[MAXN];
int mv,dp[MAXN],c[MAXN];
#define lowbit(x) ((x)&(-x))
void add(int pos,int v){
while(pos<=mv){
c[pos]=max(c[pos],v);
pos+=lowbit(pos);
}
}
void del(int pos){
while(pos<=mv){
c[pos]=0;
pos+=lowbit(pos);
}
}
int query(int pos){
int ans=0;
while(pos){
ans=max(ans,c[pos]);
pos-=lowbit(pos);
}
return ans;
}
bool cmp1(const Node &x,const Node &y){
return x.r>1;
cdq(lef,mid);
_rep(i,lef,rig)temp[i]=node[i];
sort(temp+lef,temp+mid+1,cmp1);sort(temp+mid+1,temp+rig+1,cmp2);
int pos1=lef,pos2=mid+1;
while(pos1<=mid&&pos2<=rig){
if(temp[pos1].r<=temp[pos2].a)add(temp[pos1].a,dp[temp[pos1].id]),pos1++;
else dp[temp[pos2].id]=max(dp[temp[pos2].id],query(temp[pos2].l)+1),pos2++;
}
while(pos1<=mid)add(temp[pos1].a,dp[temp[pos1].id]),pos1++;
while(pos2<=rig)dp[temp[pos2].id]=max(dp[temp[pos2].id],query(temp[pos2].l)+1),pos2++;
_rep(i,lef,mid)del(temp[i].a);
cdq(mid+1,rig);
}
int main()
{
int n=read_int(),m=read_int(),x,y;
_rep(i,1,n)
node[i].a=node[i].l=node[i].r=read_int(),node[i].id=i,dp[i]=1;
while(m--){
x=read_int(),y=read_int();
node[x].l=min(node[x].l,y);
node[x].r=max(node[x].r,y);
}
_rep(i,1,n)
mv=max(mv,node[i].r);
cdq(1,n);
int ans=0;
_rep(i,1,n)
ans=max(dp[i],ans);
enter(ans);
return 0;
}