(资料图片)
题目链接
挺有意思的数据结构题，题面看着像个板子，其实还是有不少学问的。
平面上一堆矩形的题目常见套路就是对\(x\)轴扫描线，\(y\)轴线段树维护，这题也不例外。我们先对坐标离散化。题目中输入的是坐标系中的顶点的坐标，为了方便维护，我们需要转换成"格子"的坐标。注意，是先离散化再转换，如果先转换再离散化会出现下面的错误：
然后从左到右扫描线，对于每一列，我们想找出这一列中所有最后仍存在、且没有被标记过的颜色，把它们计入答案，并把这些颜色都做上标记，以后不再统计。那么我们需要同时维护两堆东西：当前存在的所有颜色和当前存在的所有没标记过的颜色。一个没标记过的颜色应该被统计，当且仅当当前列存在一个位置被这个颜色覆盖，且覆盖这个位置的所有颜色中没有编号比这个颜色大的。假设现在往扫描线中加入一个颜色，它覆盖的纵坐标区间是[l,r]。我们平时做线段树区间修改[l,r]的时候会访问\(logn\)个不相交的区间，且它们的并为[l,r]。这题里我们对线段树上的每个区间维护一个set(f集合)，加入一个覆盖[l,r]的颜色时就把这个颜色加入所有访问到的\(logn\)个区间的set里。再对每个区间维护一个set表示所有没标记的颜色(g集合)，加入元素的时候和上一个set一样，如果标记了一个颜色就把这个set中的对应颜色都删了就行。
对于线段树上的某一个节点k，它的\(g\)集合里只有最大的一个元素可能计入答案。设这个元素为x，它能计入答案的充要条件是：从k到线段树根的所有节点的f集合的所有元素都\(\le x\)；且\(k\)子树中存在一个叶子\(p\)使得从\(p\)到\(k\)路径上所有节点的f集合中的所有元素都\(\le x\)。
然后对线段树中的每个点k维护\(mx_k\)表示它的子树中到现在为止满足上面说的所有条件的最大的可能被计入答案的值(在往上pushup的时候还要经受上方节点f集合中元素的考验)；\(mnlim_k\)表示子树中最优的叶子\(p\)(也就是p到k的路径上所有点f集合元素的最大值最小)。如果搞清楚了以上定义，如何pushup已经显然了。具体见代码。
时间复杂度\(O(nlog^2n)\)。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_back#define x1 x114#define y1 y114#define x2 x514#define y2 y514void fileio(){ #ifdef LGS freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif}void termin(){ #ifdef LGS std::cout<<"\n\nEXECUTION TERMINATED"; #endif exit(0);}using namespace std;void chmax(int &x,int y){if(x > op[200010];vector dscx,dscy;namespace st{ int n2=1,mx[800010],mnlim[800010]; set all[800010],cand[800010]; void pushUp(int k,bool isLeaf) { if(isLeaf) { if(cand[k].empty()) mx[k]=-1; else mx[k]=(*cand[k].rbegin()==*all[k].rbegin() ? *cand[k].rbegin():-1); if(all[k].empty()) mnlim[k]=-1;else mnlim[k]=*all[k].rbegin(); } else { int curlim=(all[k].empty() ? -1:*all[k].rbegin()); mnlim[k]=min(mnlim[k+k+1],mnlim[k+k+2]);chmax(mnlim[k],curlim); mx[k]=-1; if(mx[k+k+1]>=curlim) chmax(mx[k],mx[k+k+1]);if(mx[k+k+2]>=curlim) chmax(mx[k],mx[k+k+2]); if(!cand[k].empty()&&*cand[k].rbegin()>=mnlim[k]) chmax(mx[k],*cand[k].rbegin()); } } void upd(int k,int lb,int ub,int tlb,int tub,int w,int val) { if(ub>n; rep(i,n) { scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]); dscx.pb(x1[i]);dscx.pb(x2[i]);dscy.pb(y1[i]);dscy.pb(y2[i]); } sort(dscx.begin(),dscx.end());dscx.erase(unique(dscx.begin(),dscx.end()),dscx.end()); sort(dscy.begin(),dscy.end());dscy.erase(unique(dscy.begin(),dscy.end()),dscy.end()); rep(i,n) { x1[i]=lower_bound(dscx.begin(),dscx.end(),x1[i])-dscx.begin();x2[i]=lower_bound(dscx.begin(),dscx.end(),x2[i])-dscx.begin(); y1[i]=lower_bound(dscy.begin(),dscy.end(),y1[i])-dscy.begin();y2[i]=lower_bound(dscy.begin(),dscy.end(),y2[i])-dscy.begin(); --x2[i];--y2[i]; op[x1[i]].pb(mpr(mpr(y1[i],y2[i]),mpr(1,i))); op[x2[i]+1].pb(mpr(mpr(y1[i],y2[i]),mpr(-1,i))); } while(st::n2-1) { ++ans; int val=st::mx[0]; st::del(0,0,st::n2-1,y1[val],y2[val],val); } } cout< 
