线段树

作为一个没做过区间离散化的弱鸡要做出这题简直太难了，现在有五百多个提交，我一个人就贡献了五十多个WA（TAT）,我刚开始的时候还想着单纯的把这些点离散化，还纳闷怎么会错，果然还是太年轻。

看了其他大佬的题解也没太明白，y总的代码也没太看明白，就自己琢磨出了一个离散化（当然也可能跟各位大佬题解的离散化是一样的，只是我没发觉），仅供参考，如果觉得其他大佬的方法更简单或更实用，请直接无视我的。

举例说明，假如题目中的操作只涉及编号为 10，20，30，40 的点,那么可以令这些点自己成一个区间,即10-10,20-20,30-30,40-40,然后再把这些点之间的区域分别缩成点，即11-19，21-29，31-39；
这些区间从左到右依次为10-10,11-19,20-20,21-29,30-30,31-39,40-40,按顺序给上编号即可，然后需要记录一下每个区间的左边界和右边界，以计算区间的长度；还需要记一下每个左边界和右边界对应的区间编号，最后操作的时候要用到.

至于代码，其实我感觉我的码风跟大家的差别也是蛮大的…看看思路就行

C++ 代码

#include<bits/stdc++.h>
using namespace std;

struct node{
    int l,r;
    long long sum[3],add[3],mul,rev,len;//len为该结点对应的区间的长度
}tr[1000001];

struct q{
    int type;
    long long a,b,c,d,e;
};

unordered_map<long long,long long>le,ri,lloc,rloc;//le[i]表示以i为左边界的区间编号，ri[i]表示以i为右边界的区间编号
int n,m,idx,mod=1e9+7;//rloc[i]表示区间i的右边界位置，lloc[i]表示区间i的左边界位置，用以计算区间长度
vector<int>nums;//记录所有操作涉及的点
vector<q>qs;//暂存所有操作

void pushup(int x){
    node &u=tr[x],&l=tr[x<<1],&r=tr[x<<1|1];
    for(int i=0;i<3;i++){
        u.sum[i]=(l.sum[i]+r.sum[i])%mod;
    }
}

void rotate(node &u){
    int x=u.sum[0],ax=u.add[0];
    u.sum[0]=u.sum[1],u.sum[1]=u.sum[2],u.sum[2]=x;
    u.add[0]=u.add[1],u.add[1]=u.add[2],u.add[2]=ax;
}

void pushdown(int x){
    node &u=tr[x],&l=tr[x<<1],&r=tr[x<<1|1];

    for(int i=0;i<u.rev;i++){
        rotate(l),rotate(r);
    }
    l.rev=(l.rev+u.rev)%3;
    r.rev=(r.rev+u.rev)%3;
    u.rev=0;

    for(int i=0;i<3;i++){
        l.sum[i]=(l.sum[i]*u.mul%mod+l.len*u.add[i]%mod)%mod;
        r.sum[i]=(r.sum[i]*u.mul%mod+r.len*u.add[i]%mod)%mod;
        l.add[i]=(l.add[i]*u.mul%mod+u.add[i])%mod;
        r.add[i]=(r.add[i]*u.mul%mod+u.add[i])%mod;
        u.add[i]=0;
    }
    l.mul=l.mul*u.mul%mod;
    r.mul=r.mul*u.mul%mod;
    u.mul=1;
}

void build(int u,int l,int r){
    tr[u]={l,r,{0,0,0},{0,0,0},1,0,rloc[r]-lloc[l]+1};
    if(l==r) return;
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify_1(int u,int l,int r,long long a[]){//加
    if(tr[u].l>=l&&tr[u].r<=r){
        for(int i=0;i<3;i++){
            tr[u].sum[i]=(tr[u].sum[i]+a[i]*tr[u].len)%mod;
            tr[u].add[i]=(tr[u].add[i]+a[i])%mod;
        }
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify_1(u<<1,l,r,a);
    if(r>mid) modify_1(u<<1|1,l,r,a);
    pushup(u);
}

void modify_2(int u,int l,int r,long long mul){//乘
    if(tr[u].l>=l&&tr[u].r<=r){
        for(int i=0;i<3;i++){
            tr[u].sum[i]=tr[u].sum[i]*mul%mod;
            tr[u].add[i]=tr[u].add[i]*mul%mod;
        }
        tr[u].mul=tr[u].mul*mul%mod;
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify_2(u<<1,l,r,mul);
    if(r>mid) modify_2(u<<1|1,l,r,mul);
    pushup(u);
}

void modify_3(int u,int l,int r){//转向
    if(tr[u].l>=l&&tr[u].r<=r){
        rotate(tr[u]);
        tr[u].rev=(tr[u].rev+1)%3;
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify_3(u<<1,l,r);
    if(r>mid) modify_3(u<<1|1,l,r);
    pushup(u);
}

node query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u];
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    node res;
    memset(res.sum,0,sizeof res.sum);
    if(l<=mid){
        node rt=query(u<<1,l,r);
        for(int i=0;i<3;i++){
            res.sum[i]=(res.sum[i]+rt.sum[i])%mod;
        }
    }
    if(r>mid){
        node rt=query(u<<1|1,l,r);
        for(int i=0;i<3;i++){
            res.sum[i]=(res.sum[i]+rt.sum[i])%mod;
        }
    }
    return res;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        long long type,a,b,c,d,e;
        cin>>type;
        if(type==1){
            cin>>a>>b>>c>>d>>e;
            qs.push_back({type,a,b,c,d,e});
        }
        else if(type==2){
            cin>>a>>b>>c;
            qs.push_back({type,a,b,c});
        }
        else{
            cin>>a>>b;
            qs.push_back({type,a,b});
        }
        nums.push_back(a);
        nums.push_back(b);
    }

    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=0;i<nums.size();i++){
        idx++,le[nums[i]]=idx,ri[nums[i]]=idx,lloc[idx]=nums[i],rloc[idx]=nums[i];
        if(i!=nums.size()-1)
            idx++,le[nums[i]+1]=idx,ri[nums[i+1]-1]=idx,lloc[idx]=nums[i]+1,rloc[idx]=nums[i+1]-1;
    }

    build(1,1,idx);

    for(int i=0;i<m;i++){
        long long type=qs[i].type,a=qs[i].a,b=qs[i].b,c=qs[i].c,d=qs[i].d,e=qs[i].e;
        if(type==1){
            long long k[3]={c,d,e};
            modify_1(1,le[a],ri[b],k);
        }
        else if(type==2) modify_2(1,le[a],ri[b],c);
        else if(type==3) modify_3(1,le[a],ri[b]);
        else if(type==4){
            node res=query(1,le[a],ri[b]);
            long long sum=0;
            for(int i=0;i<3;i++){
                sum=(sum+res.sum[i]*res.sum[i])%mod;
            }
            cout<<sum<<endl;
        }
    }

    return 0;
}

```