LP3313 [SDOI2014]旅行 [动态开点线段树]
存个板子。。
Problem
咕咕咕
Solution
这次线段树是用指针写的...
写法倒挺像主席树的...
差点就写成傻逼了因此还是过来存个板子...
至于主席树能不能做,因为主席树记录到根的前缀和是要整体重构的,所以对操作分块重构应该是可行的
不过算一下复杂度 $O(n\sqrt{n}\log{1e4})$ 显然应该是个错的....
Code
// Code by ajcxsu
// Problem: traveller
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10, M=2e5+10;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
const int MM=4e6;
struct Node *nil;
struct Node {
Node *ls, *rs;
int s, m;
void pup() {
s=ls->s+rs->s;
m=max(ls->m, rs->m);
}
} *rt[N], po[MM], *pp=po;
void ini() {
nil=pp++, nil->ls=nil->rs=nil, nil->s=0, nil->m=-0x3f3f3f3f;
fill(rt, rt+N, nil);
}
void updata(Node *&x, int l, int r, int d, int v) {
if(x==nil) x=pp++, *x=*nil;
if(l==r) { x->s=v, x->m=v?v:-0x3f3f3f3f; return; }
int mid=(l+r)>>1;
if(d<=mid) updata(x->ls, l, mid, d, v);
else updata(x->rs, mid+1, r, d, v);
x->pup();
}
int querys(Node *x, int l, int r, int xl, int xr) {
if(xl<=l && r<=xr) return x->s;
int mid=(l+r)>>1, ret=0;
if(xl<=mid) ret+=querys(x->ls, l, mid, xl, xr);
if(xr>mid) ret+=querys(x->rs, mid+1, r, xl, xr);
return ret;
}
int querym(Node *x, int l, int r, int xl, int xr) {
if(xl<=l && r<=xr) return x->m;
int mid=(l+r)>>1, ret=-0x3f3f3f3f;
if(xl<=mid) ret=querym(x->ls, l, mid, xl, xr);
if(xr>mid) ret=max(ret, querym(x->rs, mid+1, r, xl, xr));
return ret;
}
int c[N], w[N], dfn[N], dep[N], fa[N], son[N], top[N], siz[N], idx;
int n, q;
void dfs1(int x=1, int k=1) {
dep[x]=k, siz[x]=1;
for(int u=h[x];u;u=nexp[u])
if(!dep[to[u]]) {
fa[to[u]]=x, dfs1(to[u], k+1), siz[x]+=siz[to[u]];
if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
}
}
void dfs2(int x=1, int t=1) {
dfn[x]=++idx, top[x]=t, updata(rt[c[x]], 1, n, dfn[x], w[x]);
if(son[x]) dfs2(son[x], t);
for(int u=h[x];u;u=nexp[u])
if(!dfn[to[u]]) dfs2(to[u], to[u]);
}
int paths(int s, int t) {
Node *nd=rt[c[s]];
int ret=0;
while(top[s]!=top[t]) {
if(dep[top[s]]<dep[top[t]]) swap(s, t);
ret+=querys(nd, 1, n, dfn[top[s]], dfn[s]);
s=fa[top[s]];
}
if(dep[s]>dep[t]) swap(s, t);
return ret+querys(nd, 1, n, dfn[s], dfn[t]);
}
int pathm(int s, int t) {
Node *nd=rt[c[s]];
int ret=-0x3f3f3f3f;
while(top[s]!=top[t]) {
if(dep[top[s]]<dep[top[t]]) swap(s, t);
ret=max(ret, querym(nd, 1, n, dfn[top[s]], dfn[s]));
s=fa[top[s]];
}
if(dep[s]>dep[t]) swap(s, t);
return max(ret, querym(nd, 1, n, dfn[s], dfn[t]));
}
int main() {
ios::sync_with_stdio(false), ini();
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>w[i]>>c[i];
int u, v;
for(int i=1;i<n;i++) cin>>u>>v, ins(u, v), ins(v, u);
dfs1(), dfs2();
char com[3];
while(q--) {
cin>>com>>u>>v;
if(com[0]=='C') {
if(com[1]=='C') updata(rt[c[u]], 1, n, dfn[u], 0), updata(rt[c[u]=v], 1, n, dfn[u], w[u]);
else updata(rt[c[u]], 1, n, dfn[u], w[u]=v);
}
else {
if(com[1]=='S') cout<<paths(u, v)<<endl;
else cout<<pathm(u, v)<<endl;
}
}
return 0;
}
本文链接:https://pst.iorinn.moe/archives/sol-luogu-3313.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