标签：关键点   这一   line   fir   一个   inline   fine   sdi   排序   

「APIO2019」路灯 (K-D Tree / 树套树 / CDQ + 树状数组)

首先想到一个简单的问题转化

对于一个询问，联通的时间是若干连续的区间\([L_i,R_i]\)

所有的\(L_i,R_i+1\)都是关键点，即由不连通变为联通的时间 和 由联通变为不连通的时间

把答案转化为\(\sum R_i+1-L_i\)即可

问题转化为对于当前的操作，找到它是那些询问的关键点

如果是合并操作，被合并的两个区间之间变得联通

如果是分裂操作，裂开的两个区间之间不再联通

可以用set维护上述区间，发现每次被更新的值都是一个二维区间

算上时间这一维，问题转化为一个类 三维偏序问题，但是题限制了内存

Part1 K-D Tree

限制了内存，很容易想到直接K-D Tree，实际运行也比较优秀

注意可以把要询问的点拿出来建出K-D Tree，每次区间修改即可

时间复杂度\(O(n\sqrt n)\)，空间复杂度\(O(n)\)

#include
using namespace std;
#define rep(i,a,b) for(int i=a,i##end=b;i Pii;
#define mp make_pair
void cmin(int &a,int b){ ((a>b)&&(a=b)); }
void cmax(int &a,int b){ ((a > st,tmp;
struct Node{ int x,y; } A[N];
int cmp1(Node a,Node b){ return mp(a.x,a.y)r) return 0;
	int u=(l+r)>>1;
    nth_element(A+l,A+u,A+r+1,d?cmp2:cmp1);
	ch[u][0]=Build(l,u-1,d^1),ch[u][1]=Build(u+1,r,d^1);
	lx[u]=rx[u]=A[u].x,ly[u]=ry[u]=A[u].y;
	for(int i:ch[u]) if(i) cmin(lx[u],lx[i]),cmin(ly[u],ly[i]),cmax(rx[u],rx[i]),cmax(ry[u],ry[i]);
	return u;
}

void Upd(int x1,int x2,int y1,int y2,int u,int x) {
	if(!u || x1>rx[u] || x2ry[u] || y2first,r=it->second;
				st.erase(it);
				st.insert(mp(l,x)),st.insert(mp(x+1,r));
				Upd(l,x,x+1,r,rt,i);
			} else {
				auto it=st.upper_bound(mp(x,INF)),tmp=it; it--;
				int l=it->first,r=tmp->second; 
				st.erase(it),st.erase(tmp);
				st.insert(mp(l,r)),Upd(l,x,x+1,r,rt,-i);
			}
			col[x]^=1;
		} else {
			int ans=Que((Node){a[i],b[i]},rt);
			auto it=st.upper_bound(mp(a[i],INF)); it--;
			if(it->second>=b[i]) ans+=i;
			printf("%d\n",ans);
		}
	}
}

Part2 树套树(没有代码)

由于已知查询的节点，树套树的内存可以优化到\(O(n\log n)\)

把要询问的点拉出来，每次询问在第二维中有\(\log n\)次单点查询，所以需要被查询的位置一共只有\(n\log n\)个

把这些会被查询的位置拿出来建成\(n\)棵静态的线段树，更新就直接在这些静态的线段树上区间更新即可

时间复杂度\(O(n\log ^2 n)\)，空间复杂度\(O(n\log n)\)

Part3 CDQ+树状数组

是常规写法，不会被限制内存

CDQ一维，排序一维，树状数组一维，参见三维偏序

「APIO2019」路灯 (K-D Tree / 树套树 / CDQ + 树状数组)

标签：关键点   这一   line   fir   一个   inline   fine   sdi   排序   

原文地址：https://www.cnblogs.com/chasedeath/p/13380269.html