2019.7.26 T1 树剖+双标记

偏执的太偏执、 2023-06-04 08:00 12阅读 0赞

[**题目链接**][Link 1]

**之前很久的一道题，还是写一写，这道题一眼就是树剖不用说了吧，但是它要同时支持区间赋值和加法操作，所以我们肯定需要两个标记，但是当赋值和加法标记同时下方的时候，就需要我们的细节处理，首先赋值的初始值应该赋为-1，而且下方的时候要先释放优先级高的赋值标记。区间赋值的时候，必须清空之前的加标记！当时考试的时候就是因为这样爆零了，惨痛的教训。**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
      2 using namespace std;
      3 const int maxn=1e6+7;
      4 const int N=1e7+7;
      5 struct seg{
      6     int l,r,lazy1,lazy2;
      7     long long sum;
      8 }tree[maxn*10];
      9 struct node{
     10     int nxt,to;
     11 }edge[maxn*2];
     12 int n,m;
     13 int a[maxn];
     14 int dep[maxn],fa[maxn],size[maxn],id[maxn],son[maxn],rev[maxn],top[maxn];
     15 bool not_zhishu[N];
     16 int prime[maxn];
     17 int Time,cnt;
     18 int head[maxn];
     19 int opt,x,y,k;
     20 int st,ed;
     21 int jmr;
     22 bool flag;
     23 inline void Euler(){
     24     for( register int i=2;i<=10000000;i++){
     25         if(!not_zhishu[i]) prime[++prime[0]] = i;
     26         for(register int j=1;j<=prime[0]&&i*prime[j]<=10000000;j++){
     27             not_zhishu[i*prime[j]]=true;
     28             if(i%prime[j]==0) break;
     29         }
     30     }
     31 }
     32 inline void add(int u,int v){
     33     edge[++cnt].nxt=head[u];
     34     edge[cnt].to=v;
     35     head[u]=cnt;
     36 }
     37 inline void dfs1(int x,int f){
     38     dep[x]=dep[f]+1;
     39     fa[x]=f;
     40     size[x]=1;
     41     int maxson=-1;
     42     for(int i=head[x];i;i=edge[i].nxt){
     43         int v=edge[i].to;
     44         if(v==f) continue;
     45         dfs1(v,x);
     46         size[x]+=size[v];
     47         if(size[v]>maxson||son[x]==-1){
     48             maxson=size[v];
     49             son[x]=v;
     50         }
     51     }
     52 }
     53 inline void dfs2(int x,int topf){
     54     top[x]=topf;
     55     id[x]=++Time;
     56     rev[id[x]]=x;
     57     if(son[x]==-1) return;
     58     dfs2(son[x],topf);
     59     for(int i=head[x];i;i=edge[i].nxt){
     60         int v=edge[i].to;
     61         if(v==son[x]||v==fa[x]) continue;
     62         dfs2(v,v);
     63     }
     64 }
     65 inline void pushup(int x){
     66     tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
     67 }
     68 inline void pushdown(int x){
     69     if(tree[x].lazy2!=-1){
     70         tree[x*2].sum=tree[x].lazy2*(tree[x*2].r-tree[x*2].l+1);
     71         tree[x*2+1].sum=tree[x].lazy2*(tree[x*2+1].r-tree[x*2+1].l+1);
     72         tree[x*2].lazy2=tree[x].lazy2;
     73         tree[x*2+1].lazy2=tree[x].lazy2;
     74         tree[x].lazy2=-1;
     75         tree[x*2+1].lazy1=tree[x*2].lazy1=0;
     76     }
     77     if(tree[x].lazy1){
     78         tree[x*2].sum+=tree[x].lazy1*(tree[x*2].r-tree[x*2].l+1);
     79         tree[x*2+1].sum+=tree[x].lazy1*(tree[x*2+1].r-tree[x*2+1].l+1);
     80         tree[x*2].lazy1+=tree[x].lazy1;
     81         tree[x*2+1].lazy1+=tree[x].lazy1;
     82         tree[x].lazy1=0;
     83     }
     84 }
     85 inline void build(int now,int l,int r){
     86     tree[now].l=l;
     87     tree[now].r=r;
     88     tree[now].lazy1=0;
     89     tree[now].lazy2=-1;
     90     if(l==r){
     91         tree[now].sum=a[rev[l]];
     92         return;
     93     }
     94     int mid=(l+r)>>1;
     95     build(now*2,l,mid);
     96     build(now*2+1,mid+1,r);
     97     pushup(now);
     98 }
     99 inline void modify1(int now,int l,int r,int v){
    100     if(tree[now].l>=l&&tree[now].r<=r){
    101         tree[now].sum+=(tree[now].r-tree[now].l+1)*v;
    102         tree[now].lazy1+=v;
    103         return;
    104     }
    105     pushdown(now);
    106     int mid=(tree[now].l+tree[now].r)>>1;
    107     if(l<=mid) modify1(now*2,l,r,v);
    108     if(r>mid) modify1(now*2+1,l,r,v);
    109     pushup(now);
    110 }
    111 inline void modify2(int now,int l,int r,int v){
    112     if(tree[now].l>=l&&tree[now].r<=r){
    113         tree[now].lazy2=v;
    114         tree[now].sum=(tree[now].r-tree[now].l+1)*v;
    115         tree[now].lazy1=0;
    116         return;
    117     }
    118     pushdown(now);
    119     int mid=(tree[now].l+tree[now].r)>>1;
    120     if(l<=mid) modify2(now*2,l,r,v);
    121     if(r>mid) modify2(now*2+1,l,r,v);
    122     pushup(now);
    123 }
    124 inline int query(int now,int l,int r){
    125     if(tree[now].l>=l&&tree[now].r<=r) return tree[now].sum;
    126     int mid=(tree[now].l+tree[now].r)>>1;
    127     pushdown(now);
    128     int val=0;
    129     if(l<=mid) val+=query(now*2,l,r);
    130     if(r>mid) val+=query(now*2+1,l,r);
    131     return val;
    132 }
    133 inline void link1(int x,int y,int v){
    134     while(top[x]!=top[y]){
    135         if(dep[top[x]]<dep[top[y]]) swap(x,y);
    136         modify1(1,id[top[x]],id[x],v);
    137         x=fa[top[x]];
    138     }
    139     if(dep[x]<dep[y]) swap(x,y);
    140     modify1(1,id[y],id[x],v);
    141 }
    142 inline void link2(int x,int y,int v){
    143     while(top[x]!=top[y]){
    144         if(dep[top[x]]<dep[top[y]]) swap(x,y);
    145         modify2(1,id[top[x]],id[x],v);
    146         x=fa[top[x]];
    147     }
    148     if(dep[x]<dep[y]) swap(x,y);
    149     modify2(1,id[y],id[x],v);
    150 }
    151 inline void linkquery(int x,int y){
    152     int ans=0;
    153     while(top[x]!=top[y]){
    154         if(dep[top[x]]<dep[top[y]]) swap(x,y);
    155         ans+=query(1,id[top[x]],id[x]);
    156         x=fa[top[x]];
    157     }
    158     if(dep[x]<dep[y]) swap(x,y);
    159     ans+=query(1,id[y],id[x]);
    160     if(ans<=3){printf("TANOSHI\n");return;}
    161     if(ans%2==0){printf("SUGOI\n");return;}
    162     int tmp=ans-2;
    163     if(not_zhishu[tmp]){printf("TANOSHI\n");return;}
    164     else{printf("SUGOI\n");return;}
    165 }
    166 int main(){
    167 //    freopen("japari.in","r",stdin);
    168 //    freopen("japari.out","w",stdout); 
    169     memset(son,-1,sizeof(son));
    170     Euler();
    171     scanf("%d%d",&n,&m);
    172     for(register int i=1;i<=n;i++){
    173         scanf("%d",&a[i]);
    174     } 
    175     for(register int i=1;i<n;i++){
    176         scanf("%d%d",&st,&ed);
    177         add(st,ed);add(ed,st);
    178     }
    179     dfs1(1,0);
    180     dfs2(1,1);
    181     build(1,1,n);
    182     for(register int i=1;i<=m;i++){
    183         scanf("%d",&opt);
    184         if(opt==1){
    185             scanf("%d%d%d",&x,&y,&k);
    186             link1(x,y,k);
    187         }
    188         else if(opt==2){
    189             scanf("%d%d%d",&x,&y,&k);
    190             link2(x,y,k);
    191         }
    192         else{
    193             scanf("%d%d",&x,&y);
    194             linkquery(x,y);
    195         } 
    196     }
    197     return 0;
    198 }

转载于:https://www.cnblogs.com/LJB666/p/11371344.html

[Link 1]: https://www.luogu.org/problem/T89894
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/ff014cc41faf493a83c53959b402a941.png