【BZOJ4034】【HAOI2015】T2 – 徐亦轲的博客

我只是来学区间修改区间查询的ZKW线段树的

大概就是每次修改和查询之前把两端点到根节点上的标记下传一下

// <4034.cpp> - 09/02/16 19:07:09
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=100010;
const int MAXM=200010;
const int INF=1e9;
int bt,b[MAXN],next[MAXM],to[MAXM];
inline void add(int x,int y){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;
}
int lb[MAXN<<2];
int tot,a[MAXN],f[MAXN],son[MAXN],top[MAXN],id[MAXN],size[MAXN],end[MAXN];
void dfs1(int x){
    size[x]=1;
    for(int i=b[x];i;i=next[i]){
        if(to[i]==f[x])continue;
        f[to[i]]=x;
        dfs1(to[i]);
        size[x]+=size[to[i]];
        if(size[to[i]]>size[son[x]])son[x]=to[i];
    }
}
void dfs2(int x,int t){
    top[x]=t;
    id[x]=++tot;
    if(son[x])dfs2(son[x],t);
    for(int i=b[x];i;i=next[i]){
        if(to[i]==f[x]||to[i]==son[x])continue;
        dfs2(to[i],to[i]);
    }
    end[x]=tot;
}
int K;
lol val[MAXN<<2],lazy[MAXN<<2];
int st[MAXN];
inline void update(int x){val[x]=val[x<<1]+val[x<<1|1];}
inline void pushdown(int x){
    int t=0;
    for(x>>=1;x;x>>=1)st[++t]=x;
    lol len=K>>1;
    for(int i=t;i;i--,len>>=1){
        if(!lazy[st[i]])continue;
        val[st[i]<<1]+=len*lazy[st[i]];
        val[st[i]<<1|1]+=len*lazy[st[i]];
        lazy[st[i]<<1]+=lazy[st[i]];
        lazy[st[i]<<1|1]+=lazy[st[i]];
        lazy[st[i]]=0;
    }
}
void mod(int l,int r,int x){
    int ll=l=K+l-1,rr=r=K+r+1;
    pushdown(ll);pushdown(rr);
    lol len=1;
    for(;l^r^1;l>>=1,r>>=1,len<<=1){
        if(~l&1)val[l^1]+=x*len,lazy[l^1]+=x;
        if( r&1)val[r^1]+=x*len,lazy[r^1]+=x;
    }
    for(ll>>=1;ll;ll>>=1)update(ll);
    for(rr>>=1;rr;rr>>=1)update(rr);
}
lol query(int l,int r){
    pushdown(l=K+l-1);pushdown(r=K+r+1);
    lol res=0;
    for(;l^r^1;l>>=1,r>>=1){
        if(~l&1)res+=val[l^1];
        if( r&1)res+=val[r^1];
    }
    return res;
}
lol ask(int x){
    lol res=0;
    for(;x;x=f[top[x]])res+=query(id[top[x]],id[x]);
    return res;
}
int main(){
    int n=gi(),m=gi();
    for(int i=1;i<=n;i++)a[i]=gi();
    for(int i=1;i<n;i++)add(gi(),gi());
    dfs1(1);
    dfs2(1,1);
    for(int i=2;i<=n<<2;i++)lb[i]=lb[i>>1]+1;
    K=2<<lb[n+1];
    for(int i=1;i<=n;i++)val[K+id[i]]=a[i];
    for(int i=K-1;i;i--)update(i);
    while(m--){
        int tp=gi(),x=gi();
        if(tp==1)mod(id[x],id[x],gi());
        else if(tp==2)mod(id[x],end[x],gi());
        else printf("%lld\n",ask(x));
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

// <4034.cpp> - 09/02/16 19:07:09

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=100010;

const int MAXM=200010;

const int INF=1e9;

int bt,b[MAXN],next[MAXM],to[MAXM];

inline void add(int x,int y){

next[++bt]=b[x];b[x]=bt;to[bt]=y;

next[++bt]=b[y];b[y]=bt;to[bt]=x;

}

int lb[MAXN<<2];

int tot,a[MAXN],f[MAXN],son[MAXN],top[MAXN],id[MAXN],size[MAXN],end[MAXN];

void dfs1(int x){

size[x]=1;

for(int i=b[x];i;i=next[i]){

if(to[i]==f[x])continue;

f[to[i]]=x;

dfs1(to[i]);

size[x]+=size[to[i]];

if(size[to[i]]>size[son[x]])son[x]=to[i];

}

void dfs2(int x,int t){

top[x]=t;

id[x]=++tot;

if(son[x])dfs2(son[x],t);

for(int i=b[x];i;i=next[i]){

if(to[i]==f[x]||to[i]==son[x])continue;

dfs2(to[i],to[i]);

}

end[x]=tot;

}

int K;

lol val[MAXN<<2],lazy[MAXN<<2];

int st[MAXN];

inline void update(int x){val[x]=val[x<<1]+val[x<<1|1];}

inline void pushdown(int x){

int t=0;

for(x>>=1;x;x>>=1)st[++t]=x;

lol len=K>>1;

for(int i=t;i;i--,len>>=1){

if(!lazy[st[i]])continue;

val[st[i]<<1]+=len*lazy[st[i]];

val[st[i]<<1|1]+=len*lazy[st[i]];

lazy[st[i]<<1]+=lazy[st[i]];

lazy[st[i]<<1|1]+=lazy[st[i]];

lazy[st[i]]=0;

}

void mod(int l,int r,int x){

int ll=l=K+l-1,rr=r=K+r+1;

pushdown(ll);pushdown(rr);

lol len=1;

for(;l^r^1;l>>=1,r>>=1,len<<=1){

if(~l&1)val[l^1]+=x*len,lazy[l^1]+=x;

if( r&1)val[r^1]+=x*len,lazy[r^1]+=x;

}

for(ll>>=1;ll;ll>>=1)update(ll);

for(rr>>=1;rr;rr>>=1)update(rr);

}

lol query(int l,int r){

pushdown(l=K+l-1);pushdown(r=K+r+1);

lol res=0;

for(;l^r^1;l>>=1,r>>=1){

if(~l&1)res+=val[l^1];

if( r&1)res+=val[r^1];

}

return res;

}

lol ask(int x){

lol res=0;

for(;x;x=f[top[x]])res+=query(id[top[x]],id[x]);

return res;

}

int main(){

int n=gi(),m=gi();

for(int i=1;i<=n;i++)a[i]=gi();

for(int i=1;i<n;i++)add(gi(),gi());

dfs1(1);

dfs2(1,1);

for(int i=2;i<=n<<2;i++)lb[i]=lb[i>>1]+1;

K=2<<lb[n+1];

for(int i=1;i<=n;i++)val[K+id[i]]=a[i];

for(int i=K-1;i;i--)update(i);

while(m--){

int tp=gi(),x=gi();

if(tp==1)mod(id[x],id[x],gi());

else if(tp==2)mod(id[x],end[x],gi());

else printf("%lld\n",ask(x));

}

return 0;

}