https://acm.uestc.edu.cn/problem/ren-zai-di-shang-zou-guo-cong-tian-shang-lai/description
将点当成左闭右开的线段，然后每次查是否有位置填，也就是一个点维护和一个线段维护就可以了
#include <bits/stdc++.h> using namespace std; const int maxn= 1e5+9; int res[maxn]; int flag; struct rt{ int x,y; int nx,ny; }a[maxn]; int b[maxn*2]; struct xx{ int sum,ls,rs; int lazy; }dat[maxn*8]; int dd[maxn*8]; int dian[maxn*8]; int dianlazy[maxn*8]; int lazy[maxn*8]; void pushUpS(int k){ if(dat[k<<1].rs&&dat[k<<1|1].ls){ dat[k].sum=dat[k<<1].sum+dat[k<<1|1].sum-1; } else{ dat[k].sum=dat[k<<1].sum+dat[k<<1|1].sum; } dat[k].rs=dat[k<<1|1].rs; dat[k].ls=dat[k<<1].ls; } void pushUpd(int k){ dian[k]=dian[k<<1]+dian[k<<1|1]; } void pushUp(int k){ dd[k]=dd[k<<1]+dd[k<<1|1]; } void pushDown(int k,int l,int r){ int mid=(l+r)>>1; dd[k<<1]=mid-l+1; dd[k<<1|1]=r-mid; lazy[k<<1]=lazy[k<<1|1]=1; lazy[k]=0; } void updata(int a,int b,int l,int r,int k){ if(a<=l&&r<=b){ dd[k]=r-l+1;lazy[k]=1;return; } if(lazy[k])pushDown(k,l,r); int mid=(l+r)>>1; if(a<=mid)updata(a,b,l,mid,k<<1); if(b>mid)updata(a,b,mid+1,r,k<<1|1); pushUp(k); } int query(int a,int b,int l,int r,int k){ if(a<=l&&r<=b)return dd[k]; if(lazy[k])pushDown(k,l,r); int mid=(l+r)>>1; int ans=0; if(a<=mid)ans+=query(a,b,l,mid,k<<1); if(b>mid)ans+=query(a,b,mid+1,r,k<<1|1); return ans; } void updataS(int a,int b,int l,int r,int k){ if(dat[k].lazy)return; if(a<=l&&r<=b){ dat[k].sum=1; dat[k].ls=dat[k].rs=1; dat[k].lazy=1; return ; } int mid=(l+r)>>1; if(a<=mid)updataS(a,b,l,mid,k<<1); if(b>mid)updataS(a,b,mid+1,r,k<<1|1); pushUpS(k); } void updatad(int a,int b,int l,int r,int k,int x){ if(dianlazy[k])return; if(a<=l&&r<=b){ dian[k]=x; if(x==0)dianlazy[k]=1; return; } int mid=(l+r)>>1; if(a<=mid)updatad(a,b,l,mid,k<<1,x); if(b>mid)updatad(a,b,mid+1,r,k<<1|1,x); pushUpd(k); } int main(){ ios::sync_with_stdio(false); int n;cin>>n; int tt=0; for(int i=1;i<=n;i++){ cin>>a[i].x>>a[i].y; b[++tt]=a[i].x; b[++tt]=a[i].y; } sort(b+1,b+1+tt); int num=unique(b+1,b+1+tt)-(b+1); for(int i=1;i<=n;i++){ a[i].nx=lower_bound(b+1,b+1+num,a[i].x)-b; a[i].ny=lower_bound(b+1,b+1+num,a[i].y)-b; } int ans=0; for(int i=1;i<=n;i++){ int x=query(a[i].nx,a[i].ny,1,num,1); updata(a[i].nx,a[i].ny,1,num,1); if(a[i].nx!=a[i].ny){ updataS(a[i].nx,a[i].ny-1,1,num,1); updatad(a[i].nx,a[i].ny,1,num,1,0); } if(x==0){ ans++; if(a[i].nx==a[i].ny){ updatad(a[i].nx,a[i].nx,1,num,1,1); } } else{ ans=dat[1].sum+dian[1]; } res[i]=ans; } for(int i=1;i<=n;i++){ cout<<res[i]; if(i<n)cout<<" "; else cout<<endl; } return 0; }
