關于CDQ分治我想我自己做過前面的題應該會了這種思想了吧，然後我是真的“會了”。
我想針對于偏序問題我是會了，我現在隻會三維偏序了，腦子都是疼的。
但是 CDQ分治最主要的還是基于時間方面的分治思想，是以呢，偏序問題沒那麼重要了。
關鍵是分治！分治（敲黑闆）不是偏序！
下面我們再來幾道偏序。。。
這道題呢 暴力修改+n^2求和 肯定炸了，但是細節注意到拿到題先分析爆long long麼
每次都是單點修改是以 2e5*2e3=4e8不會炸呢。
想一下如果我們把整個矩陣便利一遍 逾時 我們生成整個矩陣爆空間。
是以需要轉換問題 針對每個點都是坐标 x，y 以及該操作的時間 t
為什麼是三個元素啊 這不是三維偏序麼？但是對于查詢呢 一起放裡面不就好了。
這裡求一個矩陣的和我們需要将其轉換一下，要不然怎麼求
轉換成 大矩陣的和減去2個小矩陣的和+最小矩陣的和不就行了麼。解決了問題。
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<utility>
#include<set>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<vector>
#include<ctime>
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void put(int x)
{
x<0?putchar('-'),x=-x:0;
int num=0;char ch[50];
while(x)ch[++num]=x%10+'0',x/=10;
num==0?putchar('0'):0;
while(num)putchar(ch[num--]);
putchar(10);return;
}
const int MAXN=800002;
struct wy
{
int x,y,z;
int v,k;
}t[MAXN],tmp[MAXN];//三維偏序問題
int c[MAXN];
int n,cnt,num,ans[MAXN];
int cmp(wy x,wy y)
{
if(x.x==y.x)
{
if(x.y==y.y)return x.v<y.v;
return x.y<y.y;
}
return x.x<y.x;
}
int cmp1(wy x,wy y)
{
return x.v<y.v;
}
void add(int x,int y)
{
for(;x<=num;x+=x&(-x))c[x]+=y;
}
int ask(int x)
{
int cnt=0;
for(;x;x-=x&(-x))cnt+=c[x];
return cnt;
}
void CDQ(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
CDQ(l,mid);
CDQ(mid+1,r);
int i=l,j=mid+1;
for(int k=l;k<=r;k++)
{
if(j>r||(i<=mid&&t[i].y<=t[j].y))add(t[i].v,t[i].z),tmp[k]=t[i],i++;
else
{
ans[t[j].v]+=ask(t[j].v);
tmp[k]=t[j];
j++;
}
}
for(int k=l;k<=mid;k++)add(t[k].v,-t[k].z);
for(int k=l;k<=r;k++)t[k]=tmp[k];
return;
}
int main()
{
//freopen("1.in","r",stdin);
n=read();
while(1)
{
int p,x,y,z,u1,u2;
p=read();
if(p==3)break;
++cnt;
x=read();y=read();
if(p==1)
{
z=read();
t[++num].x=x,t[num].y=y,t[num].z=z;
t[num].v=cnt;
}
if(p==2)
{
u1=read();u2=read();
t[++num].x=min(u1-1,x-1);t[num].y=max(u2,y);
t[num].v=cnt++;t[num].k++;
t[++num].x=max(u1,x);t[num].y=min(u2-1,y-1);
t[num].v=cnt++;t[num].k++;
t[++num].x=min(u1-1,x-1);t[num].y=min(u2-1,y-1);
t[num].v=cnt++;t[num].k++;
t[++num].x=max(u1,x);t[num].y=max(u2,y);
t[num].v=cnt;t[num].k++;
}
}
sort(t+1,t+1+num,cmp);
//for(int i=1;i<=num;i++)cout<<t[i].x<<' '<<t[i].y<<endl;
CDQ(1,num);
sort(t+1,t+1+num,cmp1);
for(int i=1;i<=num;i++)
{
if(t[i].k!=0)
{
int xx=ans[t[i].v];
int yy=ans[t[i+1].v];
int zz=ans[t[i+2].v];
int uu=ans[t[i+3].v];
put(uu-xx-yy+zz);
i+=3;
}
}
return 0;
} View Code
關鍵是思想思想 不是三維偏序！！！（說了是CDQ的思想）
下面再來一道三維偏序問題：
這道題呢 很迷的我迷了一晚上加一下午 加一中午。
聽學長講的博弈論都不想聽一直在想如何統計答案。
時間戳這個我是想出來了，但是三維偏序如何統計答案呢，我迷了一波。
因為CDQ我光想着CDQ分治左邊隻會對右邊進行累加卻沒想到啊，這個數字消失之時右邊也會對其有價值累加。
我卻一直在被CDQ左邊隻會對右邊有貢獻搞亂了，貌似不知道逆序對的性質了。
哎 慚愧其實我是能想出來的，但是思想一直不在正軌上最後被學長拉回來了。
這道題其實需要統計兩遍然後 左邊對右邊的貢獻和右邊對左邊的貢獻。
關鍵是知道自己在寫什麼資料存到了哪裡，哪裡是答案 求出來的東西是什麼這幾點很重要！
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<utility>
#include<set>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<vector>
#include<ctime>
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline long long read()
{
long long x=0,f=1;char ch=getc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
return x*f;
}
inline void put(long long x)
{
x<0?putchar('-'),x=-x:0;
long long num=0;char ch[50];
while(x)ch[++num]=x%10+'0',x/=10;
num==0?putchar('0'):0;
while(num)putchar(ch[num--]);
putchar(10);return;
}
const long long MAXN=100002;
struct wy
{
long long x,y,t;
}t[MAXN],tmp[MAXN];
long long n,m,c[MAXN];
long long q[MAXN],h,num[MAXN],cnt,x,sum[MAXN],pos[MAXN],cnt1;
long long cmp(wy x,wy y){return x.x>y.x;}
void add(long long x,long long y){for(;x;x-=x&(-x))c[x]+=y;}
void add1(long long x,long long y){for(;x<=MAXN;x+=x&(-x))c[x]+=y;}
long long ans[MAXN];
long long ask(long long x)
{
long long cnt=0;
for(;x<=MAXN;x+=x&(-x))cnt+=c[x];
return cnt;
}
long long ask1(long long x)
{
long long cnt=0;
for(;x;x-=x&(-x))cnt+=c[x];
return cnt;
}
void CDQ(long long l,long long r)
{
if(l==r)return;
long long mid=(l+r)>>1;
CDQ(l,mid);
CDQ(mid+1,r);
long long i=l,j=mid+1;
for(long long k=l;k<=r;k++)//左邊給右邊貢獻小t累加大t貢獻
{
if(j>r||(t[i].t>=t[j].t&&i<=mid))tmp[k]=t[i],add(t[i].y,1),i++;
else
{
sum[t[j].t]+=ask(t[j].y);
tmp[k]=t[j];
j++;
}
}
for(long long k=l;k<=mid;k++)add(t[k].y,-1);
for(long long k=l;k<=r;k++)t[k]=tmp[k];
return;
}
void CDQ1(long long l,long long r)
{
if(l==r)return;
long long mid=(l+r)>>1;
CDQ1(l,mid);
CDQ1(mid+1,r);
long long i=l,j=mid+1;
for(long long k=l;k<=r;k++)//左邊給右邊貢獻小t累加大t貢獻
{
if(j>r||(t[i].t>=t[j].t&&i<=mid))tmp[k]=t[i],add1(t[i].y,1),i++;
else
{
sum[t[j].t]+=ask1(t[j].y);
tmp[k]=t[j];
j++;
}
}
for(long long k=l;k<=mid;k++)add1(t[k].y,-1);
for(long long k=l;k<=r;k++)t[k]=tmp[k];
return;
}
void yy()
{
for(long long i=h;i>=1;i--)
{
cnt1+=ask1(q[i]-1);
add1(q[i],1);
}
return;
}
int main()
{
//freopen("1.in","r",stdin);
n=read();m=read();
for(long long i=1;i<=n;i++)
{
x=read();
t[i].x=i;
t[i].y=x;
pos[x]=i;
}
for(long long i=1;i<=m;i++)x=read(),num[pos[x]]=++cnt;
for(long long i=1;i<=n;i++)
{
if(num[i]!=0)t[i].t=num[i];
else q[++h]=t[i].y,t[i].t=cnt+1;
}
//for(long long i=1;i<=n;i++)cout<<t[i].x<<' '<<t[i].y<<' '<<t[i].t<<endl;
CDQ(1,n);
//for(long long i=1;i<=cnt;i++)put(sum[i]);
sort(t+1,t+1+n,cmp);
CDQ1(1,n);
yy();
//cout<<cnt1<<endl;
for(long long i=cnt+1;i>=1;i--)ans[i]=sum[i]+ans[i+1];
for(long long i=1;i<=cnt;i++)put(ans[i]-cnt1);
return 0;
}