P2023-[AHOI2009]维护序列

曾经终败给现在 2023-06-01 08:57 3阅读 0赞

1 #include <bits/stdc++.h>
      2 typedef long long ll;
      3 using namespace std;
      4 #define _for(i,a,b) for(int i = (a);i < b;i ++)
      5 #define _rep(i,a,b) for(int i = (a);i > b;i --)
      6 #define INF 0x3f3f3f3f
      7 #define pb push_back
      8 #define maxn 100003
      9 inline ll read()
     10 {
     11     ll ans = 0;
     12     char ch = getchar(), last = ' ';
     13     while(!isdigit(ch)) last = ch, ch = getchar();
     14     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
     15     if(last == '-') ans = -ans;
     16     return ans;
     17 }
     18 inline void write(ll x)
     19 {
     20     if(x < 0) x = -x, putchar('-');
     21     if(x >= 10) write(x / 10);
     22     putchar(x % 10 + '0');
     23 }
     24 struct segtree
     25 {
     26     int l,r;
     27     ll sum,add;
     28     ll mul;
     29 #define l(x) t[x].l
     30 #define r(x) t[x].r
     31 #define sum(x) t[x].sum
     32 #define add(x) t[x].add
     33 #define mul(x) t[x].mul
     34 } t[maxn<<2];
     35 int a[maxn];
     36 int N,M;
     37 int MOD;
     38 void build(int p,int l,int r)
     39 {
     40     add(p) = 0;mul(p) = 1;
     41     l(p) = l,r(p) = r;
     42     if(l==r)
     43     {
     44         sum(p)=a[l];
     45         return ;
     46     }
     47     int mid = (l+r)/2;
     48     build(p*2,l,mid);
     49     build(p*2+1,mid+1,r);
     50     sum(p) = sum(p*2)+sum(p*2+1);
     51     sum(p) %= MOD;
     52 }
     53 void spread(int p)
     54 {
     55     if(add(p) == 0 and mul(p) == 1)
     56         return ;
     57     
     58     sum(p*2) = sum(p*2)*mul(p)+add(p)*(r(p*2)-l(p*2)+1);
     59     sum(p*2+1) = sum(p*2+1)*mul(p)+add(p)*(r(p*2+1)-l(p*2+1)+1);
     60     
     61     add(p*2) *= mul(p);add(p*2) += add(p);
     62     add(p*2+1) *= mul(p);add(p*2+1) += add(p);
     63     mul(p*2) *= mul(p);
     64     mul(p*2+1) *= mul(p);
     65     add(p) = 0;
     66     mul(p) = 1;
     67     sum(p*2) %= MOD;
     68     sum(p*2+1) %= MOD;
     69     add(p*2) %= MOD;
     70     add(p*2+1) %= MOD;
     71     mul(p*2) %= MOD;
     72     mul(p*2+1) %= MOD;
     73 }
     74 void change(int type,int p,int l,int r,int d)
     75 {
     76     if(l <= l(p) and r >= r(p))
     77     {
     78         if(type==1)
     79         {
     80             sum(p) += (ll)d * (r(p)-l(p)+1);
     81             add(p) += d;
     82         }
     83         else
     84         {
     85             sum(p) *= (ll)d;
     86             add(p) *= d;
     87             mul(p) *= d;
     88         }
     89         sum(p) %= MOD;
     90         add(p) %= MOD;
     91         mul(p) %= MOD;
     92         return ;
     93     }
     94     spread(p);
     95     int mid = (l(p)+r(p))/2;
     96     if(l <= mid)
     97         change(type,p*2,l,r,d);
     98     if(r > mid)
     99         change(type,p*2+1,l,r,d);
    100     sum(p) = sum(p*2)+sum(p*2+1);
    101     sum(p) %= MOD;
    102 }
    103 ll ask(int p,int l,int r)
    104 {
    105     if(l <= l(p) and r >= r(p))
    106         return sum(p);
    107     spread(p);
    108     int mid = (l(p)+r(p))/2;
    109     ll val = 0;
    110     if(l <= mid)
    111         val += ask(p*2,l,r);
    112     if(r > mid)
    113         val += ask(p*2+1,l,r);
    114     val %= MOD;
    115     return val;
    116 }
    117 int main()
    118 {
    119     N = read();
    120     MOD = read();
    121     _for(i,1,N+1)
    122     a[i] = read();
    123     build(1,1,N);
    124     M = read();
    125     _for(i,1,M+1)
    126     {
    127         int op = read();
    128         if(op==1)
    129         {
    130             int l = read();
    131             int r = read();
    132             int y = read();
    133             change(2,1,l,r,y);
    134         }
    135         else if(op==2)
    136         {
    137             int l = read();
    138             int r = read();
    139             int y = read();
    140             change(1,1,l,r,y);
    141         }
    142         else
    143         {
    144             int l = read();
    145             int r = read();
    146             printf("%lld\n",ask(1,l,r));
    147         }
    148     }
    149     return 0;
    150 }

转载于:https://www.cnblogs.com/Asurudo/p/11579439.html