[BZOJ 3730]震波

Description
在一片土地上有N个城市，通过N-1条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为1，其中第i个城市的价值为value[i]。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。
接下来你需要在线处理M次操作：
0 x k 表示发生了一次地震，震中城市为x，影响范围为k，所有与x距离不超过k的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
1 x y 表示第x个城市的价值变成了y。
为了体现程序的在线性，操作中的x、y、k都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为0。

Input
第一行包含两个正整数N和M。
第二行包含N个正整数，第i个数表示value[i]。
接下来N-1行，每行包含两个正整数u、v，表示u和v之间有一条无向边。
接下来M行，每行包含三个数，表示M次操作。

Output
包含若干行，对于每个询问输出一行一个正整数表示答案。

Sample Input
8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1

Sample Output
11100101

HINT
1<=N,M<=100000
1<=u,v,x<=N
1<=value[i],y<=10000
0<=k<=N-1

第一次写冻态淀粉质，写完就不知道自己在干什么系列……

如果没有修改操作，那就是个简单的点分治；有修改，我们就把点分治的过程记录下来，对于每个分治重心，对其管辖范围内的所有点按照距离放在树状数组上维护

每次修改操作，枚举所有管辖\(x\)的重心，在对应树状数组中进行修改

每次询问操作，枚举所有管辖\(x\)的重心，在对应树状数组中进行查询

为了防止相同子树内贡献多算，我们需要在每个分治重心处维护每个子树的树状数组来减掉

树状数组动态空间，我们可以开一个全局的数组，然后剥离一段段区间下发给每个树状数组；对每个分治重心维护子树树状数组可以用map+pair记录；对于每个点用vector记录三元组\((x,y,dis)\)，表示管辖其的重心\(x\)，\(y\)是\(x\)的直接儿子且子树内包含该点，\(dis\)记录该点到\(x\)的距离；树状数组查询时为了防止\(dis=0\)，可以对所有距离+1

细节多……不过自己YY出来的还是很有成就感，常数略大……

/*program from Wolfycz*/
#include<map>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define Fi first
#define Se second
#define MK make_pair
#define inf 0x7f7f7f7f
#define lowbit(x) ((x)&-(x))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef unsigned long long ull;
inline char gc(){
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
    int x=0,f=1; char ch=gc();
    for (;ch<'0'||ch>'9';ch=gc())   if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}
inline int read(){
    int x=0,f=1; char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}
inline void print(int x){
    if (x<0)    putchar('-'),x=-x;
    if (x>9)    print(x/10);
    putchar(x%10+'0');
}
const int N=1e5,M=2e6;
int pre[(N<<1)+10],now[N+10],child[(N<<1)+10];
int size[N+10],h[N+10],deep[N+10],V[N+10];
bool vis[N+10];
int root,Max,tot,top;
map<pii,int>Mp;
struct S1{
    int x,Rem,dis;
    S1(){x=Rem=dis=0;}
    S1(int _x,int _r,int _d){x=_x,Rem=_r,dis=_d;}
    void insert(int _x,int _r,int _d){x=_x,Rem=_r,dis=_d;}
};
vector<S1>vec[N+10];
int tree[M+10],remain,BIT_cnt;
struct S2{
    int val,delta,len;
    void init(int x,int v){delta=remain,remain+=(len=x),val=v;}
    void insert(int x,int v){for (;x<=len;x+=lowbit(x)) tree[x+delta]+=v;}
    int Query(int x){
        x=min(x,len); int res=0;
        if (x<=0)   return res;
        for (;x;x-=lowbit(x))   res+=tree[x+delta];
        return res*val;
    }
}BIT[(N<<1)+10];//Binary Indexed Tree
void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}
void insert(int x,int y){join(x,y),join(y,x);}
void Get_root(int x,int fa,int sz){
    int res=0; size[x]=1;
    for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){
        if (son==fa||vis[son])  continue;
        Get_root(son,x,sz);
        res=max(res,size[son]);
        size[x]+=size[son];
    }
    res=max(res,sz-size[x]);
    if (res<Max)    Max=res,root=x;
}
int solve(int x,int fa,int belong){
    deep[x]=deep[fa]+1,h[++top]=x;
    int res=deep[x];
    S1 tmp(root,belong,deep[x]);
    vec[x].push_back(tmp);
    for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){
        if (son==fa||vis[son])  continue;
        res=max(res,solve(son,x,belong));
    }
    return res;
}
void divide(int x){
    static int tmp[N+10]; vis[x]=1;
    int tail=0,Md=1; deep[x]=1;
    tmp[++tail]=x;
    S1 t(x,0,deep[x]);
    vec[x].push_back(t);
    for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){
        if (vis[son])   continue;
        top=0; int dep=solve(son,x,son);
        Mp.insert(map<pii,int>::value_type(MK(x,son),++BIT_cnt));
        BIT[BIT_cnt].init(dep,-1);
        for (int i=1;i<=top;i++)    BIT[BIT_cnt].insert(deep[h[i]],V[h[i]]),tmp[++tail]=h[i];
        Md=max(Md,dep);
    }
    BIT[x].init(Md,1);
    for (int i=1;i<=tail;i++)   BIT[x].insert(deep[tmp[i]],V[tmp[i]]);
    for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){
        if (vis[son])   continue;
        root=0,Max=inf;
        Get_root(son,x,size[son]);
        divide(root);
    }
}
int main(){
    int n=read(),m=read(); BIT_cnt=n;
    for (int i=1;i<=n;i++)  V[i]=read();
    for (int i=1;i<n;i++){
        int x=read(),y=read();
        insert(x,y);
    }
    root=0,Max=inf;
    Get_root(1,0,n);
    divide(root);
    int lastans=0;
    for (int i=1;i<=m;i++){
        int type=read(),x=read()^lastans,y=read()^lastans;
        if (type==0){
            int res=0;
            for (vector<S1>::iterator it=vec[x].begin();it!=vec[x].end();it++){
                res=res+BIT[(*it).x].Query(y-(*it).dis+2);
                map<pii,int>::iterator tmp=Mp.find(MK((*it).x,(*it).Rem));
                if (tmp!=Mp.end())  res=res+BIT[tmp->Se].Query(y-(*it).dis+2);
            }
            printf("%d\n",lastans=res);
        }
        if (type==1){
            for (vector<S1>::iterator it=vec[x].begin();it!=vec[x].end();it++){
                map<pii,int>::iterator tmp=Mp.find(MK((*it).x,(*it).Rem));
                BIT[(*it).x].insert((*it).dis,y-V[x]);
                if (tmp!=Mp.end())  BIT[tmp->Se].insert((*it).dis,y-V[x]);
            }
            V[x]=y;
        }
    }
    return 0;
}

[BZOJ 3730]震波

原文：https://www.cnblogs.com/Wolfycz/p/10264187.html