本文共 5498 字，大约阅读时间需要 18 分钟。

A-环鸽的CHONG

赛时想到了题解的做法，但是最糟糕的情况是n^2的，就没敢写，没想到官方题解还真是这么写的？？？什么鬼，而且不是很容易就能构造hack数据吗

更新：啊，是我分析错了，官方题解正解

#include 
   
    using namespace std;const int maxn=5e5+5;map
    
      mp;int n,num[maxn],nex[maxn],pre[maxn];bool dfs(int l,int r){    if (l>=r) return 1;    int i=l,j=r;    int mid;    while (i<=j)    {        if (pre[i]
     
      r) {//i是区间[l,r]内的唯一数             mid=i;            break;        }        if (pre[j]
      
       r) {            mid=j;            break;        }        i++, j--;    }    if (i>j) return 0;    return (dfs(l,mid-1)&&dfs(mid+1,r));} int main(){    scanf("%d", &n);    for (int i=1;i<=n;i++)        scanf("%d",&num[i]);    mp.clear();    for (int i=1;i<=n;i++)    {        if (!mp.count(num[i]))        {            pre[i]=0;            mp[num[i]]=i;        }        else        {            int pos=mp[num[i]];            pre[i]=pos;            mp[num[i]]=i;        }    }     mp.clear();    for (int i=n;i>=1;i--)    {        if (!mp.count(num[i]))        {            nex[i]=n+1;            mp[num[i]]=i;        }        else        {            int pos=mp[num[i]];            nex[i]=pos;            mp[num[i]]=i;        }    }        printf((dfs(1,n)?"chong\n":"fuchong\n"));    return 0;}
      
     
    
   

这题写了我两个小时，在cf延时的15分钟内调出来了，直呼内行

D-小C的棋王之路

给个节点用k*x+val 表示lazy更新   初始叶子节点k=1 val=a[l]  其他  k=1  val=0

一个mul数组，记录每个节点的前面的系数k，val数组记录后面val的值  sum数组记录区间和，因为询问的是区间和

每次区间乘了一个k：

某个节点记录：

mul[id]*=k

val[id]*=k

sum[id]*=k

mul[id]=k*mul[id]%mod;val[id]=k*val[id]%mod;sum[id]=k*sum[id]%mod;

区间加了一个k:

val[id]+=k

