# 线段树

```//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;

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;
}
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);
}
}
}

void push_down(int rt,int l,int r){
}

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;
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;

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;
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;
}
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);
}
}
}

void push_down(int rt,int l,int r){
}

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;
}
}
```