「BJOI 2018」链上二次求和

Problem

Description

给定一个长度为 n 的数组 val ,要求支持两种操作共 q 次:

  1. 给定 u,v,d ,将所有满足 i\in\left[\min(u, v),\max(u, v)\right] val_{i} 都加上 d
  2. 给定 l,r ,求

\sum_{s=l}^{r}\sum_{i=1}^{n}\min\left(i,n-i+1,s\right)val_{i}

Constraints

记操作 1 的次数为 q'

1\le n\le 2\times 10^{5},1\le q\le 5\times 10^{5},0\le q'\le 10^{5},0\le val_{i},d\le 10^{9}+7,1\le u,v\le n,1\le l\le r\le n

Solution

Analysis

一道"做法写在题目上"的好题。

对求和的式子进行化简。

c_{i}=\min\left(i,n-i+1\right)

\sum_{s=l}^{r}\sum_{i=1}^{n}\min\left(i,n-i+1,s\right)val_{i}=\sum_{i=1}^{n}\left(\sum_{s=l}^{r}\min\left(c_{i},s\right)\right)val_{i}

考虑对 val_{i} 的系数进行化简。

\begin{aligned} \sum_{s=l}^{r}\min\left(c_{i},s\right) &=\sum_{s=l}^{c_{i}}s+\sum_{s=c_{i}+1}^{r}c_{i} \\ &=\frac{\left(l+c_{i}\right)\left(c_{i}-l+1\right)}{2}+\left(r-c_{i}\right)c_{i} \\ &=\frac{-c_{i}^{2}+c_{i}}{2}-\left(\frac{l^{2}-l}{2}+rc_{i}\right) \end{aligned}

\begin{aligned} \sum_{i=1}^{n}\left(\sum_{s=l}^{r}\min\left(c_{i},s\right)\right)val_{i} &=\sum_{i=1}^{n}\frac{-c_{i}^{2}+c_{i}}{2}val_{i}-\sum_{i=1}^{n}\frac{l^{2}- l}{2}val_{i}-\sum_{i=1}^{n}rc_{i}val_{i} \\ &=\sum_{i=1}^{n}\frac{-c_{i}^{2}+c_{i}}{2}val_{i}-\frac{l^{2}- l}{2}\sum_{i=1}^{n}val_{i}-r\sum_{i=1}^{n}c_{i}val_{i} \end{aligned}

考虑其中与询问参数 l,r 无关的部分即

\sum\frac{-c_{i}^{2}+c_{i}}{2}val_{i},\sum val_{i},\sum c_{i}val_{i}

这部分信息显然可以线段树维护,但是这样写起来极其麻烦并且细节很多,考虑简化。

易知 \left\{c_{n}\right\} 是对称的:

c_{n-i+1}=\min\left(n-i+1,n-\left(n-i+1\right)+1\right)=\min\left(n-i+1,i\right)=c_{i}

那么可以把序列 \left\{val_{n}\right\} 对半折叠,则此时每个元素的 c_{i} 即为其下标。
可以发现这样对计算没有任何影响。
设最大的 c_{i} 亦即折叠后序列的长度为 m (即 Half-n ),则

m=\frac{n+1}{2}

修改时:

  • [l, r] 全部位于 m 的左边即 r\le m ,则直接 update\left(l,r\right)
  • [l, r] 跨越了 m m\in\left(l,r\right) ,则拆成 \left[l,m\right] \left[n-R+1,n-m\right] 两段 update
  • [l, r] 全部位于 m 的右边 即 m\le l ,则直接 update\left(n-r+1,n-l+1\right)

查询时将询问 [l, r] 差分为 [1, r] \left[1,l-1\right] ,其余同修改。
实现时注意 c_{i}<l r<c_{i} 的情况。

时间复杂度 O(n \log{n})

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#include<cstdio>

using i64=long long;
constexpr int p=1000000007;
constexpr int maxn=200001;

template<typename _Tp>
inline void swap(_Tp&x,_Tp&y)
{_Tp z=x;x=y;y=z;}
/*
template<typename x_tp,typename y_tp>
inline void inc(x_tp&x,const y_tp&y)
{(x>=p-y)?(x+=y-p):(x+=y);}
*/
template<typename x_tp,typename y_tp>
inline void dec(x_tp&x,const y_tp&y)
{x-=y;(x<0)&&(x+=p);}
/*
template<typename x_tp,typename y_tp>
inline x_tp pls(const x_tp&x,const y_tp&y)
{return(x>=p-y)?(x-p+y):(x+y);}
*/
template<typename x_tp,typename y_tp>
inline x_tp Minus(const x_tp&x,const y_tp&y)
{return(x<y)?(x-y+p):(x-y);}

template<typename x_tp,typename y_tp>
inline void inc(x_tp&x,const y_tp&y)
{x=((i64)x+y)%p;}
template<typename x_tp,typename y_tp>
inline x_tp pls(const x_tp&x,const y_tp&y)
{return(i64)(x+y)%p;}

