传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=986
| WZJ的数据结构（八） |
| 难度级别：E； 运行时间限制：3000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
给你一个N个节点的森林，从1到N编号，每个点有权值。请你设计一个数据结构，进行以下两种操作： 1.修改：给你a、b、c，将a到b路径上所有点的权值改成c。 2.增加：给你a、b、c，将a到b路径上所有点的权值增加c。 3.询问：给你a、b，输出从a到b路径上经过所有点权值的最大值、最小值与权值和。 |
|
输入
|
|
第一行为一个正整数N。
接下来N-1行为每一条边，每行2个正整数a，b，表示有一条从a到b的边（从1开始编号）。 第N+1行为n个正整数Ai,表示每个点的开始权值。 第N+2行为一个正整数Q,表示Q次操作。 接下来Q行为每一次询问，每行3或4个正整数(t)、a、b、c。 若t=0表示修改，t=1表示增加，t=2表示查询。 |
|
输出
|
|
对于每一次询问，输出结果。
|
|
输入示例
|
|
5
1 2 1 3 2 5 5 4 1 3 2 3 5 5 2 1 5 2 3 4 0 3 5 2 1 1 4 1 2 3 4 |
|
输出示例
|
|
5 1 9
5 1 14 4 2 15 |
|
其他说明
|
|
1<=N<=100000
1<=Q<=100000 1<=Ai<=1000 1<=a,b<=N 1<=c<=1000 |
题解：树链剖分直接套上1010好了。。。
更新：指针的线段树+邻接表：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<=1;d++) if(ch[d])
#define lson x->ch[0],L,M
#define rson x->ch[1],M+1,R
using namespace std;
const int maxn=+,inf=-1u>>;
struct node{
node*ch[];int mx,mi,sm,set,add,siz;
node(){set=inf;add=;}
void init(int t){mi=mx=sm=t;return;}
void addt(int tag){
mi+=tag;mx+=tag;sm+=tag*siz;add+=tag;return;
}
void sett(int tag){
add=;mi=mx=set=tag;sm=siz*tag;return;
}
void update(){
mi=inf;mx=-inf;sm=;
CH{mi=min(mi,ch[d]->mi);mx=max(mx,ch[d]->mx);sm+=ch[d]->sm;}
return;
}
void down(){
if(set!=inf){CH{ch[d]->sett(set);}set=inf;}
if(add){CH{ch[d]->addt(add);}add=;}
return;
}
}seg[maxn<<],*nodecnt=seg,*root;
int A[maxn],n,Q,ql,qr,cv,tp,_mi,_mx,_sm;
void build(node*&x,int L,int R){
x=nodecnt++;
if(L==R) x->init(A[L]);
else{
int M=L+R>>;
build(lson);build(rson);
x->update();
} x->siz=R-L+;return;
}
void update(node*&x,int L,int R){
if(ql<=L&&R<=qr){
if(tp) x->addt(cv);
else x->sett(cv);
}else{
int M=L+R>>;
x->down();
if(ql<=M) update(lson);
if(qr>M) update(rson);
x->update();
} return;
}
void query(node*x,int L,int R){
if(ql<=L&&R<=qr){
_mi=min(_mi,x->mi);
_mx=max(_mx,x->mx);
_sm+=x->sm;
}else{
int M=L+R>>;
x->down();
if(ql<=M) query(lson);
if(qr>M) query(rson);
} return;
}
struct ted{int x,y;ted*nxt;}adj[maxn<<],*fch[maxn],*ms=adj;
void ade(int x,int y){
*ms=(ted){x,y,fch[x]};fch[x]=ms++;
*ms=(ted){y,x,fch[y]};fch[y]=ms++;
return;
}
int dep[maxn],p[maxn],son[maxn],top[maxn],siz[maxn],fa[maxn],cz=;
void dfs(int x){
siz[x]=;dep[x]=dep[fa[x]]+;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(v!=fa[x]){
fa[v]=x;dfs(v);siz[x]+=siz[v];
if(siz[son[x]]<siz[v]) son[x]=v;
}
} return;
}
void build(int x,int tp){
p[x]=++cz;top[x]=tp;
if(son[x]) build(son[x],tp);
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;
if(v!=fa[x]&&v!=son[x]) build(v,v);
} return;
}
void update(int x,int y){
int f1=top[x],f2=top[y];
while(f1!=f2){
if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);
ql=p[f1];qr=p[x];update(root,,n);
x=fa[f1];f1=top[x];
} if(dep[x]>dep[y]) swap(x,y);
ql=p[x];qr=p[y];update(root,,n);return;
}
void query(int x,int y){
int f1=top[x],f2=top[y];
while(f1!=f2){
if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);
ql=p[f1];qr=p[x];query(root,,n);
x=fa[f1];f1=top[x];
} if(dep[x]>dep[y]) swap(x,y);
ql=p[x];qr=p[y];query(root,,n);return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
void init(){
n=read();
for(int i=;i<n;i++) ade(read(),read());
dfs();build(,);
for(int i=;i<=n;i++) A[p[i]]=read();
build(root,,n);
return;
}
void work(){
Q=read();int x,y;
while(Q--){
tp=read();x=read();y=read();
if(tp!=) cv=read(),update(x,y);
else{
_mi=inf;_mx=-inf;_sm=;query(x,y);
write(_mx);PAU;write(_mi);PAU;write(_sm);ENT;
}
}
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
数组线段树：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxn3=+,inf=-1u>>;
struct Tedge{int x,y,next;}adj[maxn*];int ms=,fch[maxn];
int n,Q;
void AddEdge(int v,int u){
adj[++ms]=(Tedge){u,v,fch[u]};fch[u]=ms;
adj[++ms]=(Tedge){v,u,fch[v]};fch[v]=ms;
return;
}
int maxv[maxn3],minv[maxn3],sumv[maxn3],setv[maxn3],addv[maxn3],A[maxn];
void pushup(int o,int lc,int rc){
minv[o]=min(minv[lc],minv[rc]);
maxv[o]=max(maxv[lc],maxv[rc]);
sumv[o]=sumv[lc]+sumv[rc];
return;
}
void pushdown(int o,int lc,int rc){
if(setv[o]>=){
setv[lc]=setv[rc]=setv[o];
addv[lc]=addv[rc]=;
setv[o]=-;
} if(addv[o]){
addv[lc]+=addv[o];
addv[rc]+=addv[o];
addv[o]=;
} return;
}
void maintain(int o,int L,int R){
int lc=o<<,rc=lc|;
if(L<R&&setv[o]<) pushup(o,lc,rc);
if(setv[o]>=){
minv[o]=maxv[o]=setv[o];
sumv[o]=(R-L+)*setv[o];
} if(addv[o]){
minv[o]+=addv[o];
maxv[o]+=addv[o];
sumv[o]+=(R-L+)*addv[o];
} return;
}
int _min,_max,_sum,ql,qr,tp,cv;
void update(int o,int L,int R){
if(ql<=L&&R<=qr){
if(tp) addv[o]+=cv;
else setv[o]=cv,addv[o]=;
} else{
int M=L+R>>,lc=o<<,rc=lc|;
pushdown(o,lc,rc);
if(ql<=M) update(lc,L,M); else maintain(lc,L,M);
if(qr>M) update(rc,M+,R); else maintain(rc,M+,R);
} maintain(o,L,R);return;
}
void build(int o,int L,int R){
if(L==R) setv[o]=A[L];
else{
int M=L+R>>,lc=o<<,rc=lc|;
build(lc,L,M);build(rc,M+,R);
} maintain(o,L,R);return;
}
void query(int o,int L,int R,int add){
if(setv[o]>=){
int change=setv[o]+addv[o]+add;
_sum+=(min(R,qr)-max(L,ql)+)*change;
_min=min(_min,change);
_max=max(_max,change);
} else if(ql<=L&&R<=qr){
_sum+=sumv[o]+(R-L+)*add;
_min=min(_min,minv[o]+add);
_max=max(_max,maxv[o]+add);
} else{
int M=L+R>>,lc=o<<,rc=lc|;
if(ql<=M) query(lc,L,M,add+addv[o]);
if(M<qr) query(rc,M+,R,add+addv[o]);
} return;
}
int dep[maxn],siz[maxn],top[maxn],p[maxn],fa[maxn],son[maxn];
void dfs(int u){
siz[u]=;dep[u]=dep[fa[u]]+;
for(int i=fch[u];i;i=adj[i].next){
int v=adj[i].y;
if(v!=fa[u]){
fa[v]=u;dfs(v);
if(siz[son[u]]<siz[v]) son[u]=v;
siz[u]+=siz[v];
}
} return;
}
int cz=;
void build(int u,int tp){
p[u]=++cz;top[u]=tp;
if(son[u]) build(son[u],tp);
for(int i=fch[u];i;i=adj[i].next){
int v=adj[i].y;
if(v!=fa[u]&&v!=son[u]) build(v,v);
} return;
}
void query(int a,int b){
int f1=top[a],f2=top[b];
while(f1!=f2){
if(dep[f1]<dep[f2]) swap(a,b),swap(f1,f2);
ql=p[f1];qr=p[a];query(,,n,);
a=fa[f1];f1=top[a];
}
if(dep[a]>dep[b]) swap(a,b);
ql=p[a];qr=p[b];query(,,n,);return;
}
void update(int a,int b){
int f1=top[a],f2=top[b];
while(f1!=f2){
if(dep[f1]<dep[f2]) swap(a,b),swap(f1,f2);
ql=p[f1];qr=p[a];update(,,n);
a=fa[f1];f1=top[a];
}
if(dep[a]>dep[b]) swap(a,b);
ql=p[a];qr=p[b];update(,,n);return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
void init(){
memset(setv,-,sizeof(setv));
n=read();
for(int i=;i<n;i++) AddEdge(read(),read());
dfs();build(,);
for(int i=;i<=n;i++) A[p[i]]=read();//这么写跑的更快
build(,,n);
/*for(int i=1;i<=n;i++){//这样慢
ql=qr=p[i];cv=read();
update(1,1,n);
}*/
Q=read();
return;
}
void work(){
int a,b;
while(Q--){
tp=read();a=read();b=read();
if(tp==){//query
_sum=;_min=inf;_max=-inf;
query(a,b);
write(_max);PAU;write(_min);PAU;write(_sum);ENT;
} else cv=read(),update(a,b);
}
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
大数据跑LCT还是快：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,inf=-1u>>;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
struct node {
node *ch[],*fa;
bool rev;
int x,sm,siz,add,mi,mx,set;
inline void add_rev_tag(){
swap(ch[],ch[]);rev^=;return;
}
inline void add_plus_tag(int a){
sm+=siz*a;x+=a;add+=a;
if(mi!=inf) mi+=a;
if(mx!=-inf) mx+=a;
return;
}
inline void add_set_tag(int a){
x=set=a;add=;sm=a*siz;
if(mi!=inf) mi=set;
if(mx!=-inf) mx=set;
}
inline void down(){
if(rev){
if(ch[]) ch[]->add_rev_tag();
if(ch[]) ch[]->add_rev_tag();
rev=;
}
if(set){
if(ch[]) ch[]->add_set_tag(set);
if(ch[]) ch[]->add_set_tag(set);
set=;
}
if(add){
if(ch[]) ch[]->add_plus_tag(add);
if(ch[]) ch[]->add_plus_tag(add);
add=;
}
return;
}
inline void update(){
sm=;siz=;mi=inf;mx=-inf;
if(ch[]) sm+=ch[]->sm,siz+=ch[]->siz,mi=min(mi,ch[]->mi),mx=max(mx,ch[]->mx);
if(ch[]) sm+=ch[]->sm,siz+=ch[]->siz,mi=min(mi,ch[]->mi),mx=max(mx,ch[]->mx);
if(!x) return;
mi=min(x,mi);
mx=max(x,mx);
sm+=x;
return;
}
}lct[maxn];
inline int get_parent(node *x,node *&fa){return (fa=x->fa)?fa->ch[]==x?:fa->ch[]==x?:-:-;}
inline void rotate(node *x){
int t1,t2;
node *fa,*gfa;
t1=get_parent(x,fa);
t2=get_parent(fa,gfa);
if ((fa->ch[t1]=x->ch[t1^])) fa->ch[t1]->fa=fa;
x->ch[t1^]=fa;fa->fa=x;x->fa=gfa;
if (t2!=-) gfa->ch[t2]=x;
fa->update();return;
}
inline void pushdown(node *x){
static node *stack[maxn];
int cnt=;
while(){
stack[cnt++]=x;
node *fa=x->fa;
if (!fa || (fa->ch[]!=x && fa->ch[]!=x)) break;
x=fa;
}
while(cnt--) stack[cnt]->down();
return;
}
inline node * splay(node *x){
pushdown(x);
while(){
int t1,t2;
node *fa,*gfa;
t1=get_parent(x,fa);
if(t1==-) break;
t2=get_parent(fa,gfa);
if(t2==-){
rotate(x);break;
} else if (t1==t2){
rotate(fa);rotate(x);
} else{
rotate(x);rotate(x);
}
}
x->update();
return x;
}
inline node * access(node *x){
node *ret=NULL;
while (x) splay(x)->ch[]=ret,(ret=x)->update(),x=x->fa;
return ret;
}
inline void makeroot(int x){access(lct+x)->add_rev_tag();}
inline void link(int u,int v){
makeroot(u);splay(lct+u)->fa=lct+v;return;
}
inline void cut(int u,int v){
makeroot(u);
node *p=(access(lct+v),splay(lct+v));
p->ch[]->fa=NULL;
p->ch[]=NULL;
p->update();
}
int n,q;
int main(){
n=read();
int i;
for(i=;i<=n;i++){
lct[i].x=lct[i].sm=;
lct[i].siz=;
lct[i].add=;
lct[i].mi=inf;
lct[i].mx=-inf;
lct[i].set=;
}
for(i=;i<n;i++){
int u,v;
u=read();v=read();
link(u,v);
}
for(int i=;i<=n;i++){
lct[i].x=read();lct[i].update();
}
q=read();
int x,y,c;
while(q--){
c=read();x=read();y=read();
if(c==) makeroot(x),access(y+lct)->add_set_tag(read());
else if(c==) makeroot(x),access(y+lct)->add_plus_tag(read());
else{
makeroot(x);node*t=access(y+lct);splay(t);
write(t->mx);PAU;write(t->mi);PAU;write(t->sm);ENT;
}
}
return ;
}
搜索
复制