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

CF983D Arkady and Rectangles

题目描述

解法

这种矩形覆盖的题一定要去想扫描线了，我们把矩形按 \(x\) 坐标排序，在某个 \(x\) 加入，在某个 \(x\) 删除。那么每次就只需要考虑 \(y\) 坐标了，维护 \(y\) 坐标可以用线段树。

下面的维护方法就有点神奇了，每次就考虑哪些颜色没有被覆盖，对于线段树的每个节点维护 \(mx[i]\) 表示 \(i\) 节点的区间内最大的没有被看见的眼色，\(mi[i]\) 表示在这个区间内如果要被看到颜色至少需要多大。再用一个 \(set\) 维护覆盖该区间的所有颜色，上传的方式是这样：

mx[o]=max(mx[o<<1],mx[o<<1|1]);mi[o]=min(mi[o<<1],mi[o<<1|1]);if(!s[o].empty()) return;int hh=*s[o].rbegin();mi[o]=max(hh,mi[o]);if(hh>mx[o]){	if(vis[hh] || hh

很简洁，但是很难想

代码实现还有一个小细节，离散化的时候假设端点为 \(x\)，把 \(x-1,x,x+1\) 都离散化一下。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int M = 600005;int read(){	int x=0,f=1;char c;	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}	return x*f;}int n,m,k,ans,mx[4*M],mi[4*M];set
       
         s[4*M];int vis[M],xl[M],xr[M],yl[M],yr[M],p[M];struct node{	int x,l,r,id;	bool operator < (const node &R) const	{		return x
        
         r || l>R) return ; if(L<=l && r<=R) { if(x>0) s[i].insert(x); else s[i].erase(-x); up(i,l,r); return ; } int mid=(l+r)>>1; ins(i<<1,l,mid,L,R,x); ins(i<<1|1,mid+1,r,L,R,x); up(i,l,r);}void upd(int i,int l,int r,int L,int R){ if(L>r || l>R) return ; if(L<=l && r<=R) {up(i,l,r);return ;} int mid=(l+r)>>1; upd(i<<1,l,mid,L,R); upd(i<<1|1,mid+1,r,L,R); up(i,l,r);}signed main(){ n=read(); for(int i=1;i<=n;i++) { xl[i]=read(); p[++k]=yl[i]=read(); p[++k]=yl[i]-1; p[++k]=yl[i]+1; xr[i]=read(); p[++k]=yr[i]=read()-1; p[++k]=yr[i]-1; p[++k]=yr[i]+1; } sort(p+1,p+1+k); k=unique(p+1,p+1+k)-p-1;//必须要这样 for(int i=1;i<=n;i++) { yl[i]=lower_bound(p+1,p+1+k,yl[i])-p; yr[i]=lower_bound(p+1,p+1+k,yr[i])-p; a[++m]=node{xl[i],yl[i],yr[i],i}; a[++m]=node{xr[i],yl[i],yr[i],-i}; } sort(a+1,a+1+m); for(int i=1,j;i<=m;i=j) { for(j=i;a[j].x==a[i].x;j++) { //printf("->%d %d %d\n",a[j].id,a[j].l,a[j].r); ins(1,1,k,a[j].l,a[j].r,a[j].id); } while(mx[1]) { int c=mx[1];ans++; //printf("%d %d %d\n",c,yl[c],yr[c]); vis[c]=1;//删除这个颜色 upd(1,1,k,yl[c],yr[c]);//区间更新一下 } } printf("%d\n",ans+1);}
        
       
      
     
    
   

Sunčanje

题目描述

解法

题目转移有亿点巧妙，我们去统计有多少编号大于他的矩形和他不交，如果都和他不交那么他就完全暴露在阳光下了。

这个统计就是一个容斥，我们把四边延长成九宫格然后统计 上\(/\)下\(/\)左\(/\)右 的答案之后，减去 左上\(/\)左下\(/\)右上\(/\)右下 的答案即可。

左上\(/\)左下\(/\)右上\(/\)右下 的计算需要三维偏序，所以写 \(cdq\) 分治就可以计算了。

CF650E Clockwork Bomb

题目描述

解法

这种题可以叫做树上的构造问题，那么一定要去考虑 \(dfs\) 的方式解决。

首先如果边 \((x,y)\) 在两棵树上都出现的话，我们尝试不动他，只改变那些不合法的边，如果能做到那么就是最少的方案数。

考虑在第一棵树上 \(dfs\)，那么每次 \(u\) 访问儿子 \(v\) 时我们就看 \((u,v)\) 这条边是否在第二棵树上出现过，如果没有出现过我们就要调整它，设第二棵树上的父亲为 \(f2\)，就可能会出现第一棵树上已经有了 \((u,f2)\) 这条边的情况，不能直接连。

但是这条边一定是有地方放的，我们考虑初始时在第一棵树上保留已经合法的边，而且父子关系用第二棵树上的，那么 \(u\) 连通块的根一定还没有连接，我们连接 \((rt,f2[rt])\) 这条边即可，如果 \(f2[rt]\) 在 \(u\) 祖先方向不会构成环，如果在儿子方向会不会构成环呢？因为 \(dfs\) 已经把儿子处的结构处理好了，所以现在放心的连是没问题的。

#include 
   
    #include 
    
     using namespace std;const int M = 500005;int read(){	int x=0,f=1;char c;	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}	return x*f;}int n,m,f1[M],f2[M],fa[M];vector
     
       g1[M],g2[M];struct node{	int a,b,c,d;}s[M];void dfs1(int u,int p){	f1[u]=p;	for(int i=0;i