前言
那是一波狠毒总括。
上边是一波瞎频仍。
这几天做了几道CDQ/全部二分，感觉自身做题速度好慢啊。
很多很显然的事物都看不出来
分治分不出来 打不出来 调不对
下午午后夜晚的功效完全分裂啊。
完蛋.jpg 绝望.jpg。
前言
那是一波粗犷统计。
上边是一波瞎再三。
这几天做了几道CDQ/全部二分，感觉温馨做题速度好慢啊。
很多很明朗的事物都看不出来
分治分不出去 打不出去 调不对
早晨早上晚上的频率完全差异啊。
完蛋.jpg 绝望.jpg。
关于CDQ分治
CDQ分治，求的是三维偏序难点都清楚的。
求法呢，正是在分治外面先把一维变成有序
然后分治下去，左边(l,mid)关于右侧(mid+1,r)就不设有某一维的逆序了，所以唯有两维偏序了。
那几个时候来一波”树状数组求逆序对”的操作搞一下二维偏序
就能够把跨过中线的，右侧更新左边的场所计算出来。
瞩目：只总括左侧的操作对左侧的问询的孝敬！
然后左右两边递归处理就好了。
正确性：依照线段树的模样递归的CDQ分治，保障每一对长富组在线段树上都有且仅有3个LCA(这不废话吗)，而这一组答案就会且仅会在LCA处总结。如若在LCA下边，点对不在1个work内自然不会一个钱打二十五个结。假诺在LCA下边了，点对就在同一侧，不会相互更新。
复杂度：设三回work的复杂度是f(len)，则复杂度是O(f(n)logn)。
一般都在分治里用树状数组，一般的复杂度正是O(nlog2n)的。
一般是如此的老路：假若三维偏序分别为a,b,c；
在main函数里保险a递增。
然后在CDQ里先分治左右，传下去的时候a依旧递增，不破坏性质。
然后分治完左右两边后，需保障左右两边分别b都以一日千里的(a不主要)。
然后正是相近归并排序的操作了。
此时左手的a肯定都自愧不如右侧的a,那么一旦对于2个左侧的元素
以前好像归并的操作就足以保险拥有小于b的左侧的因素都曾经遍历过。
那么找c也低于它的？值域线段树/树状数组等数据结构维护一下就好了。
然后你如此归并了一波后，就发现计算完答案后b是稳步递增的了(这一个时候a已经不重庆大学了)。
对于上层操作，符合”左右两边分别b是多如牛毛的”了。
BZOJ陌上花开竟然是权力题？那是在搞笑。
好吧BZOJ动态逆序对，之前写过的，做五回CDQ就好了。
BZOJ稻草人，也是CDQ。
再有二个便是高维偏序难点。
cogs上的2479 HZOI2014 偏序
正是四维偏序板子。
末尾还有七个狠抓版，到了七维，不是CDQ干的业务，详情请见这个PPT。
那里只谈谈四维偏序，即a<a’ b<b’
c<c’ d<d’。
做法是喜人的CDQ套CDQ套树状数组。
有个很妙的博客：Candy？
率先在外侧遵照a排好序。
进第1层CDQ。先递归处理，然后标记本来是在mid左侧照旧右侧的，左1右0，然后按b排序。
抑或只总括左侧部分跨过中线对左边部分的进献。
奉公守法b排好序后，就改成了总括标记为0的点的”在它左边的、标记为1的、(c,d)都自愧不如它的点的个数”。
“在它左侧+(c,d)都自愧不如它” =
三维偏序。
复制到另多少个数组里再做二遍cdq就能够了。
复杂度O(nlog^3n)。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <complex>
#include <stack>
#define LL long long int
#define dob double
#define FILE "partial_order"
//#define FILE "CDQ"
using namespace std;
const int N = 100010;
struct Data{int a,b,c,id;}p[N],que[N],que2[N];
int n,vis[N],tim,T[N];
LL Ans;
inline int gi(){
int x=0,res=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*res;
}
inline void update(int x){
for(;x<=n;x+=x&-x){
if(vis[x]!=tim)T[x]=0,vis[x]=tim;
T[x]++;
}
}
inline int query(int x,int ans=0){
for(;x;x-=x&-x){
if(vis[x]!=tim)T[x]=0,vis[x]=tim;
ans+=T[x];
}
return ans;
}
inline void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)>>1,i=l,j=mid+1,k=l;
cdq(l,mid);cdq(mid+1,r);tim++;
while(i<=mid && j<=r){
if(que[i].b<que[j].b){
if(que[i].id)update(que[i].c);
que2[k++]=que[i++];
}
else{
if(!que[j].id)Ans+=query(que[j].c);
que2[k++]=que[j++];
}
}
while(i<=mid)que2[k++]=que[i++];
while(j<=r){
if(!que[j].id)Ans+=query(que[j].c);
que2[k++]=que[j++];
}
for(k=l;k<=r;++k)que[k]=que2[k];
}
inline void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>1,i=l,j=mid+1,k=l;
CDQ(l,mid);CDQ(mid+1,r);
while(i<=mid && j<=r){
if(p[i].a<p[j].a)que[k]=p[i++],que[k++].id=1;
else que[k]=p[j++],que[k++].id=0;
}
while(i<=mid)que[k]=p[i++],que[k++].id=1;
while(j<=r)que[k]=p[j++],que[k++].id=0;
for(k=l;k<=r;++k)p[k]=que[k];cdq(l,r);
}
int main()
{
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=gi();
for(int i=1;i<=n;++i)p[i].a=gi();
for(int i=1;i<=n;++i)p[i].b=gi();
for(int i=1;i<=n;++i)p[i].c=gi();
CDQ(1,n);printf("%lld\n",Ans);
fclose(stdin);fclose(stdout);
return 0;
}
CDQ套CDQ
关于CDQ分治
CDQ分治，求的是三维偏序难点都精通的。
求法呢，正是在分治外面先把一维变成有序
然后分治下去，左侧(l,mid)关于右侧(mid+1,r)就不设有某一维的逆序了，所以只有两维偏序了。
那几个时候来一波”树状数组求逆序对”的操作搞一下二维偏序
就足以把跨过中线的，左侧更新右侧的情景计算出来。
在意：只总计左侧的操作对左边的精晓的孝敬！
然后左右两边递归处理就好了。
正确性：根据线段树的造型递归的CDQ分治，保障每一对伊利组在线段树上都有且仅有三个LCA(那不废话吗)，而这一组答案就会且仅会在LCA处总计。借使在LCA上边，点对不在二个work内自然不会总结。借使在LCA下面了，点对就在同一侧，不会相互更新。
复杂度：设二回work的复杂度是f(len)，则复杂度是O(f(n)logn)。
一般都在分治里用树状数组，一般的复杂度便是O(nlog2n)的。
一般是那样的套路：假诺三维偏序分别为a,b,c；
在main函数里保险a递增。
然后在CDQ里先分治左右，传下去的时候a依旧递增，不损坏性质。
然后分治完左右两边后，需保障左右两边分别b都以多如牛毛的(a不根本)。
然后就是近似归并排序的操作了。
此时左手的a肯定都低于左边的a,那么只要对于2个出手的要素
此前类似归并的操作就足以确认保障全数小于b的右侧的成分都早已遍历过。
那么找c也低于它的？值域线段树/树状数组等数据结构维护一下就好了。
然后您这么归并了一波后，就意识总括完答案后b是雷打不动递增的了(这些时候a已经不根本了)。
对于上层操作，符合”左右两边分别b是一日千里的”了。
BZOJ陌上花开竟然是权力题？那是在搞笑。
好吧BZOJ动态逆序对，此前写过的，做四次CDQ就好了。
BZOJ稻草人，也是CDQ。
还有1个正是高维偏序难题。
cogs上的2479 HZOI二零一五 偏序
就是四维偏序板子。
前面还有四个抓牢版，到了七维，不是CDQ干的作业，详情请见这个PPT。
这里只谈谈四维偏序，即a<a’ b<b’
c<c’ d<d’。
做法是可爱的CDQ套CDQ套树状数组。
有个很妙的博客：Candy？
先是在外围遵照a排好序。
进第叁层CDQ。先递归处理，然后标记本来是在mid左侧依旧右手的，左1右0，然后按b排序。
照旧只计算右边部分跨过中线对右侧部分的进献。
依据b排好序后，就改为了计算标记为0的点的”在它左边的、标记为1的、(c,d)都自愧不如它的点的个数”。
“在它左侧+(c,d)都低于它” =
三维偏序。
复制到另1个数组里再做一遍cdq就足以了。
复杂度O(nlog^3n)。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <complex>
#include <stack>
#define LL long long int
#define dob double
#define FILE "partial_order"
//#define FILE "CDQ"
using namespace std;
const int N = 100010;
struct Data{int a,b,c,id;}p[N],que[N],que2[N];
int n,vis[N],tim,T[N];
LL Ans;
inline int gi(){
int x=0,res=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*res;
}
inline void update(int x){
for(;x<=n;x+=x&-x){
if(vis[x]!=tim)T[x]=0,vis[x]=tim;
T[x]++;
}
}
inline int query(int x,int ans=0){
for(;x;x-=x&-x){
if(vis[x]!=tim)T[x]=0,vis[x]=tim;
ans+=T[x];
}
return ans;
}
inline void cdq(int l,int r){
if(l==r)return;
int mid=(l+r)>>1,i=l,j=mid+1,k=l;
cdq(l,mid);cdq(mid+1,r);tim++;
while(i<=mid && j<=r){
if(que[i].b<que[j].b){
if(que[i].id)update(que[i].c);
que2[k++]=que[i++];
}
else{
if(!que[j].id)Ans+=query(que[j].c);
que2[k++]=que[j++];
}
}
while(i<=mid)que2[k++]=que[i++];
while(j<=r){
if(!que[j].id)Ans+=query(que[j].c);
que2[k++]=que[j++];
}
for(k=l;k<=r;++k)que[k]=que2[k];
}
inline void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>1,i=l,j=mid+1,k=l;
CDQ(l,mid);CDQ(mid+1,r);
while(i<=mid && j<=r){
if(p[i].a<p[j].a)que[k]=p[i++],que[k++].id=1;
else que[k]=p[j++],que[k++].id=0;
}
while(i<=mid)que[k]=p[i++],que[k++].id=1;
while(j<=r)que[k]=p[j++],que[k++].id=0;
for(k=l;k<=r;++k)p[k]=que[k];cdq(l,r);
}
int main()
{
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=gi();
for(int i=1;i<=n;++i)p[i].a=gi();
for(int i=1;i<=n;++i)p[i].b=gi();
for(int i=1;i<=n;++i)p[i].c=gi();
CDQ(1,n);printf("%lld\n",Ans);
fclose(stdin);fclose(stdout);
return 0;
}
CDQ套CDQ
至于整体二分
全体二分主倘使把全数询问放在一块儿二分答案，然后把操作也一块儿分治。
几时用吗？
当你意识多组理解能够离线的时候
当您意识询问能够二分答案而且check复杂度对于单组询问尚可的时候
当你意识询问的操作都以千篇一律的的时候
你就足以选取完整二分那么些事物了。
具体做法讲起来有些玄学，其实看似主席树转化到距离的操作依然线段树上二分。
想想：二分答案的时候，对于三个答案，是或不是有点操作是没用的，有个别操作进献是不变的？
比如二分一个光阴，那么时间前面发生的操作正是从未用的，时间前边的孝敬是不变的。
二分一个最大值，比mid大的都以没用的，比mid小的个数是自然的。
全体二分正是选用了这么三个属性。
二分答案，然后把没有用的操作扫进左边，和答案在[mid+1,r]的刺探一起递归处理。
把有效的操作放进左边，减去不变的进献，和答案在[l,mid]的共同递归处理。
留意答案在[mid+1,r]的摸底要算上放进了左手的操作的贡献，开个变量记下来/直接压缩都能够。
留意全体二分在solve内的复杂度一定只好与区间长度线性相关，不能够每一回都有别的复杂度！
比如一次solve的复杂度是O(lenlogn)就足以，O(len+sqrt(n))就越发。
大致便是如此1个东西。
复杂度？和CDQ是一致的，都以O(f(len)logn)。
例题？BZOJ3110
K大数查询 Codevs Meteors。
一样的覆辙了。
至于全体二分
整体二分首假诺把富有询问放在一块儿二分答案，然后把操作也一同分治。
哪天用吧？
当你意识多组通晓能够离线的时候
当你发觉询问能够二分答案而且check复杂度对于单组询问能够承受的时候
当您发觉询问的操作都以一律的的时候
你就能够采用完全二分那么些东西了。
具体做法讲起来有点玄学，其实看似主席树转化到距离的操作如故线段树上二分。
想想：二分答案的时候，对于二个答案，是还是不是多少操作是没用的，有个别操作贡献是不变的？
比如二分3个时日，那么时间前面产生的操作正是从未用的，时间前边的进献是不变的。
二分二个最大值，比mid大的都以没用的，比mid小的个数是任其自然的。
全体二分正是行使了这么1天性子。
二分答案，然后把没有用的操作扫进左侧，和答案在[mid+1,r]的了然一起递归处理。
把有效的操作放进右边，减去不变的进献，和答案在[l,mid]的协同递归处理。
留意答案在[mid+1,r]的垂询要算上放进了右侧的操作的孝敬，开个变量记下来/直接压缩都得以。
注意整体二分在solve内的复杂度一定只好与区间长度线性相关，不能够每一趟都有别的复杂度！
比如1次solve的复杂度是O(lenlogn)就足以，O(len+sqrt(n))就非凡。
大致正是如此二个事物。
复杂度？和CDQ是相同的，都以O(f(len)logn)。
例题？BZOJ3110
K大数查询 Codevs Meteors。
一样的套路了。
有关部分要留心的地点
归并自然要把剩下的搞完！每回自小编都遗忘那码子事！
树状数组不可能暴力清零！记个time或许依葫芦画瓢减回去都足以，一定无法清零！
不要在CDQ里面套sort，太慢辣！(一定进不了第壹版的！)
有关部分要留意的地点
归并肯定要把多余的搞完！每趟小编都记不清那码子事！
树状数组无法暴力清零！记个time恐怕依葫芦画瓢减回去都能够，一定无法清零！
不要在CDQ里面套sort，太慢辣！(一定进不了第3版的！)