【CF1083C】Max Mex（LCA，ST表，树上路径并，线段树二分）_随笔

【CF1083C】Max Mex（LCA，ST表，树上路径并，线段树二分）题面

给定一棵有 n n n 个点的树，每个节点有点权。所有的点权构成了一个 0 ∼ n − 1 0~sim~n - 1 0 ∼ n−1 的排列。有 q q q 次 *** 作，每次 *** 作 1 1 1 为交换两个点的点权， *** 作 2 2 2 为查询 M e x ( l ) Mex(l) Mex(l) 值最大的 M e x ( l ) Mex(l) Mex(l) 值，其中 l l l 是树上的一条路径。定义一条路径 l l l 的 M e x Mex Mex 值 M e x ( l ) Mex(l) Mex(l) 为这条路径上最小的没有出现过的自然数。

n , q ≤ 2 × 1 0 5 n,qleq 2times10^5 n,q≤2×105 .

题解

这道题思路不难，最大 Mex 可以翻译成：最大的 r r r 满足权值在 [ 0 , r ) [0,r) [0,r) 以内的点被一条简单路径覆盖。

于是我们可以对每个前缀 [ 0 , r ) [0,r) [0,r) 维护路径并，若发现并出来的不是条链，那么从此标记为不合法，后面就不用再合并了。我们可以把两条路径的最多 4 个点建一棵虚树，判断是否是条链，以及链的两端是什么。

为了快速地在路径并中得到 LCA，我们需要用欧拉序 + RMQ，用 ST表光速查找 LCA 。这样路径合并就是 O ( 1 ) O(1) O(1) 的了。

为了维护前缀路径并，我们能否让每个点存一条到权值 0 的路径呢？当然不行，因为权值 0 的点可能会改。那么我们单点就存一条当前权值到前一个权值的点，这样修改 *** 作数就是 O ( 1 ) O(1) O(1) 的了。

最后在线段树上二分就好了，时间复杂度 O ( n log ⁡ n ) O(nlog n) O(nlogn) ，常数略大。

CODE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN 200005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second 
int xchar() {
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
#define getchar() xchar()
LL read() {
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}

const int MOD = 1000000007;
int n,m,s,o,k;
int hd[MAXN],nx[MAXN<<1],v[MAXN<<1],cne;
void ins(int x,int y) {
	nx[++ cne] = hd[x]; v[cne] = y; hd[x] = cne;
}
int d[MAXN],fa[MAXN],dfn[MAXN],id[MAXN<<1],tim;
int dp[MAXN<<1][20],lo[MAXN<<1]; // 19
int mxp(int a,int b) {return d[a] < d[b] ? a:b;}
int LCA(int a,int b) {
	int l = dfn[a],r = dfn[b]; if(l>r) swap(l,r);
	int lgo = lo[r-l+1];
	return mxp(dp[l][lgo],dp[r-(1<>1]+1,dp[i][0] = id[i];
	for(int j = 1;j <= 19;j ++) {
		for(int i = 1;i+(1< dfn[b])swap(a,b);}
}tre[MAXN<<2];
it merg(it x,it y) {
	if(!x.a) return y;
	if(!y.a) return x;
	if(x.a < 0 || y.a < 0) return it(-1,-1);
	int st[5]; int llc = LCA(LCA(x.a,x.b),LCA(y.a,y.b));
	st[0] = dfn[x.a],st[1] = dfn[x.b];
	st[2] = dfn[y.a],st[3] = dfn[y.b];
	st[4] = dfn[llc]; sort(st,st+5);
	int hd = st[0],ed = st[4];
	int ct = 0;
	for(int i = 1;i < 5;i ++) {
		int lc = dfn[LCA(id[st[i-1]],id[st[i]])];
		if(lc != st[i-1] && lc != st[i]) {
			if(lc == dfn[llc]) ct ++,hd = st[i-1];
			else return it(-1,-1);
		}
	}
	if(ct > 1) return it(-1,-1);
	return it(id[hd],id[ed]);
}
int M;
void maketree(int n) {
	M=1;while(M 0;i --) tre[i] = merg(tre[i<<1],tre[i<<1|1]);
}
void addtree(int x,it y) {
	int s=M+x; tre[s] = y; s >>= 1;
	while(s) tre[s] = merg(tre[s<<1],tre[s<<1|1]),s >>= 1;
}
int solve() {
	int s = 1; it as = it();
	while(s					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5718915.html

【CF1083C】Max Mex（LCA，ST表，树上路径并，线段树二分）

发表评论

评论列表（0条）