CDQ分治
YY大爷讲归并的时候讲到了这个算法，可是蒟蒻的我连归并都不太会呢
CDQ分治似乎就是在离线且修改操作互不影响的情况下可以使用的一种方法，步骤为
1.当递归到底时，直接处理答案，然后返回
2.递归解决[l,mid]
3.处理[l,mid]对[mid + 1,r]的影响
4.递归解决[mid + 1,r]
5.将[l,mid]和[mid + 1,r]进行归并排序，为下一次处理区间之间的影响做准备
NOI2007货币兑换：当初平衡树写疯了都没有写出来，换成CDQ分治也是模板抄抄，毕竟蒟蒻不会归并，不太会凸包和分治
#include<cstdio>
#include<algorithm>
#include<cmath>
#define eps 1e-9
#define N 11111
using namespace std;
int n,i,top,stack[N];
double f[N];
struct EG{double x,y,a,b,k,rate;int id;}p[N],t[N];
bool cmp(EG x,EG y){return x.k>y.k;}
double getk(int a,int b){
if(!b)return -1e20;
if(fabs(p[a].x-p[b].x)<eps)return 1e20;
return (p[b].y-p[a].y)/(p[b].x-p[a].x);
}
void solve(int l,int r){
if(l==r){//分治到底了显然我们可以直接计算出结果
f[l]=max(f[l],f[l-1]);
p[l].y=f[l]/(p[l].a*p[l].rate+p[l].b);
p[l].x=p[l].rate*p[l].y;
return;
}
int l1=l,mid=(l+r)>>1,l2=mid+1,j=1;
for(int i=l;i<=r;i++)//将一块原顺序分为左右两块
if(p[i].id<=mid)t[l1++]=p[i];else t[l2++]=p[i];
for(int i=l;i<=r;i++)p[i]=t[i];
solve(l,mid);//递归左边
top=0;
for(int i=l;i<=mid;i++){//左边维护一个凸包
while(top>1&&getk(stack[top-1],stack[top])<getk(stack[top-1],i)+eps)top--;
stack[++top]=i;
}
stack[++top]=0;
for(int i=mid+1;i<=r;i++){
while(j<top&&getk(stack[j],stack[j+1])+eps>p[i].k)j++;//用左边的点作为决策更新右边
f[p[i].id]=max(f[p[i].id],p[stack[j]].x*p[i].a+p[stack[j]].y*p[i].b);
}
solve(mid+1,r);//递归右边
l1=l;l2=mid+1;
for(int i=l;i<=r;i++)
if(((p[l1].x<p[l2].x||(fabs(p[l1].x-p[l2].x)<eps&&p[l1].y<p[l2].y))||l2>r)&&l1<=mid)t[i]=p[l1++];else t[i]=p[l2++];
for(int i=l;i<=r;i++)p[i]=t[i];//归并
}
int main(){
scanf("%d%lf",&n,&f[0]);
for(i=1;i<=n;i++){
scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate);
p[i].k=-p[i].a/p[i].b;p[i].id=i;
}
sort(p+1,p+n+1,cmp);//这里按照斜率进行排序，保证分治的每一块斜率是有序的
solve(1,n);
printf("%.3lf",f[n]);
}
BZOJ1176：想当初这道题还不是权限题，和YY大爷一起写暴力，一起愉快地T了
#include<cstdio>
#include<algorithm>
using namespace std;
int s,w,p,m,i,pos,x1,y1,x2,y2,ans[22222],c[2222222];
struct EG{int x,y,id,opt,val,pos;}q[222222],t[222222];
bool cmp(EG a,EG b){return a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.opt<b.opt);}
void add(int x,int z){for(;x<=w;x+=x&-x)c[x]+=z;}
int query(int x){int tmp=0;for(;x;x-=x&-x)tmp+=c[x];return tmp;}
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)>>1,l1=l,l2=mid+1;
for(int i=l;i<=r;i++){
if(q[i].id<=mid&&!q[i].opt)add(q[i].y,q[i].val);
if(q[i].id>mid&&q[i].opt)ans[q[i].pos]+=q[i].val*query(q[i].y);
}
for(int i=l;i<=r;i++)if(q[i].id<=mid&&!q[i].opt)add(q[i].y,-q[i].val);
for(int i=l;i<=r;i++)if(q[i].id<=mid)t[l1++]=q[i];else t[l2++]=q[i];
for(int i=l;i<=r;i++)q[i]=t[i];
cdq(l,mid);cdq(mid+1,r);
}
int main(){
scanf("%d%d",&s,&w);
while(1){
scanf("%d",&p);
if(p==1){
m++;
scanf("%d%d%d",&q[m].x,&q[m].y,&q[m].val);
q[m].id=m;
}else if(p==2){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
pos=++ans[0];
q[++m].pos=pos;q[m].id=m;q[m].x=x1-1;q[m].y=y1-1;q[m].val=1;q[m].opt=1;
q[++m].pos=pos;q[m].id=m;q[m].x=x2;q[m].y=y2;q[m].val=1;q[m].opt=1;
q[++m].pos=pos;q[m].id=m;q[m].x=x1-1;q[m].y=y2;q[m].val=-1;q[m].opt=1;
q[++m].pos=pos;q[m].id=m;q[m].x=x2;q[m].y=y1-1;q[m].val=-1;q[m].opt=1;
}else break;
}
sort(q+1,q+m+1,cmp);
cdq(1,m);
for(i=1;i<=ans[0];i++)printf("%d\n",ans[i]);
}
三维最长偏序，也就是二维LIS，这个在多校时候不会被坑了。。今天学了一下，就是利用CDQ分治+树状数组解决。。
BZOJ3262，三维最长偏序裸题
#include<cstdio>
#include<algorithm>
#define N 200005
using namespace std;
int n,i,k,cnt,w,c[N],ans[N];
struct EG{int x,y,z,v,ans;}eg[N],p[N];
bool cmp(EG a,EG b){return a.x<b.x||a.x==b.x&&a.y<b.y||a.x==b.x&&a.y==b.y&&a.z<b.z;}
bool cmp2(EG a,EG b){return a.y<b.y||a.y==b.y&&a.z<b.z;}
void add(int x,int y){for(;x<=k;x+=x&-x)c[x]+=y;}
int query(int x){int sum=0;for(;x;x-=x&-x)sum+=c[x];return sum;}
void solve(int l,int r){
if(l==r){p[l].ans=p[l].v;return;}
int mid=(l+r)>>1,i=l,j=mid+1;
solve(l,mid);solve(mid+1,r);
sort(p+l,p+mid+1,cmp2);sort(p+mid+1,p+r+1,cmp2);
for(;j<=r;j++){
for(;i<=mid&&p[i].y<=p[j].y;i++)add(p[i].z,p[i].v);
p[j].ans+=query(p[j].z);
}
for(j=l;j<i;j++)add(p[j].z,-p[j].v);
}
int main(){
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)scanf("%d%d%d",&eg[i].x,&eg[i].y,&eg[i].z);
sort(eg+1,eg+n+1,cmp);
for(i=1,w=1;i<=n;i++,w++)
if(eg[i].x!=eg[i+1].x||eg[i].y!=eg[i+1].y||eg[i].z!=eg[i+1].z)
p[++cnt]=eg[i],p[cnt].v=w,w=0;
solve(1,cnt);
for(i=1;i<=cnt;i++)ans[p[i].ans]+=p[i].v;
for(i=1;i<=n;i++)printf("%d\n",ans[i]);
}
BZOJ2244 裸三维偏序，做两遍实数记录答案
#include<bits/stdc++.h>
#define N 50050
using namespace std;int n,i,cy,cz,ans,vy[N],vz[N],c[N];double e[N],S;
struct P{int x,y,z,f[2];double g[2];}p[N];bool cmp(P a,P b){return a.y>b.y||a.y==b.y&&a.z>b.z;}bool c2(P a,P b){return a.x<b.x;}
void add(int x,int z,double w){for(;x;x-=x&-x)if(z>c[x])c[x]=z,e[x]=w;else if(z==c[x])e[x]+=w;}
void qu(int x,int &z,double &w){for(;x<=cz;x+=x&-x)if(e[x])if(c[x]+1>z)z=c[x]+1,w=e[x];else if(c[x]+1==z)w+=e[x];}
void cl(int x){for(;x;x-=x&-x)c[x]=0,e[x]=0;}
void cdq(int l,int r,int o){
if(l==r){if(p[l].f[o]<1)p[l].f[o]=1,p[l].g[o]=1;return;}
int mid=l+r>>1,i=l,j=mid+1;cdq(l,mid,o);sort(p+l,p+mid+1,cmp);sort(p+mid+1,p+r+1,cmp);
for(;j<=r;qu(p[j].z,p[j].f[o],p[j].g[o]),j++)for(;i<=mid&&p[i].y>=p[j].y;i++)add(p[i].z,p[i].f[o],p[i].g[o]);
for(i=l;i<=mid;i++)cl(p[i].z);sort(p+mid+1,p+r+1,c2);cdq(mid+1,r,o);
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&p[i].y,&p[i].z),vy[i]=p[i].y,vz[i]=p[i].z,p[i].x=i;
sort(vy+1,vy+n+1);sort(vz+1,vz+n+1);cy=unique(vy+1,vy+n+1)-vy-1;cz=unique(vz+1,vz+n+1)-vz-1;
for(i=1;i<=n;i++)p[i].y=lower_bound(vy+1,vy+cy+1,p[i].y)-vy,p[i].z=lower_bound(vz+1,vz+cz+1,p[i].z)-vz;
for(cdq(1,n,0),i=1;i<=n;i++)if(p[i].f[0]>ans)ans=p[i].f[0],S=p[i].g[0];else if(p[i].f[0]==ans)S+=p[i].g[0];
for(sort(p+1,p+n+1,c2),i=1;i<=n;i++)p[i].x=n-p[i].x+1,p[i].y=cy-p[i].y+1,p[i].z=cz-p[i].z+1;
reverse(p+1,p+n+1);sort(p+1,p+n+1,c2);cdq(1,n,1);reverse(p+1,p+n+1);printf("%d\n",ans);sort(p+1,p+n+1,c2);
for(i=n;i;i--)if(p[i].f[0]+p[i].f[1]-1<ans)printf("0.00000 ");else printf("%.5lf ",p[i].g[0]*p[i].g[1]/S);
}
四维偏序大概就是进行两次CDQ分治，大概看懂了，大致步骤是
solve2(l,r){
solve2(l,mid);solve2(mid+1,r);
树状数组处理l~mid对mid+1~r的影响
}
solve1(l,r){
solve1(l,mid);solve1(mid+1,r);
solve2((l~mid)的修改和(mid+1~r)的询问）;
}
总复杂度O(nlg^3n)
BZOJ2527 按时间分治
#include<cstdio>
#define inf 1e9
#define N 333333
typedef long long LL;
int n,m,i,x,k,tot,la[N],ne[N],fir[N],e[N],id[N],L[N],R[N],a[N],ans[N],q1[N],q2[N];
LL sum,cur[N],now[N],c[N];
void add(int x,int z){for(;x<=m;x+=x&-x)c[x]+=z;}
LL que(int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
void get(int x,int y,int z){add(x,z);add(y+1,-z);}
void solve(int l,int r,int h,int t){
if(l==r){for(int i=h;i<=t;i++)ans[id[i]]=l;return;}
int i,j,w,mid=(l+r)>>1,ln=0,rn=0;
for(i=l;i<=mid;i++)if(L[i]<=R[i])get(L[i],R[i],a[i]);else get(L[i],m,a[i]),get(1,R[i],a[i]);
for(i=h;i<=t;i++){
cur[w=id[i]]=0;
for(j=fir[w];j;j=ne[j]){
cur[w]+=que(la[j]);
if(cur[w]+now[w]>e[w])break;
}
if(cur[w]+now[w]>=e[w])q1[++ln]=w;else q2[++rn]=w,now[w]+=cur[w];
}
for(i=l;i<=mid;i++)if(L[i]<=R[i])get(L[i],R[i],-a[i]);else get(L[i],m,-a[i]),get(1,R[i],-a[i]);
for(i=1;i<=ln;i++)id[h+i-1]=q1[i];
for(i=1;i<=rn;i++)id[h+i+ln-1]=q2[i];
solve(l,mid,h,h+ln-1);solve(mid+1,r,h+ln,t);
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)scanf("%d",&x),la[++tot]=i,ne[tot]=fir[x],fir[x]=tot;
for(i=1;i<=n;i++)scanf("%d",&e[i]),id[i]=i;
scanf("%d",&k);
for(i=1;i<=k;i++)scanf("%d%d%d",&L[i],&R[i],&a[i]);
k++;L[i]=1;R[i]=m;a[i]=inf;
solve(1,k,1,n);
for(i=1;i<=n;i++)ans[i]==k?puts("NIE"):printf("%d\n",ans[i]);
}
BZOJ2001 完全动态MST
论文题，每次对于一个分治结构找出必须选的边和肯定不选的边，继续分治时不考虑它们，这样就可以快速得到答案了。
#include<bits/stdc++.h>
#define N 50005
#define inf 1e9
using namespace std;typedef long long LL;
int n,m,Q,i,w,o,u,v[N],to[N],F[N],R[N],nb[22];LL ans[N];
struct P{int x,y,z,id;}e[22][N],p[N],q[N];bool cmp(P a,P b){return a.z<b.z;}
int gf(int x){return F[x]==x?x:F[x]=gf(F[x]);}
void cdq(int d,int l,int r,LL z){
int i,m=nb[d],mid=l+r>>1;if(l==r)v[q[l].x]=q[l].y;
for(i=1;i<=m;i++)e[d][i].z=v[e[d][i].id],p[i]=e[d][i],to[p[i].id]=i,F[p[i].x]=p[i].x,F[p[i].y]=p[i].y;
if(l==r){
for(sort(p+1,p+m+1,cmp),i=1;i<=m;i++){
o=gf(p[i].x);u=gf(p[i].y);
if(o!=u)F[o]=u,z+=p[i].z;
}
ans[l]=z;return;
}
for(i=l;i<=r;i++)p[to[q[i].x]].z=-inf;
for(sort(p+1,p+m+1,cmp),w=0,i=1;i<=m;i++){
o=gf(p[i].x);u=gf(p[i].y);
if(o!=u)F[o]=u,R[++w]=i;
}
for(i=1;i<=m;i++)F[p[i].x]=p[i].x,F[p[i].y]=p[i].y;
for(i=1;i<=w;i++)if(p[R[i]].z!=-inf)z+=p[R[i]].z,F[gf(p[R[i]].x)]=gf(p[R[i]].y);
for(nb[d+1]=0,i=1;i<=m;i++){
p[i].x=gf(p[i].x);p[i].y=gf(p[i].y);
if(p[i].z==-inf)p[i].z=inf,e[d+1][++nb[d+1]]=p[i];
}
for(sort(p+1,p+m+1,cmp),i=1;i<=m;i++){
o=gf(p[i].x);u=gf(p[i].y);
if(o!=u){
F[o]=u;
if(p[i].z!=inf)e[d+1][++nb[d+1]]=p[i];
}
}
cdq(d+1,l,mid,z);cdq(d+1,mid+1,r,z);
}
int main(){
for(scanf("%d%d%d",&n,&m,&Q),i=1;i<=m;i++)scanf("%d%d%d",&e[0][i].x,&e[0][i].y,&v[i]),e[0][i].id=i,e[0][i].z=v[i];
for(nb[0]=m,i=1;i<=Q;i++)scanf("%d%d",&q[i].x,&q[i].y);
for(cdq(0,1,Q,0),i=1;i<=Q;i++)printf("%lld\n",ans[i]);
}
BZOJ3461
考虑一次的情况，分两种情况讨论：
①把[j+1,i]改为b[i]，那么f[i]=max(S[k]+b[i]*(i-k))，S[j]-b[i]*j>S[k]-b[i]*k，S[j]-S[k]>b[i]*(j-k)，除b[i]外都单调递增，单调维护凸包在上面三分得到答案，时间复杂度O(nlgn)。
②将[j+1,i]改为b[j]，那么f[i]=max(S[j]+b[j+1]*(i-j))=(b[j+1]*i+S[j]-b[j+1]*j)
b[j+1]*i+S[j]-b[j+1]*j>b[k+1]*i+S[k]-b[k+1]*k，-b[j+1]*j+S[j]+b[k+1]*k-S[k]>i*(-b[j+1]+b[k+1])，-c[j]*j+S[j]+c[k]*k-S[k]>i*(-c[j]+c[k])。分治后按c排序维护出凸包，然后在凸包上扫一遍得到答案，时间复杂度O(nlg^2n)。可以利用归并做到O(nlgn)。
翻转a和b得到右边的答案，ans=max(L[i]+R[j]+S[j-1]-S[i])=max(R[j]+S[j-1]+max(L[i]-S[i]))，维护前缀和得到答案。
#include<bits/stdc++.h>
#define N 500100
using namespace std;typedef double DB;int n,i,j,h,t,w,a[N],b[N],c[N],p[N],q[N];long long AN,o,S[N],f[N],g[N],d[N],L[N];
DB xl(int j,int k){return (DB)(S[j]-S[k])/(j-k);}
bool cmp(int x,int y){return c[x]==c[y]?d[x]>d[y]:c[x]<c[y];}
DB sl(int x,int y){return (DB)(d[x]-d[y])/(DB)(c[y]-c[x]);}
long long ask(int x){
int l=1,r=t-1,o=t,md;
for(;l<=r;)if(md=l+r>>1,(DB)x>xl(q[md],q[md+1]))r=(o=md)-1;else l=md+1;
return S[q[o]]-1ll*q[o]*x;
}
void cdq(int l,int r){
if(l==r)return;int md=l+r>>1;cdq(l,md);cdq(md+1,r);
for(w=0,i=l;i<=md;i++)p[++w]=i;
for(sort(p+1,p+w+1,cmp),t=0,i=h=1;i<=w;q[++t]=p[i++])for(;t>1&&sl(q[t-1],q[t])>=sl(q[t],p[i]);t--);
for(i=md+1;i<=r;f[i]=max(f[i],1ll*i*c[q[h]]+d[q[h]]),i++)for(;h<t&&d[q[h]]-d[q[h+1]]<=1ll*i*(c[q[h+1]]-c[q[h]]);h++);
}
void G(){
for(i=1;i<=n;i++)S[i]=S[i-1]+a[i];
for(q[h=t=i=1]=0;i<=n;q[++t]=i++)for(f[i]=1ll*b[i]*i+ask(b[i]);h<t&&xl(q[t-1],q[t])<xl(q[t],i);)t--;
for(i=0;i<n;i++)c[i]=b[i+1],d[i]=-1ll*c[i]*i+S[i];cdq(0,n);
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)scanf("%d",&b[i]);
G();memcpy(L,f,sizeof f);reverse(a+1,a+n+1);reverse(b+1,b+n+1);G();reverse(f+1,f+n+1);
for(i=1;i<=n;i++)S[i]=S[i-1]+a[n-i+1];
for(AN=S[n],i=1;i<=n;i++)AN=max(AN,f[i]+S[i-1]+o),o=max(o,L[i]-S[i]);
printf("%lld",AN);
}
评论 (0)
