P2023 [AHOI2009]维护序列区间加乘模板

题意：

有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式：N<=1e5
(1)把数列中的一段数全部乘一个值;
(2)把数列中的一段数全部加一个值;
(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

思路：

线段树,因为有可能存在，同时加和乘，所以lazy标记变为二维，一个记录乘，一个记录加

因为乘是总和乘一个数，所以先乘再加，这里需要注意，因为原本的区间和可能是zhi+lazy【加】，乘是总体，所以标记lazy【加】也要乘

 il void pushdown(int x,ll mod,int l,int r){

     if(lazy[x][]!=){

         tree[x<<]*=lazy[x][];tree[x<<]%=mod;

         tree[x<<|]*=lazy[x][];tree[x<<|]%=mod;

         lazy[x<<][]*=lazy[x][];lazy[x<<][]%=mod;

         lazy[x<<|][]*=lazy[x][];lazy[x<<|][]%=mod;

         lazy[x<<][]*=lazy[x][];lazy[x<<][]%=mod;

         lazy[x<<|][]*=lazy[x][];lazy[x<<|][]%=mod;

         lazy[x][]=;

     }

     if(lazy[x][]!=){

         int mid=(l+r)>>;

         tree[x<<]+=(mid-l+)*lazy[x][];tree[x<<]%=mod;

         tree[x<<|]+=(r-mid)*lazy[x][];tree[x<<|]%=mod;

         lazy[x<<][]+=lazy[x][];lazy[x<<][]%=mod;

         lazy[x<<|][]+=lazy[x][];lazy[x<<|][]%=mod;

         lazy[x][]=;

     }

 }

pushdown操作

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define il inline

 #define it register int

 #define inf 0x3f3f3f3f

 #define lowbit(x) (x)&(-x)

 #define mem(a,b) memset(a,b,sizeof(a))

 #define modd 998244353

 const int maxn=2e5+;

 int n,m,k;

 ll p;

 ll tree[maxn<<],lazy[maxn<<][],a[maxn];

 il void pushdown(int x,ll mod,int l,int r){

     if(lazy[x][]!=){

         tree[x<<]*=lazy[x][];tree[x<<]%=mod;

         tree[x<<|]*=lazy[x][];tree[x<<|]%=mod;

         lazy[x<<][]*=lazy[x][];lazy[x<<][]%=mod;

         lazy[x<<|][]*=lazy[x][];lazy[x<<|][]%=mod;

         lazy[x<<][]*=lazy[x][];lazy[x<<][]%=mod;

         lazy[x<<|][]*=lazy[x][];lazy[x<<|][]%=mod;

         lazy[x][]=;

     }

     if(lazy[x][]!=){

         int mid=(l+r)>>;

         tree[x<<]+=(mid-l+)*lazy[x][];tree[x<<]%=mod;

         tree[x<<|]+=(r-mid)*lazy[x][];tree[x<<|]%=mod;

         lazy[x<<][]+=lazy[x][];lazy[x<<][]%=mod;

         lazy[x<<|][]+=lazy[x][];lazy[x<<|][]%=mod;

         lazy[x][]=;

     }

 }

 il void pushup(int x,ll mod){

     tree[x]=(tree[x<<]+tree[x<<|])%mod;

 }

 void build(int x,int l,int r,ll mod){

     lazy[x][]=;lazy[x][]=;

     if(l==r){

         tree[x]=a[l];return;

     }

     int mid=(l+r)>>;

     build(x<<,l,mid,mod);

     build(x<<|,mid+,r,mod);

     pushup(x,mod);

 }

 void updatej(int x,int l,int r,int l1,int r1,ll zhi,ll mod){

     if(l1<=l && r<=r1){

         pushdown(x,mod,l,r);

         lazy[x][]=zhi;tree[x]+=(ll)(r-l+)*zhi;tree[x]%=mod;

         return;

     }

     pushdown(x,mod,l,r);

     int mid=(l+r)>>;

     if(l1<=mid){

         updatej(x<<,l,mid,l1,r1,zhi,mod);

     }

     if(r1>mid){

         updatej(x<<|,mid+,r,l1,r1,zhi,mod);

     }

     pushup(x,mod);

 }

 void updatec(int x,int l,int r,int l1,int r1,ll zhi,ll mod){

     if(l1<=l && r<=r1){

         pushdown(x,mod,l,r);

         lazy[x][]=zhi;tree[x]*=zhi;tree[x]%=mod;

         return;

     }

     pushdown(x,mod,l,r);

     int mid=(l+r)>>;

     if(l1<=mid){

         updatec(x<<,l,mid,l1,r1,zhi,mod);

     }

     if(r1>mid){

         updatec(x<<|,mid+,r,l1,r1,zhi,mod);

     }

     pushup(x,mod);

 }

 ll query(int x,int l,int r,int l1,int r1,ll mod){

     if(l1<=l && r<=r1){

        return tree[x];

     }

     pushdown(x,mod,l,r);

     int mid=(l+r)>>;

     ll sum=;

     if(l1<=mid){

         sum+=query(x<<,l,mid,l1,r1,mod);sum%=mod;

     }

     if(r1>mid){

         sum+=query(x<<|,mid+,r,l1,r1,mod);sum%mod;

     }

     return sum%mod;

 }

 int main(){

     scanf("%d%lld",&n,&p);

     for(it i=;i<=n;i++){

         scanf("%lld",&a[i]);a[i]%=p;

     }

     build(,,n,p);

     scanf("%d",&m);

     while(m--){//cout<<tree[1]<<endl;

         int t,g;

         ll c;

         scanf("%d",&k);

         if(k==){

             scanf("%d%d%lld",&t,&g,&c);

             updatec(,,n,t,g,c%p,p);

         }

         else if(k==){

             scanf("%d%d%lld",&t,&g,&c);

             updatej(,,n,t,g,c%p,p);

         }

         else{

             scanf("%d%d",&t,&g);

             printf("%lld\n",query(,,n,t,g,p));

         }

     }

     return ;

 }

这题也wa了好多遍，直到最后相通了，当加和乘同时存在的时候

巴特西

P2023 [AHOI2009]维护序列区间加乘模板

最新文章

热门文章

巴特西

P2023 [AHOI2009]维护序列 区间加乘模板

最新文章

热门文章

P2023 [AHOI2009]维护序列区间加乘模板