关于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[<<],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;
}
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void put(int x)
{
x<?putchar('-'),x=-x:;
int num=;char ch[];
while(x)ch[++num]=x%+'',x/=;
num==?putchar(''):;
while(num)putchar(ch[num--]);
putchar();return;
}
const int MAXN=;
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=;
for(;x;x-=x&(-x))cnt+=c[x];
return cnt;
}
void CDQ(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>;
CDQ(l,mid);
CDQ(mid+,r);
int i=l,j=mid+;
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()
{
int p,x,y,z,u1,u2;
p=read();
if(p==)break;
++cnt;
x=read();y=read();
if(p==)
{
z=read();
t[++num].x=x,t[num].y=y,t[num].z=z;
t[num].v=cnt;
}
if(p==)
{
u1=read();u2=read();
t[++num].x=min(u1-,x-);t[num].y=max(u2,y);
t[num].v=cnt++;t[num].k++;
t[++num].x=max(u1,x);t[num].y=min(u2-,y-);
t[num].v=cnt++;t[num].k++;
t[++num].x=min(u1-,x-);t[num].y=min(u2-,y-);
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+,t++num,cmp);
//for(int i=1;i<=num;i++)cout<<t[i].x<<' '<<t[i].y<<endl;
CDQ(,num);
sort(t+,t++num,cmp1);
for(int i=;i<=num;i++)
{
if(t[i].k!=)
{
int xx=ans[t[i].v];
int yy=ans[t[i+].v];
int zz=ans[t[i+].v];
int uu=ans[t[i+].v];
put(uu-xx-yy+zz);
i+=;
}
}
return ;
}
关键是思想思想 不是三维偏序！！！（说了是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[<<],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;
}
inline long long read()
{
long long x=,f=;char ch=getc();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}
return x*f;
}
inline void put(long long x)
{
x<?putchar('-'),x=-x:;
long long num=;char ch[];
while(x)ch[++num]=x%+'',x/=;
num==?putchar(''):;
while(num)putchar(ch[num--]);
putchar();return;
}
const long long MAXN=;
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=;
for(;x<=MAXN;x+=x&(-x))cnt+=c[x];
return cnt;
}
long long ask1(long long x)
{
long long cnt=;
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)>>;
CDQ(l,mid);
CDQ(mid+,r);
long long i=l,j=mid+;
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,),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,-);
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)>>;
CDQ1(l,mid);
CDQ1(mid+,r);
long long i=l,j=mid+;
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,),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,-);
for(long long k=l;k<=r;k++)t[k]=tmp[k];
return;
}
void yy()
{
for(long long i=h;i>=;i--)
{
cnt1+=ask1(q[i]-);
add1(q[i],);
}
return;
}
int main()
{
//freopen("1.in","r",stdin);
n=read();m=read();
for(long long i=;i<=n;i++)
{
x=read();
t[i].x=i;
t[i].y=x;
pos[x]=i;
}
for(long long i=;i<=m;i++)x=read(),num[pos[x]]=++cnt;
for(long long i=;i<=n;i++)
{
if(num[i]!=)t[i].t=num[i];
else q[++h]=t[i].y,t[i].t=cnt+;
}
//for(long long i=1;i<=n;i++)cout<<t[i].x<<' '<<t[i].y<<' '<<t[i].t<<endl;
CDQ(,n);
//for(long long i=1;i<=cnt;i++)put(sum[i]);
sort(t+,t++n,cmp);
CDQ1(,n);
yy();
//cout<<cnt1<<endl;
for(long long i=cnt+;i>=;i--)ans[i]=sum[i]+ans[i+];
for(long long i=;i<=cnt;i++)put(ans[i]-cnt1);
return ;
}
没有梦想 何必远方？