sum[id]+k*(r-l+1） (l,r是某个节点的信息）

add(val[id],k);add(sum[id],k*(r-l+1)%mod);

区间覆盖：（惊天妙手，突然想到的处理方式）

mul[id]=0;

val[id]=k;

 sum[id]=k*(r-l+1)

mul[id]=0;val[id]=k;sum[id]=k*(r-l+1)%mod;

lazy更新：相当于某个节点同时来k倍系数以及加了个 后缀的x值

假设k、x是由id的父亲节点传来，

mul[id]*=k;

val[id]=x+k*val[id]

sum[id]=sum[id]*k+x*(r-l+1)

int root=id,len=r-l+1;ll p=mod;mul[id<<1]=mul[id]*mul[id<<1]%mod;val[id<<1]=(val[id]+val[id<<1]*mul[id]%mod)%mod;sum[root<<1]=(sum[root<<1]*mul[root]%p+val[root]*(len-(len>>1))%p)%p;mul[id<<1|1]=mul[id]*mul[id<<1|1]%mod;val[id<<1|1]=(val[id]+val[id<<1|1]*mul[id]%mod)%mod;sum[root<<1|1]=(sum[root<<1|1]*mul[root]%p+val[root]*(len>>1)%p)%p;

 

#pragma GCC optimize(2)#include
   
    #define ll long long#define maxn 1005#define inf 1e9#define pb push_back#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)using namespace std;inline ll read(){	ll x=0,w=1; char c=getchar();	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}	return w==1?x:-x;}const int N=2e5+10;ll n,m,mod;int mx;struct node{    int ty,l,r;    ll k;}a[N];ll mul[4*N],val[4*N],sum[4*N],t[N];int st[4*N];void add(ll &x,ll y){    x=(x+y)%mod;}void build(int id,int l,int r){    mul[id]=1;    if(l==r){       sum[id]=t[l];        return ;    }    int mid=l+r>>1;    build(id<<1,l,mid);    build(id<<1|1,mid+1,r);    sum[id]=(sum[id<<1]+sum[id<<1|1])%mod;}void pushdown(int id,int l,int r){    int mid=l+r>>1;    if(mul[id]==1&&val[id]==0) return;    int root=id,len=r-l+1;    ll p=mod;    mul[id<<1]=mul[id]*mul[id<<1]%mod;    val[id<<1]=(val[id]+val[id<<1]*mul[id]%mod)%mod;    sum[root<<1]=(sum[root<<1]*mul[root]%p+val[root]*(len-(len>>1))%p)%p;    mul[id<<1|1]=mul[id]*mul[id<<1|1]%mod;    val[id<<1|1]=(val[id]+val[id<<1|1]*mul[id]%mod)%mod;    sum[root<<1|1]=(sum[root<<1|1]*mul[root]%p+val[root]*(len>>1)%p)%p;    mul[id]=1,val[id]=0;}ll qu(int id,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return sum[id];    int mid=l+r>>1;    ll ans=0;    pushdown(id,l,r);    if(ql<=mid) ans=qu(id<<1,l,mid,ql,qr);    if(qr>mid) add(ans,qu(id<<1|1,mid+1,r,ql,qr));    //sum[id]=(sum[id<<1|1]+sum[id<<1])%mod;    return ans;}void up(int id,int l,int r,int ql,int qr,ll k,int ty){    if(ql<=l&&r<=qr){        if(ty==1){            //printf("id:%d sum[id]:%lld\n",id,sum[id]);            add(val[id],k);            add(sum[id],k*(r-l+1)%mod);            //printf("id:%d sum[id]:%lld\n",id,sum[id]);        }        else if(ty==2){            mul[id]=k*mul[id]%mod;            val[id]=k*val[id]%mod;            sum[id]=k*sum[id]%mod;        }        else if(ty==3){            st[id]=-1;            mul[id]=0;            val[id]=k;            sum[id]=k*(r-l+1)%mod;        }        else{            mul[id]=1,val[id]=k;            sum[id]=k*(r-l+1)%mod;        }        return ;    }    pushdown(id,l,r);    int mid=l+r>>1;    if(ql<=mid) up(id<<1,l,mid,ql,qr,k,ty);    if(qr>mid) up(id<<1|1,mid+1,r,ql,qr,k,ty);    sum[id]=(sum[id<<1|1]+sum[id<<1])%mod;}int main(){    n=read(),m=read(),mod=read();    mx=n;    rep(i,1,n) t[i]=read();    for(int i=1;i<=m;++i){        scanf("%d%d",&a[i].ty,&a[i].l);        if(a[i].ty==5) scanf("%d",&a[i].r);        else if(a[i].ty==4) mx++;        else scanf("%d%lld",&a[i].r,&a[i].k),a[i].k%=mod;        a[i].r=min(a[i].r,mx);        a[i].r=min(a[i].r,mx);    }    build(1,1,mx);    int now=n;    for(int i=1;i<=m;++i){        if(a[i].ty==1){           up(1,1,mx,a[i].l,a[i].r,a[i].k,1);        }        else if(a[i].ty==2){           up(1,1,mx,a[i].l,a[i].r,a[i].k,2);        }        else if(a[i].ty==3){           up(1,1,mx,a[i].l,a[i].r,a[i].k,3);        }        else if(a[i].ty==4){           up(1,1,mx,++now,now,a[i].l,4);        }        else if(a[i].ty==5){           printf("%lld\n",qu(1,1,mx,a[i].l,a[i].r));        }    }}/*5 6 95551 1 1 1 13 2 5 55 1 51 1 4 51 1 5 51 3 5 55 1 45 12 95551 1 1 1 13 2 5 51 1 4 51 1 5 51 3 5 55 1 42 1 5 52 2 2 53 5 5 53 3 5 55 1 31 2 3 55 1 3*/
   

转载地址：https://ccsudeer.blog.csdn.net/article/details/106185780 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！