线段树

//hdu 4578
#define ls (rt<<1)
#define rs (ls|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=1e5+55;
int mod=10007;
int mul[maxn<<2],add[maxn<<2],cov[maxn<<2],sum[3][maxn<<2],a[maxn];

inline int modmul(int a,int b){return a*b%mod;}
inline int modmul(int a,int b,int c){return modmul(modmul(a,b),c);}
inline int modmul(int a,int b,int c,int d){return modmul(modmul(a,b,c),d);}

void push_son(int son,int l,int r,int covrt,int mulrt,int addrt){
    if(covrt!=-1){
        sum[0][son]=modmul(covrt,r-l+1);
        sum[1][son]=modmul(covrt,sum[0][son]);
        sum[2][son]=modmul(covrt,sum[1][son]);
        cov[son]=covrt;
        mul[son]=1;
        add[son]=0;
    }
    if(mulrt!=1){
        sum[0][son]=modmul(sum[0][son],mulrt);
        sum[1][son]=modmul(sum[1][son],mulrt,mulrt);
        sum[2][son]=modmul(sum[2][son],mulrt,mulrt,mulrt);
        mul[son]=modmul(mul[son],mulrt);
        add[son]=modmul(add[son],mulrt);
    }
    if(addrt!=0){//(x+d)^3=x^3+3*x^2*d+3*x*d^2+d^3
        sum[2][son]=(sum[2][son]+modmul(3,sum[1][son],addrt)+modmul(3,sum[0][son],addrt,addrt)+modmul(r-l+1,addrt,addrt,addrt))%mod;
        sum[1][son]=(sum[1][son]+modmul(2,addrt,sum[0][son])+modmul(r-l+1,addrt,addrt))%mod;
        sum[0][son]=(sum[0][son]+modmul(r-l+1,addrt))%mod;
        add[son]=(add[son]+addrt)%mod;
    }
}

void push_down(int rt,int l,int r){
    push_son(ls,l,ml,cov[rt],mul[rt],add[rt]);
    push_son(rs,mr,r,cov[rt],mul[rt],add[rt]);
    cov[rt]=-1; mul[rt]=1; add[rt]=0;
}

void push_up(int rt,int l,int r){
    sum[0][rt]=(sum[0][ls]+sum[0][rs])%mod;
    sum[1][rt]=(sum[1][ls]+sum[1][rs])%mod;
    sum[2][rt]=(sum[2][ls]+sum[2][rs])%mod;
}

void build(int rt,int l,int r){
    cov[rt]=-1;
    mul[rt]=1;
    add[rt]=0;
    if(l==r){
        sum[0][rt]=a[l];
        sum[1][rt]=modmul(a[l],a[l]);
        sum[2][rt]=modmul(a[l],a[l],a[l]);
    }
    else{
        build(ls,l,ml);
        build(rs,mr,r);
        push_up(rt,l,r);
    }
}

void update(int rt,int l,int r,int ql,int qr,int d,int type){
    if(l!=r) push_down(rt,l,r);
    if(ql<=l&&r<=qr){
        if(type==1) push_son(rt,l,r,-1,1,d);
        if(type==2) push_son(rt,l,r,-1,d,0);
        if(type==3) push_son(rt,l,r, d,1,0);
    }
    else{
        if(ml>=ql) update(ls,l,ml,ql,qr,d,type);
        if(mr<=qr) update(rs,mr,r,ql,qr,d,type);
        push_up(rt,l,r);
    }
}

int query(int rt,int l,int r,int ql,int qr,int pw){// pw-1
    if(l!=r) push_down(rt,l,r);
    if(ql<=l&&r<=qr){
        return sum[pw][rt];
    }
    else{
        int ret=0;
        if(ml>=ql) ret+=query(ls,l,ml,ql,qr,pw);
        if(mr<=qr) ret+=query(rs,mr,r,ql,qr,pw);
        return ret%mod;
    }
}

