hdu4578线段树区间更新

/*

只有在区间中的数字不相同时才pushdown：往子区间传递数字再到子区间更新，同时该区间的flag置0

更新完左右子区间后进行pushup，如果左右子区间数字相同，那么把子区间合并，子区间数字置0

*/

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

#define ll long long

#define mod 10007

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define maxn 200000

int n,q,flag[maxn<<],x[maxn<<];

inline void pushup(int rt){

    if(!flag[rt<<] || !flag[rt<<|])

        flag[rt]=;

    else if(x[rt<<]!=x[rt<<|])

        flag[rt]=;

    else flag[rt]=,x[rt]=x[rt<<];

}

inline void pushdown(int rt){

    if(flag[rt]){

        flag[rt<<]=flag[rt<<|]=;

        x[rt<<]=x[rt];

        x[rt<<|]=x[rt];

        flag[rt]=;

    }

}

void update(int L,int R,int op,int val,int l,int r,int rt){

    if(L<=l && R>=r && flag[rt]){

        if(op==)

            x[rt]=(x[rt]+val)%mod;

        else if(op==) x[rt]=x[rt]*val%mod;

        else x[rt]=val;

        return;

    }

    pushdown(rt);

    int m=l+r>>;

    if(L<=m) update(L,R,op,val,lson);

    if(R>m) update(L,R,op,val,rson);

    pushup(rt);

}

ll query(int L,int R,int val,int l,int r,int rt){

    if(L<=l && R>=r && flag[rt]){

        ll ans=;

        for(int i=;i<=val;i++)

            ans=(ans*x[rt])%mod;

        ans=(ans*(r-l+))%mod;

        return ans;

    }

    pushdown(rt);

    int m=l+r>>;

    ll ans=;

    if(L<=m) ans+=query(L,R,val,lson);

    if(R>m) ans+=query(L,R,val,rson);

    return ans%mod;

}

int main(){

    while(scanf("%d%d",&n,&q),n){

        memset(flag,,sizeof flag);

        memset(x,,sizeof x);

        int op,L,R,val;

        while(q--){

            scanf("%d%d%d%d",&op,&L,&R,&val);

            if(op<= && op>=) update(L,R,op,val,,n,);

            else printf("%lld\n",query(L,R,val,,n,));

        }

    }

    return ;

}