【bzoj1798】Seq维护序列

描述 Description

西行妖又开花了,于是幽灵们排着队到西行寺来观赏樱花,但可怕的是,幽幽子的结界在这个关键的时候却坏了,已经在庭院中的幽灵可以自由召唤自己熟识的幽灵,并且其他幽灵也可以自由从进入庭院。妖梦需要知道一段区间内幽灵的数量才可以放心使用【迷津慈航斩】来清理掉幽灵而不至于破坏庭院。于是她找到了Sakaki,但悲催的Sakaki月考考砸正在补作业,连自己喜欢的女孩都帮不了,所以他找到了你,希望你能解决这个问题。
庭院中的幽灵可以近似看做一条长度为N的线,因为幽灵没有实体所以在单位长度内可以有若干只幽灵,一段区间[ L , R ]内的幽灵可以同时作法,这时区间内的每只幽灵都会召来 C – 1 只幽灵,每只幽灵所召唤的幽灵都会落在自己所在的单位长度内,幽灵也会从天而降,在区间[ L , R ]内每单位区间落下C只幽灵。当妖梦要使用【迷津慈航斩】的时候,就会向你询问区间[ L , R ]内幽灵数的总和(ps 当然幽灵是灵体,是不会消失的,攻击只会使他们暂时迷惘),当然这个数会很大,你只需要输出这个数对5201314取模(膜)的值。

  • 去tmd垃圾题面

  • 区间加法

  • 区间乘法

  • 维护区间和输出取膜

输入格式 Input Format

第一行为两个整数N和M
N为幽灵队列的长度,M为操作的次数
接下来有N个数,第i个数表示第i个单位长度内最初有几个幽灵
从第三行开始每行有一个操作
操作1:“1 L R C” 区间[ L , R ]内每只幽灵召唤C-1只幽灵在自己的单位长度内;
操作2:“2 L R C”区间[ L, R ]内每单位区间增加C只幽灵;
操作3:“3 L R”查询区间[ L, R ]内幽灵数量的总和模5201314的值
同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。

输出格式 Output Format

对每个操作3,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。

样例输入 Sample Input

7 5
1 2 3 4 5 6 7
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

样例输出 Sample Output

45
35
94

线段树模板题…

Code

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>
#include<algorithm>
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define INF 2100000000
#define maxn 100100
#define intt long long
#define mo 5201314
using namespace std;
intt ax,ay,x,y,q,c;
intt n,m;
struct qaq{
intt maxx,deladd;
intt delx;
}tree[maxn*4];

intt read(){
intt f=1;
intt k=0;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
k=(k<<3)+(k<<1)+c-'0';
c=getchar();
}
return f*k;
}

void push_down(intt id,intt l,intt r){
if(tree[id].delx==1&&tree[id].deladd==0) return;
intt tad=tree[id].deladd;
intt txx=tree[id].delx;
intt mid=(l+r)>>1;
tree[L(id)].deladd=(tree[L(id)].deladd*txx+tad)%mo;
tree[R(id)].deladd=(tree[R(id)].deladd*txx+tad)%mo;
tree[L(id)].delx=(tree[L(id)].delx*txx)%mo;
tree[R(id)].delx=(tree[R(id)].delx*txx)%mo;
tree[L(id)].maxx=(tree[L(id)].maxx*txx+(mid-l+1)*tad)%mo;
tree[R(id)].maxx=(tree[R(id)].maxx*txx+(r-(mid+1)+1)*tad)%mo;
tree[id].deladd=0;
tree[id].delx=1;
return;
}

void build(intt l,intt r,intt id,intt v){
if(l>y||r<x) return;
tree[id].delx=1;
tree[id].deladd=0;
if(x<=l&&r<=y){
tree[id].maxx=v;
//cout<<v<<endl;
return;
}
intt mid=(l+r)>>1;
build(l,mid,L(id),v);
build(mid+1,r,R(id),v);
tree[id].maxx=(tree[L(id)].maxx+tree[R(id)].maxx)%mo;
//cout<<tree[id].maxx<<endl;
return;
}

void updatax(intt l,intt r,intt id,intt v){
if(l>y||r<x) return;
if(x<=l&&r<=y){
tree[id].deladd=(tree[id].deladd*v)%mo;
tree[id].delx=(tree[id].delx*v)%mo;
tree[id].maxx=(tree[id].maxx*v)%mo;
return;
}
push_down(id,l,r);
intt mid=(l+r)>>1;
updatax(l,mid,L(id),v);
updatax(mid+1,r,R(id),v);
tree[id].maxx=(tree[L(id)].maxx+tree[R(id)].maxx)%mo;
return;
}

void updataadd(intt l,intt r,intt id,intt v){
if(l>y||r<x) return;
if(x<=l&&r<=y){
tree[id].deladd=(tree[id].deladd+v)%mo;
tree[id].maxx=(tree[id].maxx+(r-l+1)*v)%mo;
return;
}
push_down(id,l,r);
intt mid=(l+r)>>1;
updataadd(l,mid,L(id),v);
updataadd(mid+1,r,R(id),v);
tree[id].maxx=(tree[L(id)].maxx+tree[R(id)].maxx)%mo;
return;
}

intt findit(int l,int r,int id){
if(l>y||r<x) return 0;
if(x<=l&&r<=y){
//cout<<tree[id].
return tree[id].maxx%mo;
}
push_down(id,l,r);
intt mid=(l+r)>>1;
intt t1=findit(l,mid,L(id));
intt t2=findit(mid+1,r,R(id));
return (t1+t2)%mo;
}

int main(){
//freopen("a.txt","r",stdin);
//freopen("b.txt","w",stdout);
memset(tree,0,sizeof(tree));
n=read();
m=read();
//cout<<n<<' '<<m<<endl;
for(int i=1;i<=n;++i){
c=read();
x=y=i;
build(1,n,1,c);
}
for(int i=1;i<=m;++i){
q=read();
ax=read();
ay=read();
if(q==1){
x=ax;
y=ay;
c=read();
updatax(1,n,1,c);
}
else if(q==2){
x=ax;
y=ay;
c=read();
updataadd(1,n,1,c);
}
else{
x=ax;
y=ay;
cout<<findit(1,n,1)%mo<<endl;
}
}
//cout<<"Runtime:"<<double(1.0*clock()/1000.0)<<"S!"<<endl;
return 0;
}