Transformation(三重标记线段树)

发布于 2020-10-12  0 次阅读


题目大意:

Transformation

思路:

AC Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
#define INF 0x3f3f3f3f
const int M=10007;
const int N=1e5 +9;
int n, m , c, x, y, v;
struct segtree{
    int s1, s2, s3;
    int lazya, lazym, lazyc;
    void clear(){
        s1=s2=s3=0;
        lazya=lazyc=0;
        lazym=1;
    }
}tr[N<<2];
inline int lc(int p) {return p<<1;}
inline int rc(int p) {return p<<1|1;}
inline void push_up(int p){
    tr[p].s1=(tr[lc(p)].s1+tr[rc(p)].s1)%M;
    tr[p].s2=(tr[lc(p)].s2+tr[rc(p)].s2)%M;
    tr[p].s3=(tr[lc(p)].s3+tr[rc(p)].s3)%M;
}
inline void build(int p, int l, int r){ 
    tr[p].clear();
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(lc(p), l, mid);
	build(rc(p), mid+1, r);
}
inline void f(int f, int p, int len){
    int k;
	if(tr[f].lazyc){
        k=tr[f].lazyc;
        tr[p].s3=len*k*k*k%M;
        tr[p].s2=len*k*k%M;
        tr[p].s1=len*k%M;
        tr[p].lazya=0;
        tr[p].lazym=1;
        tr[p].lazyc=k;
    }
    if(tr[f].lazym!=1){
        k=tr[f].lazym;
        tr[p].s3=k*k*k*tr[p].s3%M;
        tr[p].s2=k*k*tr[p].s2%M;
        tr[p].s1=k*tr[p].s1%M;
        tr[p].lazya=k*tr[p].lazya%M;
        tr[p].lazym=k*tr[p].lazym%M;
    }
    if(tr[f].lazya){
        k=tr[f].lazya;
        tr[p].s3=(tr[p].s3 + len*k*k*k + 3*k*tr[p].s2 + 3*k*k*tr[p].s1)%M;
        tr[p].s2=(tr[p].s2 + len*k*k + 2*k*tr[p].s1)%M;
        tr[p].s1=(tr[p].s1 + len*k)%M;
        tr[p].lazya=(tr[p].lazya + k)%M;
    }
}
inline void push_down(int p, int lenl, int lenr){
	f(p, lc(p), lenl);
	f(p, rc(p), lenr);
	tr[p].lazya=tr[p].lazyc=0;
    tr[p].lazym=1;
}
inline void updata(int p, int l, int r, int x, int y, int k){
	if(l<=x && y<=r){
        int len=y-x+1;
        if(c==1){
            tr[p].lazya=(tr[p].lazya+k)%M;
            tr[p].s3=(tr[p].s3 + len*k*k*k + 3*k*tr[p].s2 + 3*k*k*tr[p].s1)%M;
            tr[p].s2=(tr[p].s2 + 2*k*tr[p].s1 + len*k*k)%M;
            tr[p].s1=(tr[p].s1 + len*k)%M;
        }
        else if(c==2){
            tr[p].lazya=tr[p].lazya*k%M;
            tr[p].lazym=tr[p].lazym*k%M;
            tr[p].s3=k*k*k*tr[p].s3%M;
            tr[p].s2=k*k*tr[p].s2%M;
            tr[p].s1=k*tr[p].s1%M;
        }
        else{
            tr[p].lazyc=k;
            tr[p].lazya=0;
            tr[p].lazym=1;
            tr[p].s3=len*k*k*k%M;
            tr[p].s2=len*k*k%M;
            tr[p].s1=len*k%M;
        }
		return ;
	}
	int mid=(x+y)>>1;
    push_down(p, mid-x+1, y-mid);
	if(l<=mid) updata(lc(p), l, r, x, mid, k);
	if(r>mid)  updata(rc(p), l, r, mid+1, y, k);
    push_up(p);
}

inline int query(int p, int l, int r, int x, int y){
	if(l<=x && y<=r){
        if(v==1)      return tr[p].s1;
        else if(v==2) return tr[p].s2;
        else          return tr[p].s3;
    }
    int mid=(x+y)>>1;
    push_down(p, mid-x+1, y-mid);
    int ans=0;
    if(l<=mid) ans=(ans+query(lc(p), l, r, x, mid))%M;
    if(r>mid)  ans=(ans+query(rc(p), l, r, mid+1, y))%M;
    return ans;
}
signed main(){
    while(~scanf("%lld%lld", &n, &m)&&(n||m)){
        build(1,1,n);
        for(int i=1; i<=m; i++){
            scanf("%lld%lld%lld%lld", &c, &x, &y, &v);
            if(c==4) printf("%lld\n", query(1,x,y,1,n));
            else     updata(1,x,y,1,n,v);
        }
    }
	return 0;
}

平平无奇的大学在读本科生