6.Transformation

Transformation

#include<iostream>
#include<cstring>
#define qc std::ios::sync_with_stdio(false)
using namespace std;
const int maxl=1e5+10;
const int mod=10007;
struct seg_t
{
    int R,L,mid;
    int mul,add;
    long long sum[3];
};
seg_t tree[maxl<<2];
int n,m;
void debug(){
    // for(int i=1;i<n<<1;i++){
    //     cout<<tree[i].sum[0]<<" ";
    // }
    // cout<<endl;
}

void tree_caul(int k,int mul,int add){
    int len = tree[k].R - tree[k].L + 1;//区间大小
    tree[k].sum[0] = tree[k].sum[0] * mul %mod;//一次方
    tree[k].sum[1] = tree[k].sum[1] * mul %mod*mul%mod;//二次方 
    tree[k].sum[2] = tree[k].sum[2] * mul %mod*mul%mod*mul%mod;//三次方


    tree[k].mul = (tree[k].mul * mul )%mod;//乘法累加
    tree[k].add = ((tree[k].add * mul )% mod + add)%mod;//加法累加
    tree[k].sum[2] = (tree[k].sum[2] + 3*add%mod*add%mod *tree[k].sum[0]%mod)%mod;
    tree[k].sum[2] = (tree[k].sum[2] + 3*add%mod*tree[k].sum[1]%mod)%mod ;
    tree[k].sum[2] = (tree[k].sum[2] + len * add%mod *add %mod *add%mod)%mod;
    
    tree[k].sum[1] = (tree[k].sum[1] + 2*add%mod *tree[k].sum[0] %mod )%mod;
    tree[k].sum[1] = (tree[k].sum[1] + len*add%mod*add%mod)%mod;
 
    tree[k].sum[0] = (tree[k].sum[0] +len*add%mod)%mod;
}
void pushdown(int k){
    if(tree[k].L==tree[k].R){return;}
    tree_caul(k<<1,tree[k].mul,tree[k].add);
    tree_caul(k<<1|1,tree[k].mul,tree[k].add);
    tree[k].mul = 1;
    tree[k].add = 0;
}
void pushup(int k){
    for(int i=0;i<3;i++)
        tree[k].sum[i]=(tree[k<<1].sum[i]+tree[k<<1|1].sum[i])%mod;
}
void buid(int k,int l,int r){
    tree[k].L=l,tree[k].R=r,tree[k].mid=(l+r)>>1;
    if(tree[k].L==tree[k].R){
        for(int i=0;i<3;i++)
            tree[k].sum[i]=0;
        tree[k].mul=1;
        tree[k].add=0;
        //tree[k].sev_=false;
        return;
    }
    //if(tree[k].R<l||tree[k].L>r)return;
    buid(k<<1,tree[k].L,tree[k].mid);
    buid(k<<1|1,tree[k].mid+1,tree[k].R);
    pushup(k);
}
void tree_update(int k,int l,int r,int mx,int ax){
    if(tree[k].L>=l&&tree[k].R<=r){
        tree_caul(k,mx,ax);
        return;
    }
    pushdown(k);
    if(l<=tree[k].mid)tree_update(k<<1,l,r,mx,ax);
    if(r>tree[k].mid)tree_update(k<<1|1,l,r,mx,ax);
    pushup(k);
}
int querry(int k,int l,int r,int p){
    if(tree[k].L>=l&&tree[k].R<=r){
        return tree[k].sum[p]%mod;
    }
    pushdown(k);
    int ans_sum=0;
    if(l<=tree[k].mid)ans_sum+=querry(k<<1,l,r,p)%mod;
    if(r>tree[k].mid)ans_sum+=querry(k<<1|1,l,r,p)%mod;
    return ans_sum%mod;
}
int main(){
    qc;
    while (cin>>n>>m)
    {
        if(n==0&&m==0)break;
        memset(tree,0,sizeof(tree));
        buid(1,1,n);
        int f,a,b,c;
        while (m--)
        {
            cin>>f>>a>>b>>c;
            if(f==1)tree_update(1,a,b,1,c);
            if(f==2)tree_update(1,a,b,c,0);
            if(f==3)tree_update(1,a,b,0,c);
            if(f==4)cout<<querry(1,a,b,c-1)%mod<<endl;
        }
        
    }
};