60pts求调，貌似取模少了（？）

P2023 [AHOI2009] 维护序列

@[The_Shadow_Dragon](/user/848964) 不会取模，于是肝了个 `int128` ```cpp #include<bits/stdc++.h> using namespace std; #define ll __int128_t inline ll read() { ll x = 0, f = 1; char c = getchar(); while(c > '9' || c < '0') { if(c == '-') { f = -1; } c = getchar(); } while(c <= '9' && c >= '0') { x = (x << 3) + (x << 1) + (c ^ '0'); c = getchar(); } return x * f; } inline void write(ll x) { if(x < 0) { putchar('-'); x = -x; } if(x > 9) { write(x / 10); } putchar((x % 10) + '0'); } ll a[2000001],n,m,p,i,pd,x,y,k; struct student { ll l,r,sum,lazyj,lazyc; }tree[2000001]; ll lson(ll x) { return x*2; } ll rson(ll x) { return x*2+1; } void pushup(ll rt) { tree[rt].sum=(tree[lson(rt)].sum%p+tree[rson(rt)].sum%p)%p; } void build(ll rt,ll l,ll r) { tree[rt].l=l; tree[rt].r=r; tree[rt].lazyc=1; if(l==r) { tree[rt].sum=a[l]%p; return; } ll mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } void pushdown(ll rt) { tree[lson(rt)].sum=(tree[lson(rt)].sum*tree[rt].lazyc+tree[rt].lazyj*(tree[lson(rt)].r-tree[lson(rt)].l+1))%p; tree[rson(rt)].sum=(tree[rson(rt)].sum*tree[rt].lazyc+tree[rt].lazyj*(tree[rson(rt)].r-tree[rson(rt)].l+1))%p; tree[lson(rt)].lazyc=(tree[rt].lazyc*tree[lson(rt)].lazyc)%p; tree[rson(rt)].lazyc=(tree[rt].lazyc*tree[rson(rt)].lazyc)%p; tree[lson(rt)].lazyj=(tree[rt].lazyc*tree[lson(rt)].lazyj+tree[rt].lazyj)%p; tree[rson(rt)].lazyj=(tree[rt].lazyc*tree[rson(rt)].lazyj+tree[rt].lazyj%p)%p; tree[rt].lazyj=0; tree[rt].lazyc=1; } void updatej(ll rt,ll l,ll r,ll val) { if(l<=tree[rt].l&&tree[rt].r<=r) { tree[rt].lazyj=(tree[rt].lazyj+val)%p; tree[rt].sum=(tree[rt].sum%p+val*(tree[rt].r-tree[rt].l+1))%p; return; } pushdown(rt); ll mid=(tree[rt].l+tree[rt].r)/2; if(l<=mid) { updatej(lson(rt),l,r,val); } if(mid<r) { updatej(rson(rt),l,r,val); } pushup(rt); } void updatec(ll rt,ll l,ll r,ll val) { if(l<=tree[rt].l&&tree[rt].r<=r) { tree[rt].lazyj*=val; tree[rt].lazyj%=p; tree[rt].lazyc*=val; tree[rt].lazyj%=p; tree[rt].sum*=val; tree[rt].sum%=p; return; } pushdown(rt); ll mid=(tree[rt].l+tree[rt].r)/2; if(l<=mid) { updatec(lson(rt),l,r,val); } if(mid<r) { updatec(rson(rt),l,r,val); } pushup(rt); } ll query(ll rt,ll l,ll r) { if(l<=tree[rt].l&&tree[rt].r<=r) { return tree[rt].sum%p; } pushdown(rt); ll mid=(tree[rt].l+tree[rt].r)/2,ans=0; if(l<=mid) { ans=(ans%p+query(lson(rt),l,r)%p)%p; } if(mid<r) { ans=(ans%p+query(rson(rt),l,r)%p)%p; } return ans%p; } int main() { n=read();p=read(); for(i=1;i<=n;i++) { a[i]=read(); } build(1,1,n); m=read(); for(i=1;i<=m;i++) { pd=read(); if(pd==1) { x=read();y=read();k=read(); updatec(1,x,y,k); } if(pd==2) { x=read();y=read();k=read(); updatej(1,x,y,k); } if(pd==3) { x=read();y=read(); write(query(1,x,y)%p); puts(""); } } return 0; } ```
by Loser_Syx @ 2023-03-11 10:29:08

@[Saint_ying_xtf](/user/852144) 有没有不用int128的方法
by hzoi_Shadow @ 2023-03-11 10:37:40

@[The_Shadow_Dragon](/user/848964) 在看
by Loser_Syx @ 2023-03-11 10:38:18

@[The_Shadow_Dragon](/user/848964) 话说您这防抄袭给我吓到了
by Loser_Syx @ 2023-03-11 10:39:36

