bzoj 1036 (나무 사슬 분할)
10340 단어 데이터 구조
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include
#include
#include
#include
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
typedef long long ll;
const int maxn=30004;
const ll INF=1000000007;
int head[maxn],des[maxn<<1],nxt[maxn<<1],edge=0;
int top[maxn],dep[maxn],fa[maxn],son[maxn],siz[maxn],tid[maxn],rk[maxn],tim=0;
ll sum[maxn<<2],maxx[maxn<<2],num[maxn];
int n,m,q;
inline void adde(int u,int v) {
des[edge]=v,nxt[edge]=head[u],head[u]=edge++;
des[edge]=u,nxt[edge]=head[v],head[v]=edge++;
}
inline void dfs1(int p,int father,int d) {
dep[p]=d,fa[p]=father,siz[p]=1;
for (int i=head[p];i!=-1;i=nxt[i]) {
int v=des[i];
if (v==father) continue;
dfs1(v,p,d+1);
siz[p]+=siz[v];
if (son[p]==-1||siz[v]>siz[son[p]])
son[p]=v;
}
}
inline void dfs2(int p,int tp) {
top[p]=tp,tid[p]=++tim,rk[tid[p]]=p;
if (son[p]==-1) return ;
dfs2(son[p],tp);
for (int i=head[p];i!=-1;i=nxt[i]) {
int v=des[i];
if (v!=fa[p]&&v!=son[p])
dfs2(v,v);
}
}
inline void pushup(int rt) {
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);
}
inline void build(int l,int r,int rt) {
if (l==r) {sum[rt]=maxx[rt]=num[rk[l]];return ;}
int mid=(l+r)>>1;
build(lson),build(rson);
pushup(rt);
}
inline void modify(int l,int r,int rt,int pos,ll val) {
if (l==r) {sum[rt]=maxx[rt]=val;return ;}
int mid=(l+r)>>1;
if (pos<=mid) modify(lson,pos,val);
else modify(rson,pos,val);
pushup(rt);
}
inline ll query_max(int l,int r,int rt,int L,int R) {
if (L<=l&&r<=R) return maxx[rt];
int mid=(l+r)>>1;ll res=-INF;
if (L<=mid) res=max(res,query_max(lson,L,R));
if (midreturn res;
}
inline ll query_sum(int l,int r,int rt,int L,int R) {
if (L<=l&&r<=R) return sum[rt];
int mid=(l+r)>>1;ll res=0;
if (L<=mid) res+=query_sum(lson,L,R);
if (midreturn res;
}
inline ll get_max(int x,int y) {
ll res=-INF;
while (top[x]!=top[y]) {
if (tid[top[x]]//tid dep
res=max(res,query_max(root,tid[top[x]],tid[x]));
x=fa[top[x]];
}
if (tid[x]>tid[y]) swap(x,y);//tid dep
return max(res,query_max(root,tid[x],tid[y]));
}
inline ll get_sum(int x,int y) {
ll res=0;
while (top[x]!=top[y]) {
if (tid[top[x]]//tid dep
res+=query_sum(root,tid[top[x]],tid[x]);
x=fa[top[x]];
}
if (tid[x]>tid[y]) swap(x,y);//tid dep
res+=query_sum(root,tid[x],tid[y]);
return res;
}
int main() {
freopen("bzoj 1036.in","r",stdin);
memset(head,-1,sizeof(head));
memset(son,-1,sizeof(son));
scanf("%d",&n);
for (register int i=1;iint u,v;
scanf("%d%d",&u,&v);
adde(u,v);
}
dfs1(1,0,1);
dfs2(1,1);
for (register int i=1;i<=n;++i) scanf("%lld",&num[i]);
build(root);
scanf("%d",&q);
while (q--) {
char ss[10];
int pos,L,R;
ll val;
scanf("%s",ss);
if (ss[0]=='C') {
scanf("%d%lld",&pos,&val);
modify(root,tid[pos],val);
}
else {
scanf("%d%d",&L,&R);
if (ss[1]=='M') printf("%lld
",get_max(L,R));
else printf("%lld
",get_sum(L,R));
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.