//更新动态开点
#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=1e5+55;
int mod=10007;
int mul[maxn*2],add[maxn*2],cov[maxn*2],sum[3][maxn*2],ls[maxn*2],rs[maxn*2],a[maxn],tot;

inline int modmul(int a,int b){return a*b%mod;}
inline int modmul(int a,int b,int c){return modmul(modmul(a,b),c);}
inline int modmul(int a,int b,int c,int d){return modmul(modmul(a,b,c),d);}

void push_son(int&son,int l,int r,int covrt,int mulrt,int addrt){
    if(son==0) {
        son=++tot;
        mul[son]=1;
        add[son]=0;
        cov[son]=-1;
        sum[0][son]=0;
        sum[1][son]=0;
        sum[2][son]=0;
        ls[son]=0;
        rs[son]=0;
    }
    if(covrt!=-1){
        sum[0][son]=modmul(covrt,r-l+1);
        sum[1][son]=modmul(covrt,sum[0][son]);
        sum[2][son]=modmul(covrt,sum[1][son]);
        cov[son]=covrt;
        mul[son]=1;
        add[son]=0;
    }
    if(mulrt!=1){
        sum[0][son]=modmul(sum[0][son],mulrt);
        sum[1][son]=modmul(sum[1][son],mulrt,mulrt);
        sum[2][son]=modmul(sum[2][son],mulrt,mulrt,mulrt);
        mul[son]=modmul(mul[son],mulrt);
        add[son]=modmul(add[son],mulrt);
    }
    if(addrt!=0){//(x+d)^3=x^3+3*x^2*d+3*x*d^2+d^3
        sum[2][son]=(sum[2][son]+modmul(3,sum[1][son],addrt)+modmul(3,sum[0][son],addrt,addrt)+modmul(r-l+1,addrt,addrt,addrt))%mod;
        sum[1][son]=(sum[1][son]+modmul(2,addrt,sum[0][son])+modmul(r-l+1,addrt,addrt))%mod;
        sum[0][son]=(sum[0][son]+modmul(r-l+1,addrt))%mod;
        add[son]=(add[son]+addrt)%mod;
    }
}

void push_down(int rt,int l,int r){
    push_son(ls[rt],l,ml,cov[rt],mul[rt],add[rt]);
    push_son(rs[rt],mr,r,cov[rt],mul[rt],add[rt]);
    cov[rt]=-1; mul[rt]=1; add[rt]=0;
}

void push_up(int rt,int l,int r){
    sum[0][rt]=(sum[0][ls[rt]]+sum[0][rs[rt]])%mod;
    sum[1][rt]=(sum[1][ls[rt]]+sum[1][rs[rt]])%mod;
    sum[2][rt]=(sum[2][ls[rt]]+sum[2][rs[rt]])%mod;
}

void build(int&rt,int l,int r){
    rt=tot=0;
    push_son(rt,l,r,-1,1,0);
}

void update(int rt,int l,int r,int ql,int qr,int d,int type){
    if(ql<=l&&r<=qr){
        if(type==1) push_son(rt,l,r,-1,1,d);
        if(type==2) push_son(rt,l,r,-1,d,0);
        if(type==3) push_son(rt,l,r, d,1,0);
    }
    else{
        push_down(rt,l,r);
        if(ml>=ql) update(ls[rt],l,ml,ql,qr,d,type);
        if(mr<=qr) update(rs[rt],mr,r,ql,qr,d,type);
        push_up(rt,l,r);
    }
}

int query(int rt,int l,int r,int ql,int qr,int pw){// pw-1
    if(ql<=l&&r<=qr){
        return sum[pw][rt];
    }
    else{
        push_down(rt,l,r);
        int ret=0;
        if(ml>=ql) ret+=query(ls[rt],l,ml,ql,qr,pw);
        if(mr<=qr) ret+=query(rs[rt],mr,r,ql,qr,pw);
        return ret%mod;
    }
}