BZOJ 4034: [HAOI 2015] 트 리 조작 (낙 곡 P3178)
9019 단어 BZOJ낙 곡데이터 구조 - 트 리 체인 분할블 로그 칼럼
BZOJ 제목 전송 문 낙 곡 제목 전송 문
가장 기초적인 나무 토막.구간 수정 라인 트 리 직접 태그.long long (1e6 (M) * 1e6 (a) = 1e12) 을 켜 는 것 을 주의 하 세 요.
코드:
#include
#include
#include
#include
#define N 100005
using namespace std;
typedef long long LL;
struct tree{ int l,r; LL sum,tg; }t[N*4];
struct edge{ int next,to; }ed[N*2];
int n,m,nd,k,a[N],fa[N],dep[N],to[N],h[N],tp[N],sz[N],L[N],R[N],in[N];
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
if (l==r) return EOF; return *l++;
}
inline int _read(){
int num=0,f=1; char ch=readc();
while (!isdigit(ch)) { if (ch=='-') f=-1; ch=readc(); }
while (isdigit(ch)) num=(num<<3)+(num<<1)+(ch^48),ch=readc();
return num*f;
}
inline void addedge(int x,int y){
ed[++k].next=h[x],ed[k].to=y,h[x]=k;
}
void dfs1(int x,int depth){
sz[x]=1,dep[x]=depth;
for (int i=h[x];i;i=ed[i].next)
if (ed[i].to!=fa[x]){
int v=ed[i].to;
fa[v]=x,dfs1(v,depth+1),sz[x]+=sz[v];
if (sz[v]>sz[to[x]]) to[x]=v;
}
}
void dfs2(int x){
L[x]=++nd,in[nd]=x;
for (int i=h[x];i;i=ed[i].next)
if (ed[i].to==to[x])
tp[ed[i].to]=tp[x],dfs2(ed[i].to);
for (int i=h[x];i;i=ed[i].next)
if (ed[i].to!=to[x]&&ed[i].to!=fa[x])
tp[ed[i].to]=ed[i].to,dfs2(ed[i].to);
R[x]=nd;
}
void build(int l,int r,int x){
t[x].l=l,t[x].r=r;
if (l==r){ t[x].sum=a[in[l]]; return; }
int mid=l+r>>1; build(l,mid,x*2),build(mid+1,r,x*2+1);
t[x].sum=t[x*2].sum+t[x*2+1].sum;
}
inline void pshd(int x){
t[x*2].tg+=t[x].tg,t[x*2+1].tg+=t[x].tg;
t[x*2].sum+=t[x].tg*(t[x*2].r-t[x*2].l+1);
t[x*2+1].sum+=t[x].tg*(t[x*2+1].r-t[x*2+1].l+1);
t[x].tg=0;
}
void mdfy(int x,int l,int r,int w){
if (t[x].l>r||t[x].rreturn;
if (t[x].l>=l&&t[x].r<=r){
t[x].sum+=(t[x].r-t[x].l+1)*(LL)w;// LL
t[x].tg+=w; return;
}
if (t[x].tg) pshd(x);
mdfy(x*2,l,r,w),mdfy(x*2+1,l,r,w);
t[x].sum=t[x*2].sum+t[x*2+1].sum;
}
LL find(int x,int l,int r){
if (t[x].l>r||t[x].rreturn 0;
if (t[x].l>=l&&t[x].r<=r) return t[x].sum;
if (t[x].tg) pshd(x);
return find(x*2,l,r)+find(x*2+1,l,r);
}
inline LL srch(int x,int y){
LL ans=0;
while (tp[x]!=tp[y]){
if (dep[tp[x]]1,L[tp[x]],L[x]),x=fa[tp[x]];
}
if (dep[x]return ans+=find(1,L[y],L[x]);
}
int main(){
n=_read(),m=_read();
for (int i=1;i<=n;i++) a[i]=_read();
for (int i=1;iint u=_read(),v=_read();
addedge(u,v),addedge(v,u);
}
dfs1(1,1),tp[1]=1,dfs2(1),build(1,n,1);
while (m--){
int flag=_read(),x=_read(),z;
switch (flag){
case 1: z=_read(),mdfy(1,L[x],L[x],z); break;
case 2: z=_read(),mdfy(1,L[x],R[x],z); break;
case 3: printf("%lld
",srch(1,x)); break;
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ3930: [CQOI2015] 선택거의 짠 물고기일 거야.. 처음에 제목 yy에 대해 정확할 것 같고 복잡도 계산이 안 되는 검색을 했는데 잘 안 되는 것 같아서 DP를 생각하고 정확해 보이는 DP를 생각해서 끊었어요.그럼 용납하고 싶다......설...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.