洛谷 5309.「YunoOI 2011」D1T1

开始看 Ynoi 了呢……
话说这道题其实很早之前就会了,由于当时常数太大就没过……

有个套路叫做根号分治。

对于此题,具体地说,就是设一个阈值 \(T\)
\(x \ge T\),直接暴力更改即可,用分块维护,修改复杂度是 \(O(\frac nT)\)
\(x < T\),则注意到此时应该得到一个 \(O(T)\) 的算法才能平衡复杂度;考虑把原序列按每块大小为 \(x\) 分成若干块,则每一块一定都刚好有一个位置被修改,贡献是一样的。
于是前缀和维护即可,复杂度 \(O(T)\)

其实 \(T\) 瞎取个数就行了(逃

代码:

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
#include <cstdio>
#include <cmath>
#include <algorithm>
#define add(x,y) ((x) + (y) >= mod ? (x) + (y) - mod : (x) + (y))
#define dec(x,y) ((x) < (y) ? (x) - (y) + mod : (x) - (y))
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x,1);
}

const int N = 2e5;
const int BLOCK = 119;
const int CNT = N / BLOCK + 2;
const int mod = 1e9 + 7;
int n,m,block,mn = BLOCK + 1,mx;
int a[N + 5],sum[CNT + 5],pos[N + 5],s[BLOCK + 5][BLOCK + 5];
int vis[BLOCK + 5];
int ans;
inline void update(int x,int y,int z)
{
if(x >= block)
{
for(;y <= n;y += x)
a[y] = add(a[y],z),sum[pos[y]] = add(sum[pos[y]],z);
return ;
}
vis[x] |= 1;
for(register int i = y;i <= x;++i)
s[x][i] = add(s[x][i],z);
}
inline void query(int l,int r)
{
for(register int i = l,R = min(pos[l] * block,r);i <= R;++i)
ans = add(ans,a[i]);
if(pos[l] ^ pos[r])
for(register int i = (pos[r] - 1) * block + 1;i <= r;++i)
ans = add(ans,a[i]);
for(register int i = pos[l] + 1;i < pos[r];++i)
ans = add(ans,sum[i]);
for(register int i = 1,L,R,w;i <= block && (L = (l - 1) / i + 1,R = (r - 1) / i + 1,1);++i)
(L ^ R ?
(
w = 1LL * (R - L - 1) * s[i][i] % mod,ans = add(ans,w),
ans = add(ans,s[i][i]),ans = dec(ans,s[i][l - (L - 1) * i - 1]),
ans = add(ans,s[i][r - (R - 1) * i])
)
:
(
ans = add(ans,s[i][r - (R - 1) * i]),
ans = dec(ans,s[i][l - (L - 1) * i - 1])
));
}
int main()
{
read(n),read(m),block = BLOCK;
for(register int i = 1;i <= n;++i)
read(a[i]),a[i] %= mod,pos[i] = (i - 1) / block + 1,sum[pos[i]] = add(sum[pos[i]],a[i]);
int op,x,y,z;
for(;m;--m)
read(op),read(x),read(y),
op == 1 ? (read(z),z %= mod,update(x,y,z),1) : (printf("%d\n",(ans = 0,query(x,y),ans)));
}