BZOJ4372 烁烁的游戏(动态点分治+线段树)

  建出点分树,每个节点维护其作为点分树上lca对子树内点的贡献,线段树维护即可,同时另开一个线段树以减掉父亲重复的贡献。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,p[N],size[N],deep[N],fa[N][19],t;
bool flag[N];
struct data{int to,nxt;
}edge[N<<1];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void dfs(int k)
{
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k][0])
{
fa[edge[i].to][0]=k;
deep[edge[i].to]=deep[k]+1;
dfs(edge[i].to);
}
}
int lca(int x,int y)
{
if (deep[x]<deep[y]) swap(x,y);
for (int j=18;~j;j--) if (deep[fa[x][j]]>=deep[y]) x=fa[x][j];
if (x==y) return x;
for (int j=18;~j;j--) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
return fa[x][0];
}
int dis(int x,int y){return deep[x]+deep[y]-(deep[lca(x,y)]<<1);}
namespace newtree
{
int rt,cnt[2],root[2][N],fa[N];
struct data{int l,r,x;}tree[2][N<<7];
void addedge(int x,int y){fa[y]=x;}
void add(int &k,int l,int r,int p,int x,int op)
{
if (!k) k=++cnt[op];
tree[op][k].x+=x;
if (l==r) return;
int mid=l+r>>1;
if (p<=mid) add(tree[op][k].l,l,mid,p,x,op);
else add(tree[op][k].r,mid+1,r,p,x,op);
}
int sum(int k,int l,int r,int x,int op)
{
if (!k) return 0;
if (l==r) return tree[op][k].x;
int mid=l+r>>1;
if (x<=mid) return sum(tree[op][k].l,l,mid,x,op);
else return tree[op][tree[op][k].l].x+sum(tree[op][k].r,mid+1,r,x,op);
}
void modify(int x,int d,int w)
{
add(root[0][x],0,n,0,w,0),add(root[0][x],0,n,d+1,-w,0);
int i=x;
while (i!=rt)
{
int D=dis(x,fa[i]);
if (D<=d)
add(root[0][fa[i]],0,n,0,w,0),add(root[0][fa[i]],0,n,d-D+1,-w,0),
add(root[1][i],0,n,0,-w,1),add(root[1][i],0,n,d-D+1,w,1);
i=fa[i];
}
}
int query(int x)
{
int ans=0,i=x;
while (i) ans+=sum(root[0][i],0,n,dis(x,i),0),ans+=sum(root[1][i],0,n,dis(x,fa[i]),1),i=fa[i];
return ans;
}
}
void make(int k,int from)
{
size[k]=1;
for (int i=p[k];i;i=edge[i].nxt)
if (!flag[edge[i].to]&&edge[i].to!=from)
{
make(edge[i].to,k);
size[k]+=size[edge[i].to];
}
}
int findroot(int k,int from,int s)
{
int mx=0;
for (int i=p[k];i;i=edge[i].nxt)
if (!flag[edge[i].to]&&edge[i].to!=from&&size[edge[i].to]>size[mx]) mx=edge[i].to;
if ((size[mx]<<1)>s) return findroot(mx,k,s);
else return k;
}
int build(int k)
{
make(k,k);
flag[k=findroot(k,k,size[k])]=1;
for (int i=p[k];i;i=edge[i].nxt)
if (!flag[edge[i].to]) newtree::addedge(k,build(edge[i].to));
return k;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj4372.in","r",stdin);
freopen("bzoj4372.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read();
for (int i=1;i<n;i++)
{
int x=read(),y=read();
addedge(x,y),addedge(y,x);
}
fa[1][0]=1;dfs(1);
for (int j=1;j<19;j++)
for (int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
newtree::rt=build(1);
while (m--)
{
char c=getc();
if (c=='M')
{
int x=read(),d=read(),w=read();
newtree::modify(x,d,w);
}
else printf("%d\n",newtree::query(read()));
}
return 0;
}

  

上一篇:给你一个承诺 - 玩转 AngularJS 的 Promise(转)


下一篇:《ASP.NET MVC4 WEB编程》学习笔记------Model模型绑定