记录编号	553015	评测结果	AAAAAAAAAA
题目名称	2961.[SYOI 2018] 简单的线段树	最终得分	100
用户昵称	fw	是否通过	通过
代码语言	C++	运行时间	2.442 s
提交时间	2020-08-10 16:24:52	内存使用	16.92 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100100;
struct Segent_tree {
    ll l,r,sum,plz,mlz;
    Segent_tree () {
        l = r = sum = plz = 0;
        mlz = 1;
    }
}tree[MAXN << 2]; 
ll n,m,p;
ll a[MAXN] = {0};
void pushup(ll i) {
    tree[i].sum = (tree[i << 1].sum + tree[i << 1 | 1].sum) % p;
    return ;
}
void pushdown(ll i) {
    if (tree[i].plz || tree[i].mlz > 1) {
        tree[i << 1].mlz = (tree[i << 1].mlz * tree[i].mlz) % p;
        tree[i << 1 | 1].mlz = (tree[i << 1 | 1].mlz * tree[i].mlz) % p;
        
        tree[i << 1].plz = (tree[i].mlz * tree[i << 1].plz + tree[i].plz) % p;
        tree[i << 1 | 1].plz = (tree[i].mlz * tree[i << 1 | 1].plz + tree[i].plz) % p;
        
        tree[i << 1].sum = (tree[i << 1].sum * tree[i].mlz + tree[i].plz * (tree[i << 1].r - tree[i << 1].l + 1)) % p;
        tree[i << 1 | 1].sum = (tree[i << 1 | 1].sum * tree[i].mlz + tree[i].plz * (tree[i << 1 | 1].r - tree[i << 1 | 1].l + 1)) % p;
        
        tree[i].mlz = 1;
        tree[i].plz = 0;
    }
    return ;
}
void build (ll i,int l,int r) {
    tree[i].l = l;
    tree[i].r = r;
    if (l == r) {
        tree[i].sum = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build (i << 1,l,mid);
    build (i << 1 | 1,mid + 1,r);
    tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
    return ;
}
ll search (ll i,int l,int r) {
    if (tree[i].l >= l && tree[i].r <= r) {
        return tree[i].sum % p;
    }
    if (tree[i].l > r || tree[i].r < l) return 0;
    pushdown(i);
    ll s = 0;
    if (tree[i << 1].r >= l) s += search (i << 1,l,r);
    if (tree[i << 1 | 1].l <= r) s += search (i << 1 | 1,l,r);
    return s % p;
}
void add (ll i,int l,int r,ll k) {
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].sum = (tree[i].sum + k * (tree[i].r - tree[i].l + 1)) % p;
        tree[i].plz = (tree[i].plz + k) % p;
        return ;
    }
    if (tree[i].l > r || tree[i].r < l) return ;
    pushdown (i);
    
    if (tree[i << 1].r >= l) add (i << 1,l,r,k);
    if (tree[i << 1 | 1].l <= r) add (i << 1 | 1,l,r,k);
    pushup (i);
    return ;
}
void mul (ll i,int l,int r,ll k) {
    if (tree[i].l >= l && tree[i].r <= r) {
        tree[i].sum = (tree[i].sum * k) % p;
        tree[i].plz = (tree[i].plz * k) % p;
        tree[i].mlz = (tree[i].mlz * k) % p;
        return ;
    }
    if (tree[i].l > r || tree[i].r < l) return ;
    pushdown (i);
    
    if (tree[i << 1].r >= l) mul (i << 1,l,r,k);
    if (tree[i << 1 | 1].l <= r) mul (i << 1 | 1,l,r,k);
    pushup (i);
    return ;
}
int main () {
    freopen("easilysegmenttree.in","r",stdin);
    freopen("easilysegmenttree.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&p);
    build (1,1,n);
    int cm;
    int a1,b1,c1;
    for (int q = 1;q <= m;++ q) {
        scanf("%d",&cm);
        if (cm == 1) {
            scanf("%d%d%d",&a1,&b1,&c1);
            add (1,a1,b1,c1);
        }
        else if (cm == 2) {
            scanf("%d%d%d",&a1,&b1,&c1);
            mul (1,a1,b1,c1);
        }
        else if (cm == 3) {
            scanf("%d%d",&a1,&b1);
            printf ("%llu\n",search (1,a1,b1) % p);
        }
    }
    return 0;
}