CodeForces 1084 F Max Mex
2024-08-28 20:06:24
题意：问在树上的所有路中mex值最大是多少。
题解：
用线段树维护值。
区间[L,R]意味着 区间[L,R]的数可不可以合并。
重点就是合并的问题了。
首先合法的区间只有3种：
1. 一个点。
2. 一条从上到下的线段 即 u->v u = lca(u,v)。
3.一条从下到上到下的线段 u -> p -> v p = lca(u,v)
1 和 1 可以直接合并， 合并之后可能成为 2 或者成为3。
1 和 2 合并的时候 可能变成 2 或者 3。 注意的是 1 往上爬的时候可能出现在 2 的中间位置而不是端点位置。
1 和 3 合并的之后 只会变成 3。并且 p 是不会变得，只有 u 和 v 会变。
2 和 2 合并的时候 可能保持2 也可以变成3。
2 和 3 合并的时候 只会保持3， 并且 p 一样不会边，只有u 和 v 会变。 1 3 合并的操作 和 2 3 合并的操作是一样的。
3 和 3 合并的时候 只会保持3， 还是p不会边， u 和 v 会变。
所以 根据前面说的 我们要记录的是 type， u， v， p，ok。
询问的时候，我们先问出[1,x]哪一段是合法的，然后再在右边去询问能不能把右边的并到[1,x]上。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 2e5 + ;
int anc[N][];
int v[N], deep[N];
vector<int> vc[N];
void dfs(int o){
for(int x : vc[o]){
deep[x] = deep[o]+;
anc[x][] = o;
for(int i = ; i < ; ++i) anc[x][i] = anc[anc[x][i-]][i-];
dfs(x);
}
}
int lca(int u, int v){
if(deep[u] > deep[v]) swap(u,v);
int k = deep[v] - deep[u];
for(int i = ; i >= ; --i){
if((k>>i)&) v = anc[v][i];
}
if(u == v) return u;
for(int i = ; i >= ; --i){
if(anc[u][i] != anc[v][i])
u = anc[u][i], v = anc[v][i];
}
return anc[u][];
}
int ok[N<<], pre[N<<], type[N<<], low[N<<][];
void Merge(int rt, int ls, int rs){
ok[rt] = ;
if(!ok[ls] || !ok[rs]) return;
if(pre[ls] == low[ls][] && pre[rs] == low[rs][]){
int fp = lca(pre[ls], pre[rs]);
ok[rt] = ; pre[rt] = fp;
if(fp == pre[ls] || fp == pre[rs]){
type[rt] = ;
if(fp == low[ls][]) low[rt][] = low[rs][];
else low[rt][] = low[ls][];
}
else {
type[rt] = ;
low[rt][] = pre[ls]; low[rt][] = pre[rs];
}
return ;
}
if(pre[ls] == low[ls][]) swap(ls, rs);
if(type[ls] == && type[rs] == && pre[rs] == low[rs][]){
int fp = lca(pre[ls], pre[rs]);
int sp = lca(low[ls][], low[rs][]);
pre[rt] = fp;
if(fp == sp){
if(fp == pre[rs]) {
ok[rt] = ; type[rt] = ;
low[rt][] = low[ls][];
}
else {
ok[rt] = ; type[rt] = ;
low[rt][] = low[ls][]; low[rt][] = low[rs][];
}
}
else if((fp == pre[ls] || fp == pre[rs]) && (sp == low[ls][]||sp == low[rs][])){
ok[rt] = ; type[rt] = ;
if(sp == low[ls][]) low[rt][] = low[rs][];
else low[rt][] = low[ls][];
}
return ;
}
if(type[ls] == && type[rs] == ){
int fp = lca(pre[ls], pre[rs]);
int sp = lca(low[ls][], low[rs][]);
pre[rt] = fp;
if(fp == sp){
type[rt] = ; ok[rt] = ;
low[rt][] = low[ls][]; low[rt][] = low[rs][];
}
else if((fp == pre[ls] || fp == pre[rs]) && (sp == low[ls][]||sp == low[rs][])){
ok[rt] = ; type[rt] = ;
if(sp == low[ls][]) low[rt][] = low[rs][];
else low[rt][] = low[ls][];
}
else ok[rt] = ;
return ;
}
if(type[ls] + type[rs] == ){
if(type[ls] == ) swap(ls, rs);
int fp = lca(pre[ls], pre[rs]);
if(fp != pre[rs]) ok[rt] = ;
else {
type[rt] = ; pre[rt] = fp;
int sp = lca(low[ls][], low[rs][]);
if(sp == low[ls][]){
low[rt][] = low[rs][]; low[rt][] = low[rs][];
ok[rt] = ;
return ;
}
if(sp == low[rs][]){
low[rt][] = low[ls][];
low[rt][] = low[rs][]; ok[rt] = ;
return ;
}
sp = lca(low[ls][], low[rs][]);
if(sp == low[ls][]){
low[rt][] = low[rs][]; low[rt][] = low[rs][];
ok[rt] = ;
return ;
}
if(sp == low[rs][]){
low[rt][] = low[rs][]; low[rt][] = low[ls][];
ok[rt] = ;
return ;
}
return ;
}
return ;
}
if(type[ls] + type[rs] == ){
type[rt] = ;
if(pre[ls] == pre[rs]){
pre[rt] = pre[ls];
int sp1 = lca(low[ls][], low[rs][]), sp2 = lca(low[ls][], low[rs][]);
if((sp1 == low[ls][] || sp1 == low[rs][]) && (sp2 == low[ls][] || sp2 == low[rs][])){
ok[rt] = ;
if(sp1 == low[ls][]) low[rt][] = low[rs][];
else low[rt][] = low[ls][];
if(sp2 == low[ls][]) low[rt][] = low[rs][];
else low[rt][] = low[ls][];
return ;
}
sp1 = lca(low[ls][], low[rs][]), sp2 = lca(low[ls][], low[rs][]);
if((sp1 == low[ls][] || sp1 == low[rs][]) && (sp2 == low[ls][] || sp2 == low[rs][])){
ok[rt] = ;
if(sp1 == low[ls][]) low[rt][] = low[rs][];
else low[rt][] = low[ls][];
if(sp2 == low[ls][]) low[rt][] = low[rs][];
else low[rt][] = low[ls][];
return ;
}
}
}
}
void Update(int L, int k, int l, int r, int rt){
if(l == r){
type[rt] = ok[rt] = ;
low[rt][] = pre[rt] = k;
return ;
}
int m = l+r >> ;
if(L <= m) Update(L, k, lson);
else Update(L, k, rson);
Merge(rt, rt<<, rt<<|);
}
void Copy(int aim, int f){
ok[aim] = ok[f]; pre[aim] = pre[f];
low[aim][] = low[f][]; low[aim][] = low[f][];
type[aim] = type[f];
}
int n, u;
int to = (<<)+, b = , ansr;
int Query(int l, int r, int rt){
if(ok[rt]){
if(b == ) {
b = to; ansr = r; Copy(b, rt);
return ;
}
Merge(to+, to, rt);
if(ok[to+]){
Copy(to, to+); ansr = r;
return ;
}
if(l != r){
int m = l+r >> ;
int k = Query(lson);
if(k == ) Query(rson);
}
return ;
}
int m = l+r >> ;
int k = Query(lson);
if(k == ) Query(rson);
return ;
}
int main(){
scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%d", &v[i]), v[i] += ;
for(int i = ; i <= n; ++i){
scanf("%d", &u);
vc[u].pb(i);
}
dfs();
for(int i = ; i <= n; ++i)
Update(v[i], i, , n, );
int q, op, l, r;
scanf("%d", &q);
while(q--){
scanf("%d", &op);
if(op == ){
scanf("%d%d", &l, &r); swap(v[l], v[r]);
Update(v[l], l, , n, ); Update(v[r], r, , n, );
}
else {
b = ; Query(,n,);
printf("%d\n", ansr);
}
}
return ;
}
最新文章
- UVA 10791 Minimum Sum LCM（分解质因数）
- Jmeter组件8. BeanShell Sampler
- SQL server 动态行转列
- js实现单文件以及多文件下载
- 【POJ 1679】The Unique MST（次小生成树）
- 点的双联通+二分图的判定（poj2942）
- 如何让你的Apache支持include文件解析和支持shtml的相关配置
- 文件上传下载struts2
- windows下搭建Nexus3私服和基于IDEA15的Maven学习笔记
- 与我们息息相关的internet服务(1)---域名服务
- T4 代码生成 Demo (抽奖程序)
- Oracle通过JOB定时执行存储过程实现两表数据比对
- 20165323 预备作业3 Linux安装及学习
- PHP常见错误提示含义解释
- javax.crypto.BadPaddingException: Given final block not properly padded解决方案
- 一个发送邮件的java类，包含多种发送方法
- 使用OpenCV通过摄像头捕获实时视频并探测人脸
- Tuscany glossary of terms
- JQuery事件e参数的方法preventDefault()取消默认行为
- 【源码学习之spark core 1.6.1 各种部署模式所使用的的TaskSceduler及SchedulerBackend】