loj 139 树链剖分

题目大意：

给定一棵n

换根：将一个指定的节点设置为树的新根
修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值
修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值
询问路径：询问某条路径上节点的权值和
询问子树：询问某个子树内节点的权值和

思路：

莫得思路

换根就完事了（讨论一下根是否在查询点的子树里）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<queue>
  9 #define inf 2147483648
 10 #define ll long long
 11 #define MAXN 100100
 12 using namespace std;
 13 inline int read()
 14 {
 15     int x=0,f=1;char ch=getchar();
 16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
 17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
 18     return x*f;
 19 }
 20 int n,m,cnt,nxt[MAXN<<1],fst[MAXN],to[MAXN<<1];
 21 int dep[MAXN],sz[MAXN],hsh[MAXN],HSH[MAXN],fa[MAXN],bl[MAXN],rt=1;
 22 ll tag[MAXN<<2],sum[MAXN<<2],val[MAXN];
 23 void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
 24 void dfs(int x)
 25 {
 26     for(register int i=fst[x];i;i=nxt[i])
 27         if(to[i]!=fa[x]) {dep[to[i]]=dep[x]+1,fa[to[i]]=x;dfs(to[i]);sz[x]+=sz[to[i]];}
 28     sz[x]++;
 29 }
 30 void dfs(int x,int anc)
 31 {
 32     hsh[x]=++cnt,HSH[cnt]=x,bl[x]=anc;int hvs=0;
 33     for(register int i=fst[x];i;i=nxt[i])
 34         if(to[i]!=fa[x]&&sz[to[i]]>sz[hvs]) hvs=to[i];
 35     if(!hvs) return ;dfs(hvs,anc);
 36     for(register int i=fst[x];i;i=nxt[i])
 37         if(to[i]!=fa[x]&&to[i]!=hvs) dfs(to[i],to[i]);
 38 }
 39 void pshd(int k,int l,int r,int mid)
 40 {
 41     sum[k<<1]+=tag[k]*(mid-l+1),sum[k<<1|1]+=tag[k]*(r-mid);
 42     tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k],tag[k]=0;
 43 }
 44 void mdf(int k,int l,int r,int a,int b,int x)
 45 {
 46     if(l==a&&r==b) {sum[k]+=(ll)x*(r-l+1),tag[k]+=x;return ;}
 47     int mid=l+r>>1;
 48     if(tag[k]) pshd(k,l,r,mid);
 49     if(b<=mid) mdf(k<<1,l,mid,a,b,x);
 50     else if(a>mid) mdf(k<<1|1,mid+1,r,a,b,x);
 51     else {mdf(k<<1,l,mid,a,mid,x);mdf(k<<1|1,mid+1,r,mid+1,b,x);}
 52     sum[k]=sum[k<<1]+sum[k<<1|1];
 53 }
 54 ll query(int k,int l,int r,int a,int b)
 55 {
 56     if(l==a&&r==b) return sum[k];
 57     int mid=l+r>>1;
 58     if(tag[k]) pshd(k,l,r,mid);
 59     if(b<=mid) return query(k<<1,l,mid,a,b);
 60     else if(a>mid) return query(k<<1|1,mid+1,r,a,b);
 61     else return query(k<<1,l,mid,a,mid)+query(k<<1|1,mid+1,r,mid+1,b);
 62 }
 63 inline void workm()
 64 {
 65     int x=read(),c=read();
 66     if(x==rt) {mdf(1,1,n,1,n,c);return ;}ll f,res=0;int y=rt;
 67     if(hsh[x]+sz[x]-1>=hsh[rt]&&hsh[x]<=hsh[rt])
 68     {
 69         while(fa[bl[y]]!=x&&bl[y]!=bl[x]) y=fa[bl[y]];
 70         if(bl[y]==bl[x]) f=hsh[x]+1;else f=hsh[bl[y]];
 71         mdf(1,1,n,1,f-1,c);
 72         if(f+sz[HSH[f]]<=n) mdf(1,1,n,f+sz[HSH[f]],n,c);
 73     }
 74     else mdf(1,1,n,hsh[x],hsh[x]+sz[x]-1,c);
 75 }
 76 inline ll workq(int x)
 77 {
 78     if(x==rt) return sum[1];ll f,res=0;int y=rt;
 79     if(hsh[x]+sz[x]-1>=hsh[rt]&&hsh[x]<=hsh[rt])
 80     {
 81         while(fa[bl[y]]!=x&&bl[y]!=bl[x]) y=fa[bl[y]];
 82         if(bl[y]==bl[x]) f=hsh[x]+1;else f=hsh[bl[y]];
 83         res+=query(1,1,n,1,f-1);
 84         if(f+sz[HSH[f]]<=n) res+=query(1,1,n,f+sz[HSH[f]],n);
 85         return res;
 86     }
 87     else return query(1,1,n,hsh[x],hsh[x]+sz[x]-1);
 88 }
 89 int main()
 90 {
 91     n=read();int a,b,c;ll res=0;
 92     for(register int i=1;i<=n;i++) val[i]=read();
 93     for(register int i=2;i<=n;i++) {b=read();add(i,b);add(b,i);}
 94     fa[1]=1;dfs(1);cnt=0;dfs(1,1);
 95     for(register int i=1;i<=n;i++) mdf(1,1,n,hsh[i],hsh[i],val[i]);
 96     m=read();
 97     for(register int t=1;t<=m;t++)
 98     {
 99         c=read();
100         if(c==1) rt=read();
101         else if(c==2)
102         {
103             a=read(),b=read(),c=read();
104             while(bl[a]!=bl[b])
105             {
106                 if(dep[bl[a]]<dep[bl[b]]) swap(a,b);
107                 mdf(1,1,n,hsh[bl[a]],hsh[a],c);
108                 a=fa[bl[a]];
109             }
110             if(dep[a]>dep[b]) swap(a,b);
111             mdf(1,1,n,hsh[a],hsh[b],c);
112         }
113         else if(c==4)
114         {
115             a=read(),b=read(),res=0;
116             while(bl[a]!=bl[b])
117             {
118                 if(dep[bl[a]]<dep[bl[b]]) swap(a,b);
119                 res+=query(1,1,n,hsh[bl[a]],hsh[a]);
120                 a=fa[bl[a]];
121             }
122             if(dep[a]>dep[b]) swap(a,b);
123             res+=query(1,1,n,hsh[a],hsh[b]);
124             printf("%lld
",res);
125         }
126         else if(c==3) workm();
127         else printf("%lld
",workq(read()));
128     }
129 }

View Code

bzoj 3083 遥远的国度

题目大意：

支持三种操作 1换根 2路径赋值 3查询字数内最小值

思路：

上面那道题弱化版但是因为tag没下传调了一年

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<queue>
  9 #define inf 2147483648
 10 #define ll long long
 11 #define MAXN 100100
 12 #define int unsigned int
 13 using namespace std;
 14 inline int read()
 15 {
 16     int x=0,f=1;char ch=getchar();
 17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
 18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
 19     return x*f;
 20 }
 21 int n,m,cnt,nxt[MAXN<<1],fst[MAXN],to[MAXN<<1];
 22 int dep[MAXN],sz[MAXN],hsh[MAXN],HSH[MAXN],fa[MAXN],bl[MAXN],rt;
 23 int tag[MAXN<<2],mn[MAXN<<2];
 24 void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
 25 void dfs(int x)
 26 {
 27     for(int i=fst[x];i;i=nxt[i])
 28         if(to[i]!=fa[x]) {dep[to[i]]=dep[x]+1,fa[to[i]]=x;dfs(to[i]);sz[x]+=sz[to[i]];}
 29     sz[x]++;
 30 }
 31 void dfs(int x,int anc)
 32 {
 33     hsh[x]=++cnt,HSH[cnt]=x,bl[x]=anc;int hvs=0;
 34     for(int i=fst[x];i;i=nxt[i])
 35         if(to[i]!=fa[x]&&sz[to[i]]>sz[hvs]) hvs=to[i];
 36     if(!hvs) return ;dfs(hvs,anc);
 37     for(int i=fst[x];i;i=nxt[i])
 38         if(to[i]!=fa[x]&&to[i]!=hvs) dfs(to[i],to[i]);
 39 }
 40 void pshd(int k) {mn[k<<1]=mn[k<<1|1]=tag[k<<1]=tag[k<<1|1]=tag[k],tag[k]=0;}
 41 void mdf(int k,int l,int r,int a,int b,int x)
 42 {
 43     if(l==a&&r==b) {mn[k]=tag[k]=x;return ;}
 44     int mid=l+r>>1;
 45     if(tag[k]) pshd(k);
 46     if(b<=mid) mdf(k<<1,l,mid,a,b,x);
 47     else if(a>mid) mdf(k<<1|1,mid+1,r,a,b,x);
 48     else {mdf(k<<1,l,mid,a,mid,x);mdf(k<<1|1,mid+1,r,mid+1,b,x);}
 49     mn[k]=min(mn[k<<1],mn[k<<1|1]);
 50 }
 51 int query(int k,int l,int r,int a,int b)
 52 {
 53     if(l==a&&r==b) return mn[k];
 54     int mid=l+r>>1;
 55     if(tag[k]) pshd(k);
 56     if(b<=mid) return query(k<<1,l,mid,a,b);
 57     else if(a>mid) return query(k<<1|1,mid+1,r,a,b);
 58     else return min(query(k<<1,l,mid,a,mid),query(k<<1|1,mid+1,r,mid+1,b));
 59 }
 60 inline int work(int x)
 61 {
 62     if(x==rt) return mn[1];int f,res=inf,y=rt;
 63     if(hsh[x]+sz[x]-1>=hsh[rt]&&hsh[x]<=hsh[rt])
 64     {
 65         while(fa[bl[y]]!=x&&bl[y]!=bl[x]) y=fa[bl[y]];
 66         if(bl[y]==bl[x]) f=hsh[x]+1;else f=hsh[bl[y]];
 67         res=min(res,query(1,1,n,1,f-1));
 68         if(f+sz[HSH[f]]<=n) res=min(res,query(1,1,n,f+sz[HSH[f]],n));
 69         return res;
 70     }
 71     else return query(1,1,n,hsh[x],hsh[x]+sz[x]-1);
 72 }
 73 signed main()
 74 {
 75     //freopen("country1.in","r",stdin);
 76     //freopen("ok.txt","w",stdout);
 77     n=read(),m=read();int a,b,c;
 78     for(int i=1;i<n;i++) {a=read(),b=read();add(a,b);add(b,a);}
 79     fa[1]=1;dfs(1);cnt=0;dfs(1,1);
 80     for(int i=1;i<=n;i++) mdf(1,1,n,hsh[i],hsh[i],read());
 81     rt=read();
 82     while(m--)
 83     {
 84         c=read();
 85         if(c==1) rt=read();
 86         else if(c==2)
 87         {
 88             a=read(),b=read(),c=read();
 89             while(bl[a]!=bl[b])
 90             {
 91                 if(dep[bl[a]]<dep[bl[b]]) swap(a,b);
 92                 mdf(1,1,n,hsh[bl[a]],hsh[a],c);
 93                 a=fa[bl[a]];
 94             }
 95             if(dep[a]>dep[b]) swap(a,b);
 96             mdf(1,1,n,hsh[a],hsh[b],c);
 97         }
 98         else printf("%d
",work(read()));
 99     }
100 }

View Code