首页 > 代码库 > BZOJ4765: 普通计算姬
BZOJ4765: 普通计算姬
推了下发现没法树剖直接搞,于是强上分块……按dfs序分块,每个块存一个原编号的有序表,再维护一个前缀和。修改相当于到根的链都加上一个数,树剖之后每个区间根号修改,查询在所有块中二分,复杂度$O(n^{1.5}logn)$。有$O(n^{1.5})$做法没推出来,反正多个log也过了。
WA的人那么多,一定有坑,仔细研究了数据范围,发现刚好爆long long,我真是太机智了哇哈哈
#include<bits/stdc++.h> #define lb lower_bound #define ub upper_bound using namespace std; typedef unsigned long long ll; const int M=320; const int N=M*M; int dfn,n1,n2,n3,n4,n5; struct edge{ int v;edge*s; }e[N*2]; edge*l1=e,*h[N]; void ins(int u,int v){ edge s={v,h[u]}; *(h[u]=l1++)=s; } typedef int arr[N]; arr b,d,f,w,c1,c2,c3,c4,c5; ll c6[N]; void dfs1(int u){ c3[u]=1,c6[u]=d[u]; for(edge*i=h[u];i;i=i->s) if(i->v!=c2[u]){ c1[i->v]=c1[c2[i->v]=u]+1; dfs1(i->v); c3[u]+=c3[i->v]; c6[u]+=c6[i->v]; if(c3[i->v]>c3[c4[u]]) c4[u]=i->v; } } void dfs2(int u,int v){ f[u]=++dfn,c5[u]=v; if(c4[u])dfs2(c4[u],v); for(edge*i=h[u];i;i=i->s) if(i->v!=c2[u]&&i->v!=c4[u]) dfs2(i->v,i->v); } struct blo{ ll d,c1[M]; int c2[M]; void pre(){ for(int i=1;i<=n3;++i) c1[i]=c1[i-1]+c6[c2[i]]; } void inc(int v,int s,int t){ for(int i=1;i<=n3;++i) if(s<=f[c2[i]]&&f[c2[i]]<=t) c6[c2[i]]+=v; pre(); } ll ask(int s,int t){ int u=lb(c2+1,c2+n3+1,s)-c2-1; int v=ub(c2+1,c2+n3+1,t)-c2-1; return d*(v-u)+c1[v]-c1[u]; } }a[M]; void inc(int v,int s,int t){ int l=b[s],r=b[t]; a[l].inc(v,s,t); if(l!=r){ a[r].inc(v,s,t); for(int i=l+1;i<r;++i) a[i].d+=v; } } void inc(int u,int v){ for(;u;u=c2[c5[u]]) inc(v,f[c5[u]],f[u]); } ll ask(int s,int t){ ll v=0; for(int i=1;i<=n2;++i) v+=a[i].ask(s,t); return v; } int main(){ scanf("%d%d",&n1,&n5); n2=sqrt(n1+.5); n3=(n1+n2-1)/n2; n4=n2*n3; for(int i=1;i<=n4;++i) b[f[i]=i]=(i-1)/n3+1; for(int i=1;i<=n1;++i) scanf("%d",d+i); int r,o,u,v; for(int i=1;i<=n1;++i){ scanf("%d%d",&u,&v); if(!u)r=v; else ins(u,v),ins(v,u); } dfs1(r),dfs2(r,r); for(int i=1;i<=n4;++i) a[b[f[i]]].c2[++w[b[f[i]]]]=i; for(int i=1;i<=n2;++i) a[i].pre(); while(n5--){ scanf("%d%d%d",&o,&u,&v); if(o==1) inc(u,v-d[u]),d[u]=v; else printf("%llu\n",ask(u,v)); } }
BZOJ4765: 普通计算姬
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。