[CF983D]Arkady and Rectangles-白红宇

[CF983D]Arkady and Rectangles

阅读量：6266 次

发布时间：2019-06-22

本文共 1900 字，大约阅读时间需要 6 分钟。

题意：按顺序在坐标轴上画$n$个颜色为$1\cdots n$的矩形（数字大的颜色覆盖数字小的颜色），问最后能看到多少种颜色

先离散化，然后考虑扫描线+线段树

线段树每个节点用一个set存覆盖整个区间的颜色，$mx$表示之前未被看到并且能在这个区间看到的最大颜色，$mn$表示能在这个区间看到的最小颜色，那么修改时用儿子的对应信息和当前节点的set最大值更新信息即可

每次扫描线修改完后统计答案，不停地把根节点的$mx$加入答案（已被看到过）并更新线段树对应区间即可

注意坐标区间$[l,r]$转为实现时的区间是$[l,r-1]$！

#include
     
      #include
      
       #include
       #include
        
         using namespace std;set
         
          cov[800010];int mx[800010],mn[800010];bool vis[100010];void pushup(int x,bool f){	if(f)		mx[x]=mn[x]=0;	else{		mx[x]=max(mx[x<<1],mx[x<<1|1]);		mn[x]=min(mn[x<<1],mn[x<<1|1]);	}	if(!cov[x].empty()){		int g=*cov[x].rbegin();		if(!vis[g])			mx[x]=max(mx[x],g);		else			mn[x]=max(mn[x],g);	}	if(mn[x]>mx[x])mx[x]=0;}void modify(int L,int R,int v,int l,int r,int x){	if(L<=l&&r<=R){		if(v>0)			cov[x].insert(v);		else			cov[x].erase(-v);		return pushup(x,l==r);	}	int mid=(l+r)>>1;	if(L<=mid)modify(L,R,v,l,mid,x<<1);	if(mid
          
           <<1|1); pushup(x,0);}map
           
            px,py;map
            
             ::iterator it;struct rect{ int x1,y1,x2,y2;}r[100010];struct event{ int l,r,v; event(int a=0,int b=0,int c=0){l=a;r=b;v=c;}};vector
             
              e[200010];int main(){ int n,nx,ny,i,ans; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d%d%d%d",&r[i].x1,&r[i].y1,&r[i].x2,&r[i].y2); px[r[i].x1]=px[r[i].x2]=1; py[r[i].y1]=py[r[i].y2]=1; } for(nx=1,it=px.begin();it!=px.end();it++,nx++)it->second=nx; nx--; for(ny=1,it=py.begin();it!=py.end();it++,ny++)it->second=ny; ny--; for(i=1;i<=n;i++){ r[i].x1=px[r[i].x1]; r[i].x2=px[r[i].x2]; r[i].y1=py[r[i].y1]; r[i].y2=py[r[i].y2]-1; e[r[i].x1].push_back(event(r[i].y1,r[i].y2,i)); e[r[i].x2].push_back(event(r[i].y1,r[i].y2,-i)); } ans=0; for(i=1;i<=nx;i++){ for(event v:e[i])modify(v.l,v.r,v.v,1,ny,1); while(mx[1]){ vis[mx[1]]=1; ans++; modify(r[mx[1]].y1,r[mx[1]].y2,0,1,ny,1); } } printf("%d",ans+1);}

转载于:https://www.cnblogs.com/jefflyy/p/9130727.html

你可能感兴趣的文章