小C的棋王之路------（ODT）

相信珂学emmm，一眼板子题，直接珂朵莉树，set针对区间覆值进行启发式合并，使用内置二分函数lower_bound分裂区间左右端点，然后暴力模拟，十分简单粗暴，操作1和操作2都是暴力，直接for，为何不会超时，就因为有操作3，每次区间赋值，我们可以将区间合并为一个，直接用结构体表示struce node={l,r,val}，这就是珂朵莉树的精髓了，至于操作4的添加节点，因为一般来说set里面都会插入一个末尾节点，下标比数组大1，为了方便分裂区间右端点为数组末尾的操作,所以用一个变量记录数组末尾下标，然后每次操作4，先删除set的末尾节点，然后扩展一个新节点，然后标记末尾变量+1，再插入末尾标记。

至于结构体内为何要用一个mutable，因为不加就不行= =，加就对了

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define ll long long
#define pll pair<long long,long long>
#define P pair<int,int>
#define PP pair<P,P>
#define eps 1e-4
#define It set<node>::iterator
using namespace std;
const int maxn=1e5+10;
ll mod;
struct node {
    int l,r;
    mutable ll val;
    node(int l, int r=-1,ll val=-1):l(l),r(r),val(val) {}
    bool operator< (const node& n) const {
        return l<n.l;
    }
};
set<node> s;
int rep[maxn],n,m;
It split(int idx) {
    It it=s.lower_bound(node(idx));
    if (it!=s.end()&&it->l==idx) return it;
    --it;
    int l=it->l,r=it->r,val=it->val;
    s.erase(it);
    s.insert(node(l,idx-1,val));
    return s.insert(node(idx,r,val)).first;
}
void assign(int l, int r, int val) {
    It it2=split(r+1),it1=split(l);
    s.erase(it1,it2);
    s.insert(node(l,r,val));
}
void add(int l, int r, ll val) {
    It it2=split(r+1),it1=split(l);
    while (it1!=it2) {
        it1->val+=val;
        it1->val%=mod;
        it1++;
    }
}
void Mul(int l, int r, ll val) {
    It it2=split(r+1),it1=split(l);
    while (it1!=it2) {
        it1->val*=val;
        it1->val%=mod;
        it1++;
    }
}
ll solve(int l, int r) {
    It it2=split(r+1);
    It it1=split(l);
    ll res=0;
    while (it1!=it2) {
        res+=it1->val*(it1->r-it1->l+1);
        res%=mod;
        it1++;
    }
    return res;
}
int main() {
//  memset(rep,-1,sizeof(rep));
    scanf("%d%d%lld",&n,&m,&mod);
    for (int i=1; i<=n; i++) {
        ll num;
        scanf("%lld",&num);
        s.insert(node(i,i,num));
    }
    s.insert(node(n+1));
    int Last=n+1;
    while (m--) {
        int op,l,r;
        ll k;
        scanf("%d",&op);
        if (op==1) {
            scanf("%d%d%lld",&l,&r,&k);
            add(l,r,k);
        } else if (op==2) {
            scanf("%d%d%lld",&l,&r,&k);
            Mul(l,r,k);
        } else if (op==3) {
            scanf("%d%d%lld",&l,&r,&k);
            assign(l,r,k);
        } else if (op==4) {
            scanf("%lld",&k);
            It it=s.lower_bound(node(Last));
            s.erase(it);
            s.insert(node(Last,Last,k));
            Last+=1;
            s.insert(node(Last));
        } else if (op==5) {
            scanf("%d%d",&l,&r);
            printf("%lld\n",solve(l,r));
        }

    }

    return 0;
}