很久以前写了个

int _n=1;
while(_n<n) _n<<=1;
n=_n;

也就是把 $n$ 扩大到第一个 $\ge n$ 的 $2$ 的正整数次幂再建树，操作之类的。

然后因为有点废空间，所以重构了一下代码……

然后……

AC & AC on #1,3,4

唯一的区别就是 AC 的那个进行了上面的操作，然后为什么会这样呀qaq

代码：

#include<iostream>
#include<cstdio>
//#define int long long
#define ll long long
#define il inline
using namespace std;

const int MAXN=2e5+5;
int n,q; ll m,a[MAXN];

struct node{ll ans=0,add=0,mul=1;};

class segment_tree
{
public:

    const ll &mod=m;
    ll *a;
    node v[MAXN<<2]={};

    il void pushup(int pos)
    {
        v[pos].ans=(v[pos<<1].ans+v[pos<<1|1].ans)%mod;
    }

    il void build(int l,int r,int pos)
    {
        if(l==r) return v[pos]={a[l],0ll,1ll},void();

        int mid=l+r>>1;
        build(l,mid,pos<<1),build(mid+1,r,pos<<1|1);
        pushup(pos);
    }

    il void addtag(int len,int pos,ll ka,ll km)
    {
        v[pos].ans=(v[pos].ans*km%mod+ka*len%mod)%mod;
        v[pos].mul=v[pos].mul*km%mod;
        v[pos].add=(v[pos].add*km%mod+ka)%mod;
    }

    il void pushdown(int len,int pos)
    {
        addtag(len>>1,pos<<1,v[pos].add,v[pos].mul);
        addtag(len>>1,pos<<1|1,v[pos].add,v[pos].mul);
        v[pos].add=0,v[pos].mul=1;
    }

    il void upd_add(int l,int r,int pos,int lt,int rt,ll k)
    {
        if(l>rt || r<lt) return;
        if(l>=lt && r<=rt) return addtag(r-l+1,pos,k,1ll),void();

        pushdown(r-l+1,pos);
        int mid=l+r>>1;
        upd_add(l,mid,pos<<1,lt,rt,k),upd_add(mid+1,r,pos<<1|1,lt,rt,k);
        pushup(pos);
    }

    il void upd_mul(int l,int r,int pos,int lt,int rt,ll k)
    {
        if(l>rt || r<lt) return;
        if(l>=lt && r<=rt) return addtag(r-l+1,pos,0ll,k),void();

        pushdown(r-l+1,pos);
        int mid=l+r>>1;
        upd_mul(l,mid,pos<<1,lt,rt,k),upd_mul(mid+1,r,pos<<1|1,lt,rt,k);
        pushup(pos);
    }

    il ll query(int l,int r,int pos,int lt,int rt)
    {
        if(l>rt || r<lt) return 0ll;
        if(l>=lt && r<=rt) return v[pos].ans;

        pushdown(r-l+1,pos);
        int mid=l+r>>1;
        return (query(l,mid,pos<<1,lt,rt)+query(mid+1,r,pos<<1|1,lt,rt))%mod;
    }
} tr;

signed main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n>>q>>m;
    for(int i=1;i<=n;++i) cin>>a[i];

    /* //这里是唯一的区别，加了就 AC，不加就 30pts
    int _n=1;
    while(_n<n) _n<<=1;
    n=_n;
    */

    tr.a=a;
    tr.build(1,n,1);

    int op,x,y; ll k;

    while(q--)
    {
        cin>>op;

        if(op==1) cin>>x>>y>>k,tr.upd_mul(1,n,1,x,y,k);
        else if(op==2) cin>>x>>y>>k,tr.upd_add(1,n,1,x,y,k);
        else cin>>x>>y,cout<<tr.query(1,n,1,x,y)<<'\n';
    }

    return 0;
}