这是一些可以让你身败名裂的东西。
点分治
有人已经发现了这个恐怖的事实,事实就是我现在看半年前的点分治代码根本看不懂。
好吧,事实上今天上午也没讲点分治。
cdq分治
这个东西吧,我觉得吧,建议别学,过于困难。其实寒假学过,但是没有一个字是自己写的。
前置知识之求逆序对个数
给定 \(n\) 个数,每个数都有一个权值 \(a_i\),求满足 \(i\le j\) 同时 \(a_i\geq a_j\) 的点对个数。
显然,我们只需按顺序遍历一遍,用树状数组或者线段树维护一下在当前点之前,大于等于当前 \(a_i\) 的点个数即可。
至于它为什么对吧,显然你按顺序遍历就一定满足 \(i\neq j\),同时你维护的就是 \(a_j \geq a_i\),所以正确性十分显然啊。
正文
给定 \(n\) 个数,每个数有3个值 \(u_i,v_i,w_i\),求满足 \(u_i\le u_j,v_i\le v_j,w_i\le w_j\)的点对个数。
假如令 \(w_i=1\),那么答案就很显然了,我们只需要把它当成逆序对来算就可以。
同时,我们灵光一现,发现还有一个东西叫做归并排序,同时,归并排序前对 \(u\) 排序,就一定可以保证左半边的 \(u_i\) 值是小于等于右半边的,同时,归并排序本身就可以维护使 \(v\) 有序,因此,我们只需要再用树状数组维护一下 \(w\) 的顺序即可。
所以 cdq分治的思路就很显然了,分三层维护其有序性,首先在外面对 \(u\) 排个序,然后再使用归并排序,通过合并维护 \(v\) 的顺序,最后在归并排序过程中,我们考虑用个什么东西维护最后一维就好了。
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
int n,k,ans=0;
const int N=2e5+100;
int c[N],sum[N];
struct node {int x,y,z,ans,cnt;friend bool operator <(node a,node b) {if(a.x!=b.x) return a.x<b.x;if(a.y!=b.y) return a.y<b.y;return a.z<b.z;}
}a[N],b[N];
map<node,int>mp;
int read(){int x;cin>>x;return x;}
void insert(int x,int d){if(x==0) return ;while(x<=k){c[x]+=d;x+=lowbit(x);}
}
int ask(int x){int t=0;while(x){t+=c[x];// if(c[x]<0) cerr<<"GGGGG "<<x<<endl;x-=lowbit(x);} return t;
}
void merge(int l,int r) {if(l==r) return ;int mid=(l+r)>>1;merge(l,mid);merge(mid+1,r);int i=l,j=mid+1,now=l;for(;i<=mid&&j<=r;now++) {if(a[i].y<=a[j].y) {b[now]=a[i];insert(a[i].z,a[i].cnt);i++;}else {b[now]=a[j];b[now].ans+=ask(a[j].z);j++;}} for(;i<=mid;) {b[now]=a[i];insert(a[i].z,a[i].cnt);i++,now++;}for(;j<=r;j++,now++) {b[now]=a[j];b[now].ans+=ask(a[j].z);}for(int i=l;i<=mid;i++) {insert(a[i].z,-a[i].cnt);}for(int i=l;i<=r;i++) a[i]=b[i];return ;
}
signed main() {freopen("flower.in","r",stdin);freopen("flower.out","w",stdout);memset(c,0,sizeof(c));n=read();k=read();int x,y,z;for(int i=1;i<=n;i++) {x=read();y=read();z=read();mp[{x,y,z,0,0}]++;}int cnt=0;for(auto y:mp) {cnt++;node t=y.first;t.cnt=y.second;a[cnt]=t;a[cnt].ans=0;}sort(a+1,a+1+cnt);merge(1,cnt);for(int i=1;i<=cnt;i++) {a[i].ans=a[i].ans+a[i].cnt-1ll;sum[a[i].ans]+=a[i].cnt;}for(int i=0;i<n;i++) {cout<<sum[i]<<"\n";}return 0;
}
线段树分治
容易注意到,三个月之前我开过这一篇总结,但是那个摘要里面的只有标题至今都还是只有标题。
分治
就是,你考虑,对于一些求什么什么区间的问题,我们就把这个问题递归下去做,然后做一做左区间的,做一做右区间的,然后合并一下,就做完了。
例题
消失之物
容易想到,这题可以退背包来写,但是我们今天学分治,所以我们考虑分治,你考虑你每次往下走的时候,都把另一个区间的点给加进来,然后你走到最下面叶子的时候,一定就只有这个点还没有被加进来,然后直接统计答案就好。
然后考虑时间复杂度,显然,每个点最多会被加入 \(\log n\) 次,所以总时间复杂度 \(O(nmlogn)\) 可以接受。