题目链接 https://www.luogu.org/problem/T89894
之前很久的一道题, 还是写一写, 这道题一眼就是树剖不用说了吧, 但是它要同时支持区间赋值和加法操作, 所以我们肯定需要两个标记, 但是当赋值和加法标记同时下方的时候, 就需要我们的细节处理, 首先赋值的初始值应该赋为 - 1, 而且下方的时候要先释放优先级高的赋值标记. 区间赋值的时候, 必须清空之前的加标记! 当时考试的时候就是因为这样爆零了, 惨痛的教训.
代码如下:
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=1e6+7;
- const int N=1e7+7;
- struct seg{
- int l,r,lazy1,lazy2;
- long long sum;
- }tree[maxn*10];
- struct node{
- int nxt,to;
- }edge[maxn*2];
- int n,m;
- int a[maxn];
- int dep[maxn],fa[maxn],size[maxn],id[maxn],son[maxn],rev[maxn],top[maxn];
- bool not_zhishu[N];
- int prime[maxn];
- int Time,cnt;
- int head[maxn];
- int opt,x,y,k;
- int st,ed;
- int jmr;
- bool flag;
- inline void Euler(){
- for( register int i=2;i<=10000000;i++){
- if(!not_zhishu[i]) prime[++prime[0]] = i;
- for(register int j=1;j<=prime[0]&&i*prime[j]<=10000000;j++){
- not_zhishu[i*prime[j]]=true;
- if(i%prime[j]==0) break;
- }
- }
- }
- inline void add(int u,int v){
- edge[++cnt].nxt=head[u];
- edge[cnt].to=v;
- head[u]=cnt;
- }
- inline void dfs1(int x,int f){
- dep[x]=dep[f]+1;
- fa[x]=f;
- size[x]=1;
- int maxson=-1;
- for(int i=head[x];i;i=edge[i].nxt){
- int v=edge[i].to;
- if(v==f) continue;
- dfs1(v,x);
- size[x]+=size[v];
- if(size[v]>maxson||son[x]==-1){
- maxson=size[v];
- son[x]=v;
- }
- }
- }
- inline void dfs2(int x,int topf){
- top[x]=topf;
- id[x]=++Time;
- rev[id[x]]=x;
- if(son[x]==-1) return;
- dfs2(son[x],topf);
- for(int i=head[x];i;i=edge[i].nxt){
- int v=edge[i].to;
- if(v==son[x]||v==fa[x]) continue;
- dfs2(v,v);
- }
- }
- inline void pushup(int x){
- tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
- }
- inline void pushdown(int x){
- if(tree[x].lazy2!=-1){
- tree[x*2].sum=tree[x].lazy2*(tree[x*2].r-tree[x*2].l+1);
- tree[x*2+1].sum=tree[x].lazy2*(tree[x*2+1].r-tree[x*2+1].l+1);
- tree[x*2].lazy2=tree[x].lazy2;
- tree[x*2+1].lazy2=tree[x].lazy2;
- tree[x].lazy2=-1;
- tree[x*2+1].lazy1=tree[x*2].lazy1=0;
- }
- if(tree[x].lazy1){
- tree[x*2].sum+=tree[x].lazy1*(tree[x*2].r-tree[x*2].l+1);
- tree[x*2+1].sum+=tree[x].lazy1*(tree[x*2+1].r-tree[x*2+1].l+1);
- tree[x*2].lazy1+=tree[x].lazy1;
- tree[x*2+1].lazy1+=tree[x].lazy1;
- tree[x].lazy1=0;
- }
- }
- inline void build(int now,int l,int r){
- tree[now].l=l;
- tree[now].r=r;
- tree[now].lazy1=0;
- tree[now].lazy2=-1;
- if(l==r){
- tree[now].sum=a[rev[l]];
- return;
- }
- int mid=(l+r)>>1;
- build(now*2,l,mid);
- build(now*2+1,mid+1,r);
- pushup(now);
- }
- inline void modify1(int now,int l,int r,int v){
- if(tree[now].l>=l&&tree[now].r<=r){
- tree[now].sum+=(tree[now].r-tree[now].l+1)*v;
- tree[now].lazy1+=v;
- return;
- }
- pushdown(now);
- int mid=(tree[now].l+tree[now].r)>>1;
- if(l<=mid) modify1(now*2,l,r,v);
- if(r>mid) modify1(now*2+1,l,r,v);
- pushup(now);
- }
- inline void modify2(int now,int l,int r,int v){
- if(tree[now].l>=l&&tree[now].r<=r){
- tree[now].lazy2=v;
- tree[now].sum=(tree[now].r-tree[now].l+1)*v;
- tree[now].lazy1=0;
- return;
- }
- pushdown(now);
- int mid=(tree[now].l+tree[now].r)>>1;
- if(l<=mid) modify2(now*2,l,r,v);
- if(r>mid) modify2(now*2+1,l,r,v);
- pushup(now);
- }
- inline int query(int now,int l,int r){
- if(tree[now].l>=l&&tree[now].r<=r) return tree[now].sum;
- int mid=(tree[now].l+tree[now].r)>>1;
- pushdown(now);
- int val=0;
- if(l<=mid) val+=query(now*2,l,r);
- if(r>mid) val+=query(now*2+1,l,r);
- return val;
- }
- inline void link1(int x,int y,int v){
- while(top[x]!=top[y]){
- if(dep[top[x]]<dep[top[y]]) swap(x,y);
- modify1(1,id[top[x]],id[x],v);
- x=fa[top[x]];
- }
- if(dep[x]<dep[y]) swap(x,y);
- modify1(1,id[y],id[x],v);
- }
- inline void link2(int x,int y,int v){
- while(top[x]!=top[y]){
- if(dep[top[x]]<dep[top[y]]) swap(x,y);
- modify2(1,id[top[x]],id[x],v);
- x=fa[top[x]];
- }
- if(dep[x]<dep[y]) swap(x,y);
- modify2(1,id[y],id[x],v);
- }
- inline void linkquery(int x,int y){
- int ans=0;
- while(top[x]!=top[y]){
- if(dep[top[x]]<dep[top[y]]) swap(x,y);
- ans+=query(1,id[top[x]],id[x]);
- x=fa[top[x]];
- }
- if(dep[x]<dep[y]) swap(x,y);
- ans+=query(1,id[y],id[x]);
- if(ans<=3){printf("TANOSHI\n");return;}
- if(ans%2==0){printf("SUGOI\n");return;}
- int tmp=ans-2;
- if(not_zhishu[tmp]){printf("TANOSHI\n");return;}
- else{printf("SUGOI\n");return;}
- }
- int main(){
- // freopen("japari.in","r",stdin);
- // freopen("japari.out","w",stdout);
- memset(son,-1,sizeof(son));
- Euler();
- scanf("%d%d",&n,&m);
- for(register int i=1;i<=n;i++){
- scanf("%d",&a[i]);
- }
- for(register int i=1;i<n;i++){
- scanf("%d%d",&st,&ed);
- add(st,ed);add(ed,st);
- }
- dfs1(1,0);
- dfs2(1,1);
- build(1,1,n);
- for(register int i=1;i<=m;i++){
- scanf("%d",&opt);
- if(opt==1){
- scanf("%d%d%d",&x,&y,&k);
- link1(x,y,k);
- }
- else if(opt==2){
- scanf("%d%d%d",&x,&y,&k);
- link2(x,y,k);
- }
- else{
- scanf("%d%d",&x,&y);
- linkquery(x,y);
- }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3160453.html