@[Saint_ying_xtf](/user/852144) 这个取模貌似多了 ```cpp #include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; ll a[2000001],n,m,p,i,pd,x,y,k; struct student { ll l,r,sum,lazyj,lazyc; }tree[2000001]; ll lson(ll x) { return x*2; } ll rson(ll x) { return x*2+1; } void pushup(ll rt) { tree[rt].sum=((tree[lson(rt)].sum%p)+(tree[rson(rt)].sum)%p)%p; } void build(ll rt,ll l,ll r) { tree[rt].l=l; tree[rt].r=r; tree[rt].lazyc=1; if(l==r) { tree[rt].sum=a[l]%p; return; } ll mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } void pushdown(ll rt) { tree[lson(rt)].sum=((tree[lson(rt)].sum%p)*((tree[rt].lazyc%p)+((tree[rt].lazyj%p)*((tree[lson(rt)].r-tree[lson(rt)].l+1)%p))%p)%p)%p; tree[rson(rt)].sum=((tree[rson(rt)].sum%p)*((tree[rt].lazyc%p)+((tree[rt].lazyj%p)*((tree[rson(rt)].r-tree[rson(rt)].l+1)%p))%p)%p)%p; tree[lson(rt)].lazyc=((tree[rt].lazyc%p)*(tree[lson(rt)].lazyc%p))%p; tree[rson(rt)].lazyc=((tree[rt].lazyc%p)*(tree[rson(rt)].lazyc%p))%p; tree[lson(rt)].lazyj=((tree[rt].lazyc%p)*(tree[lson(rt)].lazyj%p)%p+(tree[rt].lazyj%p)%p)%p; tree[rson(rt)].lazyj=((tree[rt].lazyc%p)*(tree[rson(rt)].lazyj%p)%p+(tree[rt].lazyj%p)%p)%p; tree[rt].lazyj=0; tree[rt].lazyc=1; } void updatej(ll rt,ll l,ll r,ll val) { if(l<=tree[rt].l&&tree[rt].r<=r) { tree[rt].lazyj=(tree[rt].lazyj+val)%p; tree[rt].sum=(tree[rt].sum%p+(val%p)*(tree[rt].r-tree[rt].l+1)%p)%p; return; } pushdown(rt); ll mid=(tree[rt].l+tree[rt].r)/2; if(l<=mid) { updatej(lson(rt),l,r,val); } if(mid<r) { updatej(rson(rt),l,r,val); } pushup(rt); } void updatec(ll rt,ll l,ll r,ll val) { if(l<=tree[rt].l&&tree[rt].r<=r) { tree[rt].lazyj*=val; tree[rt].lazyj%=p; tree[rt].lazyc*=val; tree[rt].lazyj%=p; tree[rt].sum*=val; tree[rt].sum%=p; return; } pushdown(rt); ll mid=(tree[rt].l+tree[rt].r)/2; if(l<=mid) { updatec(lson(rt),l,r,val); } if(mid<r) { updatec(rson(rt),l,r,val); } pushup(rt); } ll query(ll rt,ll l,ll r) { if(l<=tree[rt].l&&tree[rt].r<=r) { return tree[rt].sum%p; } pushdown(rt); ll mid=(tree[rt].l+tree[rt].r)/2,ans=0; if(l<=mid) { ans=(ans+query(lson(rt),l,r))%p; } if(mid<r) { ans=(ans+query(rson(rt),l,r))%p; } return ans%p; } int main() { #ifndef ONLINE_JUDGE freopen("linshi.in","r",stdin); #endif cin>>n>>p; for(i=1;i<=n;i++) { cin>>a[i]; } build(1,1,n); cin>>m; for(i=1;i<=m;i++) { cin>>pd; if(pd==1) { cin>>x>>y>>k; updatec(1,x,y,k); } if(pd==2) { cin>>x>>y>>k; updatej(1,x,y,k); } if(pd==3) { cin>>x>>y; cout<<query(1,x,y)%p<<endl; } } return 0; }
by hzoi_Shadow @ 2023-03-11 10:40:39

@[Saint_ying_xtf](/user/852144) 我第一份代码还有一堆没有define的long long
by hzoi_Shadow @ 2023-03-11 10:43:41

@[The_Shadow_Dragon](/user/848964) ~~事实证明我调不出来了~~
by Loser_Syx @ 2023-03-11 10:46:03

@[Saint_ying_xtf](/user/852144) 说实话，我马蜂已经快把我同学们逼疯了
by hzoi_Shadow @ 2023-03-11 10:53:51

@[The_Shadow_Dragon](/user/848964) 这码风还行啊，我调过最离谱的一次代码是某lz不换行
by Loser_Syx @ 2023-03-11 10:54:43

@[Saint_ying_xtf](/user/852144) az（可参考[我上个帖子](https://www.luogu.com.cn/discuss/574224)，当时把我多位同学逼疯了，一个个都说要刀了我）
by hzoi_Shadow @ 2023-03-11 10:57:40