F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 3730 >> 请问这份代码哪些地方可以进行常数优化
1527148777 @ 2018-02-21 23:41:15
[ Quote ] [ Edit ] [ Delete ] 1#
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 100001

int n,a[N];

int front[N],nxt[N<<1],to[N<<1],tot;

int all,root;
int siz[N],f[N];

bool vis[N];

int dep[N];
int fa[N][18],dis[N][18];

struct Segment
{
int cnt;
int rt[N];
int lc[N*80],rc[N*80],val[N*80];

void Change(int &k,int l,int r,int x,int y)
{
if(!k) k=++cnt;
if(l==r)
{
val[k]+=y;
return;
}
int mid=l+r>>1;
if(x<=mid) Change(lc[k],l,mid,x,y);
else Change(rc[k],mid+1,r,x,y);
val[k]=val[lc[k]]+val[rc[k]];
}

int Query(int k,int l,int r,int x)
{
if(!k) return 0;
if(r<=x) return val[k];
int mid=l+r>>1;
if(x<=mid) return Query(lc[k],l,mid,x);
else return val[lc[k]]+Query(rc[k],mid+1,r,x);
}

}tr,ftr;

void read(int &x)
{
x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
}

void getroot(int x,int y)
{
siz[x]=1; f[x]=0;
for(int i=front[x];i;i=nxt[i])
if(to[i]!=y && !vis[to[i]])
{
getroot(to[i],x);
siz[x]+=siz[to[i]];
f[x]=max(f[x],siz[to[i]]);
}
f[x]=max(f[x],all-siz[x]);
if(f[x]<f[root]) root=x;
}

void cal(int x,int ancestor,int father,int d)
{
int t;
for(int i=front[x];i;i=nxt[i])
{
t=to[i];
if(t!=father && !vis[t])
{
fa[t][++dep[t]]=ancestor;
dis[t][dep[t]]=d+1;
cal(t,ancestor,x,d+1);
}
}
}

void build(int x)
{
vis[x]=true;
cal(x,x,0,0);
int tmp=all;
for(int i=front[x];i;i=nxt[i])
if(!vis[to[i]])
{
all=siz[to[i]];
if(all>siz[x]) all=tmp-siz[x];
root=0;
getroot(to[i],0);
build(root);
}
}

void change(int x,int y)
{
tr.Change(tr.rt[x],0,n-1,0,y);
int d;
for(int i=dep[x];i;--i)
{
ftr.Change(ftr.rt[fa[x][i+1]],0,n-1,dis[x][i],y);
// printf("kk %d\n",dis[x][i]);
tr.Change(tr.rt[fa[x][i]],0,n-1,dis[x][i],y);
}
}

int query(int x,int d)
{
int ans=tr.Query(tr.rt[x],0,n-1,d);
for(int i=dep[x];i;--i)
{
if(d-dis[x][i]>=0) ans+=tr.Query(tr.rt[fa[x][i]],0,n-1,d-dis[x][i]);
if(d-dis[x][i]>=0) ans-=ftr.Query(ftr.rt[fa[x][i+1]],0,n-1,d-dis[x][i]);
}
return ans;
}

void out(int x)
{
if(x>=10) out(x/10);
putchar(x%10+'0');
}

int main()
{
//freopen("data.in","r",stdin);
//freopen("my.out","w",stdout);
int m;
read(n); read(m);
for(int i=1;i<=n;++i) read(a[i]);
int u,v;
for(int i=1;i<n;++i)
{
read(u); read(v);
add(u,v);
}
f[0]=n+1;
all=n;
getroot(1,0);
build(root);
for(int i=1;i<=n;++i) fa[i][dep[i]+1]=i;
for(int i=1;i<=n;++i)
change(i,a[i]);
int ty,last=0;
while(m--)
{
read(ty); read(u); read(v);
u^=last; v^=last;
if(!ty) last=query(u,v),out(last),printf("\n");
else change(u,v-a[u]),a[u]=v;
}
//printf("%d %d",tr.cnt,ftr.cnt);
return 0;
}
1527148777 @ 2018-02-21 23:43:54
[ Quote ] [ Edit ] [ Delete ] 2#
代码链接:http://www.cnblogs.com/TheRoadToTheGold/p/8457809.html
Unstoppable728 @ 2018-12-16 16:13:14
[ Quote ] [ Edit ] [ Delete ] 3#
请不要使用倍增Lca
[Top] [Previous Page] [Next Page]

HOME Back