CDQ分治 的一些题目
LG3810 【模板】三维偏序（陌上花开）
https://www.luogu.com.cn/problem/P3810
本来就是很模板的题了，什么时候把题解补上，具体见代码
#include
#include
#include
#include
using namespace std;
const int N=100005;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||'9'>1,i=l,j=mid+1;
CDQ(l,mid);CDQ(mid+1,r);
sort(a+l,a+mid+1,cmpy);
sort(a+mid+1,a+r+1,cmpy);
for(;j<=r;++j){//利用双指针,满足y的情况
while(a[i].y<=a[j].y&&i<=mid)
update(a[i].z,a[i].num),++i;
a[j].ans+=getsum(a[j].z);//利用树状数组统计z满足的数的数量
}
for(int loc=l;loc LG4169 [Violet]天使玩偶/SJY摆棋子
https://www.luogu.com.cn/problem/P4169
需要见距离公式变形。如果要满足一个CDQ的性质，就需要将坐标轴旋转四个 \(90^{\circ}\) 求四次答案。
然后因为每次 cdq 完顺序会被打乱，如果重新按时间 \(O(n\log n)\) 排序，不如每次存入一个临时数组，然后 \(O(n)\) 直接复制过去。
#include
#include
#include
using namespace std;
const int N=600005,R=10000007;//大概之前INF太大导致炸了
struct node{int x,y,opt,id,ans;}ori[N],a[N],tmp[N];
int n,m,rev;
struct BIT{
int c[R];
inline int lowbit(int x){return x&-x;}
inline void update(int i,int v){for(;i<=rev;i+=lowbit(i))c[i]=max(c[i],v);}
inline int getmax(int i,int ans=0){
for(;i;i-=lowbit(i))ans=max(ans,c[i]);
return ans?ans:-R;//特判为0,给-R是为了减去得到+R
}
inline void clear(int i){for(;c[i];i+=lowbit(i))c[i]=0;}
}t;
void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)>>1,j=l,p1=l;
cdq(l,mid);cdq(mid+1,r);
for(int i=mid+1;i<=r;++i){
while(j<=mid&&a[j].x<=a[i].x){
if(a[j].opt==1)t.update(a[j].y,a[j].x+a[j].y);//详见距离计算公式
tmp[p1++]=a[j++];
}
if(a[i].opt==2)
ori[a[i].id].ans=min(ori[a[i].id].ans,a[i].x+a[i].y-t.getmax(a[i].y));
tmp[p1++]=a[i];
}
for(int i=l;i LG3157 [CQOI2011]动态逆序对
https://www.luogu.com.cn/problem/P3157
转化一下就是典型的三维偏序
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=100005;
struct node{int opt,val,loc,id,tim;}opt[N<<1];
bool cmp(node x,node y){return x.loc>1,j=l;
cdq(l,mid);cdq(mid+1,r);
sort(opt+l,opt+mid+1,cmp);
sort(opt+mid+1,opt+r+1,cmp);
for(int i=mid+1;i<=r;++i){
while(j<=mid&&opt[j].loc<=opt[i].loc)
update(opt[j].val,opt[j].opt),++j;
ans[opt[i].id]+=opt[i].opt*(getsum(n)-getsum(opt[i].val));
}
for(int i=l;imid;--i){
while(j>=l&&opt[j].loc>=opt[i].loc)
update(opt[j].val,opt[j].opt),--j;
ans[opt[i].id]+=opt[i].opt*getsum(opt[i].val-1);
}
for(int i=mid;i>j;--i)update(opt[i].val,-opt[i].opt);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
pos[a[i]]=i;
opt[++tot]=(node){1,a[i],i,0,tot};
}
for(int i=1;i<=m;++i){
int x;scanf("%d",&x);
opt[++tot]=(node){-1,x,pos[x],i,tot};
}
cdq(1,tot);
for(int i=1;i<=m;++i)ans[i]+=ans[i-1];
for(int i=0;i