洛谷 5309 「Ynoi 2011」初始化

发表于 | 分类于 |

开始看 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)));
}