• 【luogu P7518】宝石(主席树)(二分)


    宝石

    题目链接:luogu P7518

    题目大意

    给你一棵树,树上每个点有颜色,然后给你一个颜色序列,保证序列上没有一样的颜色。
    然后多次操作每次问你树上的一条路径,要你找到一个最大的 k 使得给你的树上序列的子序列中存在 1~k 的颜色序列。

    思路

    解决历史性遗留问题了属于是。
    (几年前考场不会写的题,现在终于改了)


    首先拆成向上和向下两条路径(注意不要有点交集,LCA 那个地方我放在了向上)

    首先观察到一个特别的点,就是给出的颜色序列不会有颜色出现多次。
    什么意思呢,那对于每个颜色,它如果是你当前要找的颜色,它要的下一个颜色是固定的。
    所以我们完全可以试着维护一个数组 l s t lst lst 表示你要的第 i i i 个颜色上一次出现在哪里,然后每个位置都弄这么一个。

    每个都弄一个其实不可以但是我们先不管他,而且显然是可以用继承的方法得到。
    那有了这个数组,我们考虑每个点维护一个线段树,如果当前点是第 i i i 个你要的宝石,那第 j j j 个位置就是放着你从 i ∼ j i\sim j ij,你往上走,找到这一串子序列的最大深度。
    那每个点都维护一个线段树,但是不难发现可以继承,你就从要的上一个颜色继承过来,然后维护一下当前位置的深度即可。
    (注意这里是向上的所以应该是从下一个颜色继承过来)

    然后至于询问,因为要的颜色都是从第 1 1 1 个开始,而且答案显然会单调,所以你可以直接在线段树上找最后一个深度大于等于你 LCA 的深度的即可。


    接着是向下,感觉也可以用线段树来弄,那这次就是从上一个颜色继承过来了。
    但是发现询问的地方会有小小的问题,就是你起点是不确定的。
    那你考虑二分一个终点,然后看往前最多能拿多少(就把序列反过来拿),然后看是否跟之前的答案能拼出一个完整的。

    (询问记得特判如果往下的一段只有 LCA 而由于我们 LCA 固定在往上了,所以就不用往下直接用往上的答案即可

    代码

    #include
    #include
    #include
    
    using namespace std;
    
    const int N = 2e5 + 100;
    const int M = 5e4 + 100;
    int n, m, c, P[N], p[N], w[N], q, ans[N], Lca[N];
    int fa[N][21], deg[N];
    vector <int> G[N], nx[N], ny[N];
    
    int re, zf; char ch;
    int read() {
    	re = 0; zf = 1; ch = getchar();
    	while (ch < '0' || ch > '9') {
    		if (ch == '-') zf = -zf;
    		ch = getchar();
    	}
    	while (ch >= '0' && ch <= '9') {
    		re = (re << 3) + (re << 1) + ch - '0';
    		ch = getchar();
    	}
    	return re * zf;
    }
    
    void dfs0(int now, int father) {
    	fa[now][0] = father; for (int i = 1; i <= 20; i++) fa[now][i] = fa[fa[now][i - 1]][i - 1];
    	deg[now] = deg[father] + 1;
    	for (int i = 0; i < G[now].size(); i++) { int x = G[now][i];
    		if (x == father) continue; dfs0(x, now);
    	}
    }
    
    int LCA(int x, int y) {
    	if (deg[x] < deg[y]) swap(x, y);
    	for (int i = 20; i >= 0; i--) if (deg[fa[x][i]] >= deg[y]) x = fa[x][i];
    	if (x == y) return x;
    	for (int i = 20; i >= 0; i--) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    	return fa[x][0];
    }
    
    const int Ns = N << 6;
    int rt[N];
    struct XD_tree {
    	int ls[Ns], rs[Ns], val[Ns], tot;
    	
    	int copy(int now) {
    		int re = ++tot; ls[re] = ls[now]; rs[re] = rs[now]; val[re] = val[now]; return re;
    	}
    	
    	void change(int &now, int l, int r, int pl, int va) {
    		now = copy(now); val[now] = max(val[now], va);
    		if (l == r) return ; int mid = (l + r) >> 1;
    		if (pl <= mid) change(ls[now], l, mid, pl, va);
    			else change(rs[now], mid + 1, r, pl, va);
    	}
    	
    	int ask_0(int now, int l, int r, int k) {//往上(顺序 
    		if (!now || val[now] < k) return 0;
    		if (l == r) return l;
    		int mid = (l + r) >> 1;
    		if (val[rs[now]] < k) return ask_0(ls[now], l, mid, k);
    			else return ask_0(rs[now], mid + 1, r, k);
    	}
    	
    	int ask_1(int now, int l, int r, int k) {//往下(逆序 
    		if (!now || val[now] < k) return c + 1;
    		if (l == r) return l;
    		int mid = (l + r) >> 1;
    		if (val[ls[now]] < k) return ask_1(rs[now], mid + 1, r, k);
    			else return ask_1(ls[now], l, mid, k);
    	}
    	
    	void clear() {
    		for (int i = 1; i <= tot; i++) ls[i] = rs[i] = val[i] = 0;
    		tot = 0; for (int i = 1; i <= n; i++) rt[i] = 0;
    	}
    }T;
    
    int lst[M];
    void work_up(int now, int father) {
    	int tmp = -1, col = p[w[now]];
    	if (p[w[now]]) {
    		tmp = lst[col]; lst[col] = now;
    		rt[now] = rt[lst[col + 1]]; T.change(rt[now], 1, c, col, deg[now]);
    	}
    	
    	for (int i = 0; i < nx[now].size(); i++) { int id = nx[now][i];
    		ans[id] = T.ask_0(rt[lst[1]], 1, c, deg[Lca[id]]);
    	}
    	
    	for (int i = 0; i < G[now].size(); i++) { int x = G[now][i];
    		if (x == father) continue; work_up(x, now);
    	}
    	if (tmp != -1) lst[col] = tmp;
    }
    
    void work_down(int now, int father) {
    	int tmp = -1, col = p[w[now]];
    	if (p[w[now]]) {
    		tmp = lst[col]; lst[col] = now;
    		rt[now] = rt[lst[col - 1]]; T.change(rt[now], 1, c, col, deg[now]);
    	}
    	
    	for (int i = 0; i < ny[now].size(); i++) { int id = ny[now][i];
    		if (now == Lca[id]) continue;
    		int l = ans[id] + 1, r = c, re = ans[id];
    		while (l <= r) {
    			int mid = (l + r) >> 1;
    			if (T.ask_1(rt[lst[mid]], 1, c, deg[Lca[id]] + 1) <= ans[id] + 1) re = mid, l = mid + 1;
    				else r = mid - 1;
    		} 
    		ans[id] = re;
    	}
    	
    	for (int i = 0; i < G[now].size(); i++) { int x = G[now][i];
    		if (x == father) continue; work_down(x, now);
    	}
    	if (tmp != -1) lst[col] = tmp;
    }
    
    int main() {
    	n = read(); m = read(); c = read();
    	for (int i = 1; i <= c; i++) P[i] = read(), p[P[i]] = i;
    	for (int i = 1; i <= n; i++) w[i] = read();
    	for (int i = 1; i < n; i++) {
    		int x = read(), y = read();
    		G[x].push_back(y); G[y].push_back(x);
    	}
    	
    	dfs0(1, 0);
    	
    	q = read();
    	for (int i = 1; i <= q; i++) {
    		int s = read(), t = read();
    		Lca[i] = LCA(s, t);
    		nx[s].push_back(i); ny[t].push_back(i);
    	}
    	
    	work_up(1, 0);
    	T.clear();
    	work_down(1, 0);
    	
    	for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    	
    	return 0;
    } 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
  • 相关阅读:
    【树莓派】项目中找不到第三方库的问题
    使用drawio的图层构建更强大的图表
    【开源】物联网智慧消防云平台系统,前后端分离,微服务框架带文档,源码分享
    html动态新增div元素
    【2024年5月备考新增】】 考前篇(6)《案例分析知识点(2)- 范围管理》
    SpringCloud理解篇
    pmp是什么意思啊?
    算法-递归
    068:mapboxGL绘制多边形,过滤获取选中的点的集合信息
    VVC系列(一)VTM下载编译
  • 原文地址:https://blog.csdn.net/weixin_43346722/article/details/126633401