数点,偏序,
Central_GYM · · 算法·理论
简单记录一下基础的数点,
二维数点偏序
P10814(二维数点模板)
原题我们转化一下,
我们将问题变成在一个平面内,对于每一个询问,求出在
当然你也可以 CDQ 分治,这个在下面讲。
三位数点偏序
P3810(三位数点模板)
这个题询问本质求满足
CDQ 分治
我们考虑对于
我们对于整个区间
我们既然已经把
有一个坑点在于对于完全相同的点,在将其分到两个区间的时候会少算情况,少算情况的原因无疑是因为这个点在里面放了很多,因此我们直接离散化将其缩到一个点上即可,对于每一次贡献,从原本的加 1 改为加实际的点数即可,当询问不等于任何点的时候,我们将询问当成特殊的点压入来处理,当存在下界的时候,我们再额外进行一个容斥,将其拆成多个系数为 1 或 -1 的独立询问,计算贡献。
CDQ 分治本质通过类似归并的操作人为地消掉一维的影响,是一种算是常见的手段,你也可以直接用 CDQ 二维数点来去掉数据结构(貌似会更劣),也可以 CDQ 套二维数点 CDQ 来实现三维数点,还可以 CDQ 套 CDQ 实现四维数点。
在复杂度方面 CDQ 内部处理是
#include<bits/stdc++.h>
#define lowbit x&(-x)
#define ll long long
using namespace std;
const int N=3e5+5;
struct points{
int a,b,c;
int ARIS,KEI;
}a[N],b[N];
struct bits{
int tr[N];
void update(int x,int k){
while(x<=N){
tr[x]+=k;
x+=lowbit;
}
}
int query(int x){
int ans=0;
while(x){
ans+=tr[x];
x-=lowbit;
}
return ans;
}
}tr;
bool cmp(points x,points y){
if(x.a==y.a){
if(x.b==y.b){
return x.c<y.c;
}
return x.b<y.b;
}
return x.a<y.a;
}
bool cmpp(points x,points y){
return x.b<y.b;
}
int n,m,k,f[N];
void CDQ(int pl,int pr){
if(pl==pr){
return ;
}
int mid=(pl+pr)>>1;
CDQ(pl,mid);CDQ(mid+1,pr);
sort(a+pl,a+1+mid,cmpp);sort(a+1+mid,a+1+pr,cmpp);
int l=pl,r=mid+1;
for(;r<=pr;r++){
while(a[l].b<=a[r].b&&l<=mid){
tr.update(a[l].c,a[l].KEI);
l++;
}
a[r].ARIS+=tr.query(a[r].c);
}
for(int i=pl;i<l;i++){
tr.update(a[i].c,-a[i].KEI);
}
return ;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>b[i].a>>b[i].b>>b[i].c;
}
sort(b+1,b+1+n,cmp);
int tot=0,q=0;
for(int i=1;i<=n;i++){
q++;
if(b[i].a!=b[i+1].a||b[i].b!=b[i+1].b||b[i].c!=b[i+1].c){
a[++tot]=b[i];
a[tot].KEI=q;
q=0;
}
}
m=n;
n=tot;
CDQ(1,n);
for(int i=1;i<=n;i++){
f[a[i].ARIS+a[i].KEI-1]+=a[i].KEI;
}
for(int i=0;i<m;i++){
cout<<f[i]<<'\n';
}
return 0;
}/*
再见了,王女
*/
::::
分块
这类计数题目基本都存在分块做法/咦,
这一部分参考了 NATURAL6 的 这篇题解。
我们跟前面的思路一样,我们考虑先消掉
我们有一个最简单的暴力算法,对于每一个点,加入以后我们计算二位前缀和,实现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+5;
struct points{
int a,b,c;
int ARIS,KEI;
}a[N],b[N];
bool cmp(points x,points y){
if(x.a==y.a){
if(x.b==y.b){
return x.c<y.c;
}
return x.b<y.b;
}
return x.a<y.a;
}
int n,m,k,B,tot,d[N],c[N],L[N],R[N],s[505][505],tob[N],toc[N],x,y,f[N];
void refresh(int p){
int w=0;
tot=0;
memset(s,0,sizeof(s));
for(int i=L[p];i<=R[p];i++){
tot++;
d[tot]=a[i].b;
}
sort(d+1,d+1+tot);
tot=unique(d+1,d+1+tot)-d-1;
w=0;
for(int i=1;i<=k;i++){
if(i>d[w]&&w<=tot){
w++;
}
tob[i]=w;
}
x=tot;
tot=0;
for(int i=L[p];i<=R[p];i++){
tot++;
d[tot]=a[i].c;
}
sort(d+1,d+1+tot);
tot=unique(d+1,d+1+tot)-d-1;
w=0;
for(int i=1;i<=k;i++){
if(i>d[w]&&w<=tot){
w++;
}
toc[i]=w;
}
y=tot;
for(int i=1;i<L[p];i++){
s[tob[a[i].b]][toc[a[i].c]]+=a[i].KEI;
}
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
s[i][j]+=(s[i][j-1]+s[i-1][j]-s[i-1][j-1]);
}
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>b[i].a>>b[i].b>>b[i].c;
}
sort(b+1,b+1+n,cmp);
int tot=0,q=0;
for(int i=1;i<=n;i++){
q++;
if(i==n||b[i].a!=b[i+1].a||b[i].b!=b[i+1].b||b[i].c!=b[i+1].c){
a[++tot]=b[i];
a[tot].KEI=q;
q=0;
}
}
m=n;
n=tot;
B=sqrt(n);
for(int i=1;i<=n;i++){
c[i]=(i-1)/B+1;
}
for(int i=1;i<=B;i++){
L[i]=(i-1)*B+1;
R[i]=i*B;
}
if(R[B]!=n){
B++;
L[B]=R[B-1]+1;
R[B]=n;
}
for(int p=1;p<=B;p++){
refresh(p);
for(int i=L[p];i<=R[p];i++){
for(int j=L[p];j<i;j++){
if(a[j].b<=a[i].b&&a[j].c<=a[i].c){
a[i].ARIS+=a[j].KEI;
}
}
a[i].ARIS+=s[tob[a[i].b]][toc[a[i].c]];
}
}
for(int i=1;i<=n;i++){
f[a[i].ARIS+a[i].KEI-1]+=a[i].KEI;
}
for(int i=0;i<m;i++){
cout<<f[i]<<'\n';
}
return 0;
}/*
再见了,王女
*/
::::
树套树
我们还是那个思路,先按
P10281 Grass Segments G
模拟赛题目,做的时候死亡了/fn
注意到我们对于
我们可以轻松注意到只有当四个东西都成立的时候上面的总的式子才成立,我们注意到
然后我们直接三维数点,复杂度
#include<bits/stdc++.h>
#define ll long long
#define lowbit x&-x
using namespace std;
const int N=1.6e6;
map<pair<int,int>,int> mp;
struct bits{
int tr[N+50];
void add(int x,int k){
while(x<=N){
tr[x]+=k;
x+=lowbit;
}
}
int query(int x){
int res=0;
while(x){
res+=tr[x];
x-=lowbit;
}
return res;
}
}tr;
struct ops{
int l,r,k;
}b[N];
struct node{
int a,b,c,ans,cnt,id;
}a[N],q[N];
int n,ans[N];
bool cmp2nd(node x,node y){
if(x.id==y.id){
if(x.a==y.a){
if(x.b==y.b){
return x.c<y.c;
}
return x.b<y.b;
}
return x.a<y.a;
}
return x.id<y.id;
}
bool cmpp2nd(node x,node y){
if(x.a==y.a){
if(x.b==y.b){
if(x.c==y.c){
return x.id<y.id;
}
return x.c<y.c;
}
return x.b<y.b;
}
return x.a<y.a;
}
bool cmppp2nd(node x,node y){
if(x.b==y.b){
return x.c<y.c;
}
return x.b<y.b;
}
void CDQ(int pl,int pr){
if(pl==pr){
return ;
}
int mid=(pl+pr)>>1;
CDQ(pl,mid);CDQ(mid+1,pr);
sort(a+pl,a+mid+1,cmppp2nd);sort(a+mid+1,a+pr+1,cmppp2nd);
int l=pl;
for(int r=mid+1;r<=pr;r++){
while(a[l].b<=a[r].b&&l<=mid){
if(!a[l].id){
tr.add(a[l].c,a[l].cnt);
}
l++;
}
if(a[r].id){
ans[a[r].id]+=tr.query(a[r].c);
}
}
for(int i=pl;i<l;i++){
if(!a[i].id){
tr.add(a[i].c,-a[i].cnt);
}
}
}
int A[N],B[N],C[N];
int tota,totb,totc;
bool cmpa(node x,node y){
return x.a<y.a;
}
bool cmpb(node x,node y){
return x.b<y.b;
}
bool cmpc(node x,node y){
return x.c<y.c;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>b[i].l>>b[i].r>>b[i].k;
mp[{b[i].l,b[i].r}]++;
}
int tot,m,w,now;
tot=tota=totb=totc=0;
for(int i=1;i<=n;i++){
q[++tot].a=b[i].l;
q[tot].b=-b[i].r+N;
q[tot].c=-(b[i].r-b[i].l)+N;
q[tot].cnt=1;
q[tot].id=0;
A[++tota]=q[tot].a;B[++totb]=q[tot].b;C[++totc]=q[tot].c;
q[++tot].a=b[i].r-b[i].k;
q[tot].b=-b[i].l-b[i].k+N;
q[tot].c=-b[i].k+N;
q[tot].cnt=0;
q[tot].id=i;
A[++tota]=q[tot].a;B[++totb]=q[tot].b;C[++totc]=q[tot].c;
}
sort(A+1,A+1+tota);
sort(B+1,B+1+totb);
sort(C+1,C+1+totc);
tota=unique(A+1,A+1+tota)-A-1;
totb=unique(B+1,B+1+totb)-B-1;
totc=unique(C+1,C+1+totc)-C-1;
now=1;
sort(q+1,q+1+tot,cmpa);
for(int i=1;i<=tot;i++){
while(q[i].a!=A[now]){
now++;
}
q[i].a=now;
}
now=1;
sort(q+1,q+1+tot,cmpb);
for(int i=1;i<=tot;i++){
while(q[i].b!=B[now]){
now++;
}
q[i].b=now;
}
now=1;
sort(q+1,q+1+tot,cmpc);
for(int i=1;i<=tot;i++){
while(q[i].c!=C[now]){
now++;
}
q[i].c=now;
}
sort(q+1,q+1+tot,cmp2nd);
w=m=0;
for(int i=1;i<=tot;i++){
if(q[i].id){
a[++m]=q[i];
continue;
}
if(q[i].a!=q[i+1].a||q[i].b!=q[i+1].b||q[i].c!=q[i+1].c||q[i].id!=q[i+1].id){
a[++m]=q[i];
a[m].cnt=i-w;
w=i;
}
}
sort(a+1,a+1+m,cmpp2nd);
CDQ(1,m);
for(int i=1;i<=n;i++){
cout<<ans[i]-1<<'\n';
}
return 0;
}/*
再见了,王女
*/
::::
补充思路
我们讨论一下,对于
我们不难发现,情况 1 是与剩下三种情况无关的,我们直接算即可,对于情况 2,3 我们刻意地忽略了它们的另一个界的限制,只保证其分别控制的界和交的部分的大小,这样会出现问题,也就是 4 的情况同时被 2,3 给贡献到,我们容斥一下,答案就是 1+2+3-4。
对于 1,除了左右界以外存在无法消去的
容斥无疑是简单的,边界无疑是难办的。
P11197赛狗游戏
我们看到这个问题给的两个限制,我们假设有一个点对
我们可以直接写 CDQ,很明显
我们提供一种
- 只满足二维偏序,也就是反着来只满足一维偏序。
- 满足三维偏序,也就是反着来不满足任何偏序。
那么我们的答案就是三种满足二维偏序的点对集合大小之和减去中间三个集合之交的大小再除去 2。我们可以整个图来方便理解:
对的,就是容斥最经典的那个图,我们将三个偏序分别关系满足的集合画出来,我们的答案是中间的
根据我们上面的性质我们发现对于
#include<bits/stdc++.h>
#define lowbit x&(-x)
#define ll long long
using namespace std;
const ll N=1e6+5;
ll n,k,a[N],b[N],c[N],KEI[N],ARIS;
struct bits{
ll tr[N];
void add(ll x,ll k){
while(x<=N){
tr[x]+=k;
x+=lowbit;
}
}
ll query(ll x){
ll ARIS=0;
while(x){
ARIS+=tr[x];
x-=lowbit;
}
return ARIS;
}
}tr1,tr2,tr3;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(ll i=1;i<=n;i++){
ll x;
cin>>x;
}
for(ll i=1;i<=n;i++){
ll x;
cin>>x;
a[x]=i;
}
for(ll i=1;i<=n;i++){
ll x;
cin>>x;
b[x]=i;
}
for(ll i=1;i<=n;i++){
ll x;
cin>>x;
c[x]=i;
}
for(ll i=1;i<=n;i++){
KEI[a[i]]=b[i];
}
for(ll i=1;i<=n;i++){
ARIS+=tr1.query(KEI[i]);
tr1.add(KEI[i],1);
}
for(ll i=1;i<=n;i++){
KEI[c[i]]=b[i];
}
for(ll i=1;i<=n;i++){
ARIS+=tr2.query(KEI[i]);
tr2.add(KEI[i],1);
}
for(ll i=1;i<=n;i++){
KEI[a[i]]=c[i];
}
for(ll i=1;i<=n;i++){
ARIS+=tr3.query(KEI[i]);
tr3.add(KEI[i],1);
}
cout<<(ARIS-(n-1)*n/2)/2;
return 0;
}/*
再见了,王女
*/
::::