链接:hdu4578[多标记]
题解
- 非常裸的线段树,但是很麻烦,三个标记很多细节考虑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
using namespace std;
const int N=100000+5;
const int p=10007;
ll sum[3][N<<2],add[N<<2],st[N<<2],mul[N<<2];
int n,m;
inline void pushup(int o){rep(i,0,2)sum[i][o]=(sum[i][o<<1]+sum[i][o<<1|1])%p;}
inline void pushdown(int o,int l,int r){
int mid=l+r>>1;
if(st[o]){
add[o<<1]=add[o<<1|1]=0;
mul[o<<1]=mul[o<<1|1]=1;
st[o<<1]=st[o<<1|1]=st[o];
rep(i,0,2){
sum[i][o<<1]=(mid-l+1)*(ll)pow(st[o],i+1)%p;
sum[i][o<<1|1]=(r-mid)*(ll)pow(st[o],i+1)%p;
}
st[o]=0;
}
if(mul[o]!=1){
mul[o<<1]=mul[o<<1]*mul[o]%p;
mul[o<<1|1]=mul[o<<1|1]*mul[o]%p;
if(add[o<<1])add[o<<1]=add[o<<1]*mul[o]%p;
if(add[o<<1|1])add[o<<1|1]=add[o<<1|1]*mul[o]%p;
sum[2][o<<1]=sum[2][o<<1]*mul[o]%p*mul[o]%p*mul[o];
sum[2][o<<1|1]=sum[2][o<<1|1]*mul[o]%p*mul[o]%p*mul[o];
sum[1][o<<1]=sum[1][o<<1]*mul[o]%p*mul[o]%p;
sum[1][o<<1|1]=sum[1][o<<1|1]*mul[o]%p*mul[o]%p;
sum[0][o<<1]=sum[0][o<<1]*mul[o]%p;
sum[0][o<<1|1]=sum[0][o<<1|1]*mul[o]%p;
mul[o]=1;
}
if(add[o]){
add[o<<1]+=add[o];
add[o<<1|1]+=add[o];
ll tp=add[o]*add[o]%p*add[o]%p;
sum[2][o<<1]=(sum[2][o<<1]+tp*(mid-l+1)%p+3*add[o]*(sum[1][o<<1]+sum[0][o<<1]*add[o]%p)%p)%p;
sum[2][o<<1|1]=(sum[2][o<<1|1]+tp*(r-mid)%p+3*add[o]*(sum[1][o<<1|1]+sum[0][o<<1|1]*add[o]%p)%p)%p;
sum[1][o<<1]=(sum[1][o<<1]+2*sum[0][o<<1]*add[o]%p+add[o]*add[o]%p*(mid-l+1)%p)%p;
sum[1][o<<1|1]=(sum[1][o<<1|1]+2*sum[0][o<<1|1]*add[o]%p+add[o]*add[o]%p*(r-mid)%p)%p;
sum[0][o<<1]=(sum[0][o<<1]+add[o]*(mid-l+1))%p;
sum[0][o<<1|1]=(sum[0][o<<1|1]+add[o]*(r-mid))%p;
add[o]=0;
}
}
inline void build(int o,int l,int r){
add[o]=st[o]=0;mul[o]=1;
if(l==r){rep(i,0,2)sum[i][o]=0;return ;}
int mid=l+r>>1;
build(lson);
build(rson);
pushup(o);
}
inline void update(int o,int l,int r,int L,int R,int op,int c){
if(L<=l&&R>=r){
if(op==3){
st[o]=c;
add[o]=0;mul[o]=1;
sum[0][o]=(r-l+1)*c%p;
sum[1][o]=(r-l+1)*c%p*c%p;
sum[2][o]=(r-l+1)*c%p*c%p*c%p;
}
if(op==2){
mul[o]=mul[o]*c%p;
if(add[o])add[o]=(add[o]*c)%p;
sum[0][o]=sum[0][o]*c%p;
sum[1][o]=sum[1][o]*c%p*c%p;
sum[2][o]=sum[2][o]*c%p*c%p*c%p;
}
if(op==1){
add[o]+=c;
ll tp=c*c%p*c%p;
sum[2][o]=(sum[2][o]+tp*(r-l+1)%p+3*c*(sum[1][o]+c*sum[0][o]%p))%p;
sum[1][o]=(sum[1][o]+c*c%p*(r-l+1)%p+2*c%p*sum[0][o]%p)%p;
sum[0][o]=(sum[0][o]+c*(r-l+1))%p;
}
return ;
}
pushdown(o,l,r);
int mid=l+r>>1;
if(L<=mid)update(lson,L,R,op,c);
if(R>mid)update(rson,L,R,op,c);
pushup(o);
}
inline int query(int o,int l,int r,int L,int R,int op){
if(L<=l&&R>=r)return sum[op-1][o]%p;
pushdown(o,l,r);
int mid=l+r>>1;
ll ans=0;
if(L<=mid)ans+=query(lson,L,R,op);
if(R>mid)ans+=query(rson,L,R,op);
return ans%p;
}
int main(){
while(~scanf("%d%d",&n,&m)){
if(!n&&!m)break;
build(1,1,n);
while(m--){
int x,l,r,c;
scanf("%d%d%d%d",&x,&l,&r,&c);
if(x==4)printf("%d\n",query(1,1,n,l,r,c));
else update(1,1,n,l,r,x,c);
}
}
return 0;
}