struct IO{
#define ISIZE 16384
#define OSIZE 65536

char IBUF[ISIZE],*IS,*IT;
char OBUF[OSIZE+128],*OS,*OT;

IO():IS(IBUF),IT(IBUF),OS(OBUF),OT(OBUF+OSIZE){}
~IO(){Flush();}

inline char gc(){return(IS==IT)&&(IT=(IS=IBUF)+fread(IBUF,1,ISIZE,stdin),IS==IT)?EOF:*IS++;}
template<typename _Tp>
inline IO&operator>>(_Tp&x){
_Tp s=0;char c;
if(IS+10<IT){
do c=*IS++;while(c<48||c>57);
do s=s*10+c-48,c=*IS++;while(c>47&&c<58);
}else{
do c=gc();while(c<48||c>57);
do s=s*10+c-48,c=gc();while(c>47&&c<58);
}return(x=s,*this);
}

inline void Flush(){fwrite(OBUF,1,OS-OBUF,stdout);OS=OBUF;}
inline void pc(const char&c){if(OS>OT)Flush();*OS++=c;}
inline IO&operator<<(const char&c){return(pc(c),*this);}
template<typename _Tp>
inline IO&operator<<(_Tp x){
if(OS>OT)Flush();
static char OStack[30];static int Top;Top=0;
do OStack[++Top]=x%10+48;while(x/=10);
while(Top)*OS++=OStack[Top--];
return*this;
}

#undef ISIZE
#undef OSIZE
}io;

int v[Maxn];
int UL,UR,d;
int Qpos;
i64 _x,_y,_z;

struct Node{
Node *ls,*rs;
int w0,w1,w2;
int s0,s1,s2;
int tag;
Node():ls(nullptr),rs(nullptr),w0(0),w1(0),w2(0),s0(0),s1(0),s2(0),tag(0){}

static inline Node*newnode(){
static Node Mempool[Maxn<<1],*Alloc=Mempool-1;
return++Alloc;
}

inline void update(){
s0=pls(ls->s0,rs->s0);
s1=pls(ls->s1,rs->s1);
s2=pls(ls->s2,rs->s2);
}

inline void updit(const int&d){
inc(s0,1LL*d*w0%p);
inc(s1,1LL*d*w1%p);
inc(s2,1LL*d*w2%p);
inc(tag,d);
}

inline void push_down(){
if(tag){
ls->updit(tag);
rs->updit(tag);
tag=0;
}
}

void setup(const int&L,const int&R){
if(L==R){
w0=(((i64)L*(1-L))>>1)%p;
w1=L;w2=1;
s0=(i64)v[L]*w0%p;
s1=(i64)v[L]*L%p;
s2=v[L];
}else{
int Mid=(L+R)>>1;
ls=newnode();ls->setup(L,Mid);
rs=newnode();rs->setup(Mid+1,R);
w0=pls(ls->w0,rs->w0);
w1=pls(ls->w1,rs->w1);
w2=ls->w2+rs->w2;
update();
}
}

void update(const int&L,const int&R){
if(UL<=L&&R<=UR)
return updit(d);
push_down();
int Mid=(L+R)>>1;
if(UL<=Mid)
ls->update(L,Mid);
if(Mid<UR)
rs->update(Mid+1,R);
update();
}

void Query(const int&L,const int&R){
if(R<=Qpos)
return(void)(_x+=s0,_y+=s1);
if(Qpos<=L)
return(void)(_z+=s2);
push_down();
int Mid=(L+R)>>1;
ls->Query(L,Mid);
rs->Query(Mid+1,R);
}
};
Node*root=Node::newnode();

int m;

inline void update(const int&L,const int&R){
UL=L;UR=R;
root->update(1,m);
}

inline i64 Query(const int&pos){
Qpos=pos;_x=_y=_z=0;
root->Query(1,m);
return _x+_y*pos+((i64)pos*(pos+1)>>1)%p*(_z%p);
}

inline i64 Query(const int&L,const int&R)
{return((Query(R)-Query(L-1))%p+p)%p;}

int main(){
int n,q;
io>>n>>q;
m=(n+1)>>1;
for(int i=1;i<=m;++i)
io>>v[i];
for(int i=n-m,x;i;--i)
io>>x,inc(v[i],x);
root->setup(1,m);

for(;q;--q){
int opt,L,R;io>>opt>>L>>R;
if(opt==1){
io>>d;
if(L>R)swap(L,R);
if(R<=m)update(L,R);
else if(m<L)update(n-R+1,n-L+1);
else update(L,m),update(n-R+1,n-m);
}else{
if(R<=m)io<<Query(L,R)<<'\n';
else if(m<L)io<<Query(n-R+1,n-L+1)<<'\n';
else io<<pls(Query(L,m),Query(n-R+1,n-m))<<'\n';
}
}

return 0;
}