bzoj 3730 震波

给一个 $n$ 个点的带权树，每次修改一个点的权值，或者询问到 $x$ 距离不超过 $k$ 的点的权值和，强制在线

sol：

套路题，首先搞出一个点分树，每个重心，以到重心的距离为下标，点权为权值建两棵线段树，一个用来统计答案，一个用来消除对父节点的影响

每次修改和讯询问都是暴力爬树高，在经过的每棵线段树里修改就可以了

好了，然后我们来 $D$ 这个 sb 博主

道理我都懂，你求 LCA 为什么要树剖啊，复杂度强行加 log

明明树状数组就可以干的事情（单点加，区间和）你为什么要线段树啊，强行多大常数

OYJason 8160ms 就能过的题强行被我搞到了 13796ms

我真是个 sb

复杂度大概是 $O(nlogn + mlog^2n)$ ?

#include
#define LL long long
using namespace std;
inline int read()
{int x = 0,f = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f;for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0';return x * f;
}
const int maxn = 500010;
int n,m,lastans;
int first[maxn],to[maxn << 1],nx[maxn << 1],cnt;
inline void add(int u,int v){to[++cnt] = v;nx[cnt] = first[u];first[u] = cnt;}
inline void ins(int u,int v){add(u,v);add(v,u);}
namespace LCA //RMQ is not good ? 
{int dep[maxn],bl[maxn],fa[maxn],size[maxn];inline void dfs1(int x){size[x] = 1;for(int i=first[x];i;i=nx[i]){if(to[i] == fa[x])continue;fa[to[i]] = x;dep[to[i]] = dep[x] + 1;dfs1(to[i]);size[x] += size[to[i]];}}inline void dfs2(int x,int col){int k = 0;bl[x] = col;for(int i=first[x];i;i=nx[i])if(dep[to[i]] > dep[x] && size[to[i]] > size[k])k = to[i];if(!k)return;dfs2(k,col);for(int i=first[x];i;i=nx[i])if(dep[to[i]] > dep[x] && to[i] != k)dfs2(to[i],to[i]);}inline int lca(int x,int y){while(bl[x] != bl[y]){if(dep[bl[x]] < dep[bl[y]])swap(x,y);x = fa[bl[x]];}return dep[x] > dep[y] ? y : x;}
}
namespace SEG
{int root[maxn][2],ls[maxn << 4],rs[maxn << 4],val[maxn << 4],size;inline void Insert(int &x,int l,int r,int pos,int va){if(!x) x = ++size;val[x] += va;if(l == r)return;int mid = (l + r) >> 1;if(pos <= mid)Insert(ls[x],l,mid,pos,va);else Insert(rs[x],mid + 1,r,pos,va);}inline int query(int x,int l,int r,int L,int R){if(!x)return 0;if(L <= l && r <= R)return val[x];int mid = (l + r) >> 1,ans = 0;if(L <= mid)ans += query(ls[x],l,mid,L,R);if(R > mid)ans += query(rs[x],mid + 1,r,L,R);return ans;}
}
inline int q_dis(int x,int y){return LCA::dep[x] + LCA::dep[y] - (LCA::dep[LCA::lca(x,y)] << 1);}
int size[maxn],f[maxn],vis[maxn],d[maxn],v[maxn],son,root;
int nfa[maxn];
inline void solve(int rt,int type,int x,int fa)
{SEG::Insert(SEG::root[rt][type],0,n,d[x],v[x]);for(int i=first[x];i;i=nx[i]){if(to[i] == fa || vis[to[i]])continue;d[to[i]] = d[x] + 1;solve(rt,type,to[i],x);}
}
inline void getroot(int x,int fa)
{size[x] = 1,f[x] = 0;for(int i=first[x];i;i=nx[i]){if(to[i] == fa || vis[to[i]])continue;getroot(to[i],x);size[x] += size[to[i]];f[x] = max(f[x],size[to[i]]);}f[x] = max(f[x],son - size[x]);if(f[x] < f[root])root = x;
}
inline void work(int x)
{vis[x] = 1;d[x] = 0;solve(x,0,x,0);for(int i=first[x];i;i=nx[i]){if(vis[to[i]])continue;son = size[to[i]];root = 0;d[to[i]] = 1;getroot(to[i],0);solve(root,1,to[i],x);nfa[root] = x;work(root);}
}
inline int query(int x,int k)
{int ret = SEG::query(SEG::root[x][0],0,n,0,k);for(int i=x;nfa[i];i = nfa[i]){int du = q_dis(x,nfa[i]);ret += SEG::query(SEG::root[nfa[i]][0],0,n,0,k - du);ret -= SEG::query(SEG::root[i][1],0,n,0,k - du);        }return ret;
}
inline void update(int x,int k)
{int delt = k - SEG::query(SEG::root[x][0],0,n,0,0);SEG::Insert(SEG::root[x][0],0,n,0,delt);for(int i=x;nfa[i];i = nfa[i]){int du = q_dis(x,nfa[i]);SEG::Insert(SEG::root[nfa[i]][0],0,n,du,delt);SEG::Insert(SEG::root[i][1],0,n,du,delt);}
}
int main()
{//freopen("1.in","r",stdin);//freopen("1w.out","w",stdout);n = read(),m = read();for(int i=1;i<=n;i++)v[i] = read();for(int i=2;i<=n;i++){int u = read(),v = read();ins(u,v);}LCA::dfs1(1);LCA::dfs2(1,1);f[0] = son = n;getroot(1,0);work(root);while(m--){int opt = read(),x = read() ^ lastans,y = read() ^ lastans;if(opt)update(x,y);else printf("%d\n",lastans = query(x,y));}
}

转载于:https://www.cnblogs.com/Kong-Ruo/p/9913848.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！