CDQ分治
一般珂以替代一些较复杂的高级数据结构，能用来处理偏序问题、优化dp转移等。
大概思路就是分治处理点对的关系，分成三类点：\(\mathbf{\small{1}}\le i<j\le mid\)、\(\mathbf{\small{1}}\le i\le mid<j\le n\)、\(mid<i<j\le n\)，然后用额外的 \(O(logn)\) 的时间去计算第二类点，一般是用树状数组或者线段树维护。
题
P3810 【模板】三维偏序（陌上花开）
先按 \(a\) 为第一关键字排序，去重，然后分治。分治中我们要解决的是 \(b,c\) 的二维偏序，考虑使用树状数组求解，对两边序列分别按 \(b\) 为第一关键字排序，用双指针的维护方法不断在树状数组中统计答案，因为只会走一遍所以复杂度 \(O(nlogn)\)。最后统计答案的时候注意每个 \(i\) 实际答案是 \(ans_i+cnt_i-\mathbf{\small{1}}\)。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2*114514,M=1919810;
struct xx{
ll a,b,c,cnt,ans;
bool operator !=(const xx &lxl)const{
return a!=lxl.a||b!=lxl.b||c!=lxl.c;
}
}a[N];
ll n,m,s[N],res[N];
ll lowbit(ll x){return x&-x;}
void add(ll x,ll k){
while(x<=m){
s[x]+=k;
x+=lowbit(x);
}
}
ll query(ll x){
ll ans=0;
while(x){
ans+=s[x];
x-=lowbit(x);
}
return ans;
}
bool cmp1(xx x,xx y){
return x.a==y.a?(x.b==y.b?x.c<y.c:x.b<y.b):x.a<y.a;
}
bool cmp2(xx x,xx y){
return x.b==y.b?x.c<y.c:x.b<y.b;
}
void calc(ll l,ll r){
if(l==r) return;
ll mid=l+r>>1;
calc(l,mid),calc(mid+1,r);
sort(a+l,a+mid+1,cmp2),sort(a+mid+1,a+r+1,cmp2);
ll j=l;
for(int i=mid+1;i<=r;++i){
while(a[i].b>=a[j].b&&j<=mid){
add(a[j].c,a[j].cnt);
++j;
}
a[i].ans+=query(a[i].c);
}
for(int i=l;i<j;++i) add(a[i].c,-a[i].cnt);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>a[i].a>>a[i].b>>a[i].c;
sort(a+1,a+n+1,cmp1);
ll tot=0,top=0;
for(int i=1;i<=n;++i){
++top;
if(a[i]!=a[i+1]) a[++tot]=a[i],a[tot].cnt=top,top=0;
}
calc(1,tot);
for(int i=1;i<=tot;++i) res[a[i].ans+a[i].cnt-1]+=a[i].cnt;
for(int i=0;i<n;++i) cout<<res[i]<<'\n';
return 0;
}
P2487 [SDOI2011] 拦截导弹
先考虑朴素算法：第一问就直接 \(O(n^{\mathbf{\small{2}}})\) dp转移，第二问的话我们珂以多开几个数组：\(f\mathbf{\small{2}}_i\) 表示以 \(i\) 为开头的最长不上升子序列的长度，再开两个数组 \(g\mathbf{\small{1}},g\mathbf{\small{2}}\) 记录以 \(i\) 作为结尾和开头的最长不上升子序列的个数。这样子每个满足 \(f\mathbf{\small{1}}_i+f\mathbf{\small{2}}_i-\mathbf{\small{1}}=ans\) 的 \(i\) 的答案就是 \(\dfrac{g\mathbf{\small{1}}_i\times g\mathbf{\small{2}}_i}{sum}\)，\(sum\) 为总方案数。求以 \(i\) 开头的答案珂以直接把序列倒过来权值赋为相反数然后正常dp。
考虑怎么优化，观察到这个最长不下降子序列就是个三维偏序问题，但是我们此时注意计算顺序是先计算左区间再算中间段再算右区间，否则dp的转移会有问题。这里我们分治时维护的要求变成了单点修改区间查询，但是我已经不会树状数组了，就用了线段树。还有这个题好像珂以直接 \(O(n)\) 清空整个线段树就免得还要另开数组记录？另外要开long double。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lb long double
#define ls now<<1
#define rs now<<1|1
const ll N=2*114514,M=1919810;
ll n,m,v[N];
struct xx{
ll t;
lb h,v;
}a[N],b[N],c[N];
struct gx{
lb val,cnt;
}f1[N],f2[N];
bool cmp1(xx x,xx y){
return x.t<y.t;
}
bool cmp2(xx x,xx y){
return x.h==y.h?x.v>y.v:x.h>y.h;
}
gx add(gx x,gx y){
return x.val==y.val?(gx){x.val,x.cnt+y.cnt}:(x.val>y.val?x:y);
}
struct tree{
ll l,r;
gx v;
}t[4*N];
void pushup(ll now){
t[now].v=add(t[ls].v,t[rs].v);
}
void build(ll now,ll l,ll r){
t[now].l=l,t[now].r=r;
t[now].v=(gx){0,0};
if(l==r) return;
ll mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
void update(ll now,ll tar,gx k){
if(t[now].l==t[now].r){
t[now].v=add(t[now].v,k);
return;
}
ll mid=t[now].l+t[now].r>>1;
if(tar<=mid) update(ls,tar,k);
else update(rs,tar,k);
pushup(now);
}
gx query(ll now,ll x,ll y){
if(t[now].l>=x&&t[now].r<=y) return t[now].v;
ll mid=t[now].l+t[now].r>>1;
gx ans=(gx){0,0};
if(x<=mid) ans=add(ans,query(ls,x,y));
if(y>mid) ans=add(ans,query(rs,x,y));
return ans;
}
void clean(ll now,ll tar){
t[now].v=(gx){0,0};
if(t[now].l==t[now].r) return;
ll mid=t[now].l+t[now].r>>1;
if(tar<=mid) clean(ls,tar);
else clean(rs,tar);
}
void calc(ll l,ll r,gx *dp){
if(l==r){
if(!dp[(ll)b[l].t].val)
dp[(ll)b[l].t]=(gx){1,1};
return;
}
ll mid=l+r>>1;
calc(l,mid,dp);
for(int i=mid+1;i<=r;++i) c[i]=b[i];
sort(c+mid+1,c+r+1,cmp2);
ll j=l;
for(int i=mid+1;i<=r;++i){
while(b[j].h>=c[i].h&&j<=mid){
update(1,b[j].v,dp[(ll)b[j].t]);
++j;
}
gx ans=query(1,c[i].v,m);
if(ans.val){
++ans.val;
dp[(ll)c[i].t]=add(dp[(ll)c[i].t],ans);
}
}
for(int i=l;i<=j;++i) clean(1,b[i].v);
calc(mid+1,r,dp);
sort(b+l,b+r+1,cmp2);
}
void solve(bool flag){
for(int i=1;i<=n;++i) b[i]=a[i],v[i]=a[i].v;
sort(b+1,b+n+1,cmp1);
sort(v+1,v+n+1);
m=unique(v+1,v+n+1)-v-1;
for(int i=1;i<=n;++i) b[i].v=lower_bound(v+1,v+m+1,b[i].v)-v;
build(1,1,m);
if(!flag) calc(1,n,f1);
else calc(1,n,f2);
}
lb ans,sum;
int main(){
//ios::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i].h>>a[i].v,a[i].t=i;
solve(0);
for(int i=1;i<=n;++i) a[i]=(xx){n-i+1,-a[i].h,-a[i].v};
solve(1);
for(int i=1;i<=n;++i) ans=max(ans,f1[i].val);
for(int i=1;i<=n;++i) if(ans==f1[i].val) sum+=f1[i].cnt;
printf("%Ld\n",(ll)ans);
for(int i=1;i<=n;++i)
if(f1[i].val+f2[n-i+1].val-1==ans) printf("%0.5Lf ",(f1[i].cnt*1.0*f2[n-i+1].cnt*1.0/sum));
else printf("0.00000 ");
return 0;
}