数列分块

区间加法，区间内小于x的个数

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define int long long
using namespace std;
int n;
const int N = 1e5 + 7;
int add[N], a[N], pos[N], L[N], R[N], b[N];
vector<int > arr[N];
void reset(int x) {
    arr[x].clear();

    for (int i = L[x]; i <= R[x]; i ++)
        arr[x].push_back(a[i]);

    sort(arr[x].begin(), arr[x].end());
}
void change(int l, int r, int d) {
    int p = pos[l], q = pos[r];

    if (p == q) {
        for (int i = l; i <= r; i ++)
            a[i] += d;

        reset(q);
    } else {
        for (int i = p + 1; i <= q - 1; i ++)
            add[i] += d;

        for (int i = l; i <= R[p]; i ++)
            a[i] += d;

        reset(p);

        for (int i = L[q]; i <= r; i ++)
            a[i] += d;

        reset(q);
    }
}
int ask(int l, int r, int d) {
    int ans = 0;
    int p = pos[l], q = pos[r];

    if (p == q) {
        for (int i = l; i <= r; i ++)
            if (a[i] + add[p] < d)
                ans++;
    } else {
        for (int i = l; i <= R[p]; i ++)
            if (a[i] + add[p] < d)
                ans++;

        for (int i = L[q]; i <= r; i ++)
            if (a[i] + add[q] < d)
                ans++;

        for (int i = p + 1; i <= q - 1; i ++) {
            int po = lower_bound(arr[i].begin(), arr[i].end(), d - add[i]) - arr[i].begin();
            ans += po ;
        }
    }

    return ans;
}

signed main() {
    cin >> n;

    for (int i = 1; i <= n; i ++)
        scanf("%lld", &a[i]);

    int t = sqrt(n);
    memcpy(b, a, sizeof a);

    for (int i  = 1; i <= t; i ++) {
        L[i] = (i - 1) * t + 1;
        R[i] = i * t;
        // cout << L[i] << ' ' <<R[i] << endl;
    }

    if (R[t] < n)
        t++, L[t] = R[t - 1] + 1, R[t] = n;

    //for (int i = 1; i <= t; i ++ ) sort(b+L[i],b+R[i]+1);
    for (int i = 1; i <= t; i ++) {
        for (int j = L[i]; j <= R[i]; j ++)
            arr[i].push_back(a[j]);

        sort(arr[i].begin(), arr[i].end());
    }

    for (int i = 1; i <= t; i ++)
        for (int j = L[i]; j <= R[i]; j ++) {
            pos[j] = i;
        }

    //for (int i = 1; i <= n; i ++ ) cout << b[i] << endl;
    // for (int i = 1; i <= n ; i++ ) cout <<pos[i] << ' ';puts("");
    //for (int i =1; i <= t; i ++ ) cout << L[i] << ' ' << R[i] << endl;
    for (int i = 1; i <= n; i ++) {
        int op, l, r, d;
        scanf("%lld%lld%lld%lld", &op, &l, &r, &d);

        if (op == 0) {
            change(l, r, d);
        } else {
            printf("%lld\n", ask(l, r, d * d));
        }
    }
}

区间加法，查找x的前驱

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#define int long long
using namespace std;

const int N = 2e5 + 8;

int n,m;

int a[N],pos[N],L[N],R[N],add[N];
set<int> arr[N];

void reset(int x) {
    arr[x].clear();
    for (int i = L[x]; i<= R[x]; i ++ )
        arr[x].insert(a[i]);
}

void change(int l,int r,int d) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r ; i ++ )
            a[i] += d;
        reset(p);
    } else {
        for (int i = l; i <= R[p]; i ++ ) a[i] += d;reset(p);
        for  (int i = L[q]; i <= r; i++ ) a[i] += d;reset(q);
        for (int i = p + 1; i <= q - 1; i ++ ) add[i] += d;
    }
}

int ask(int l,int r,int d) {
    int ans = -((1ll<<31)+1);
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i ++ )
            if (a[i] + add[p] < d) ans = max(ans,a[i] + add[p]);
    }else {
        for (int i = l; i<= R[p]; i ++ ) 
            if (a[i] + add[p] < d) ans = max(ans, a[i] + add[p]);
        for (int i = L[q]; i <= r; i ++ ) 
            if(a[i] + add[q] < d) ans = max(ans, a[i] + add[q]);
        for (int i = p + 1 ; i<= q  -1; i ++ ) {
            auto po = arr[i].lower_bound(d - add[i]);
            if(po != arr[i].begin()) {
                po--;
                ans = max(ans, *(po)+ add[i]);
            }
            //cout <<*po << endl;
        }
    }
    //cout << ans << endl;
    if (ans == -((1ll<<31)+1)) ans = -1;
    //cout << ans << endl;
    return ans;
}

signed main() {
    cin >> n;
    int t = sqrt(n);
    for (int i = 1; i <= n; i++ ) scanf("%lld",a+i);
    for (int i =1 ;i <= t; i ++ ) {
        L[i] = (i - 1)*t + 1;
        R[i] = i*t;
    }
    if (R[t] < n) t++,L[t] = R[t-1] + 1,R[t] = n;
    for (int i = 1; i <= t; i ++ ) {
        for (int j = L[i]; j<= R[i]; j ++ )
            arr[i].insert(a[j]),pos[j] = i;
    }
    for (int i = 1;  i<= n; i ++ ) {
        int op,l,r,d;
        scanf("%lld%lld%lld%lld",&op,&l,&r,&d);
        if (op == 0) change(l,r,d);
        else printf("%lld\n",ask(l,r,d));
    }
}

区间开方，区间求和

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
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;

const int N =  1e5 + 7;

int a[N],L[N],R[N],pos[N],sum[N];
bool is0[N];

void sqrt_(int x) {
    if (is0[x]) return;
    is0[x] = 1;
    sum[x] = 0;
    for (int i = L[x]; i <= R[x]; i ++ ) {
        a[i] = sqrt(a[i]);
        sum[x] += a[i];
        if(a[i] > 1) is0[x] = 0;
    }
}

void change(int l,int r) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i  = l; i <= r ; i++ ) {
            sum[q] -= a[i];
            a[i] = sqrt(a[i]);
            sum[q] += a[i];
        }
    }else {
        for (int i  = l;  i<= R[p]; i ++) {
            sum[p] -= a[i];
            a[i] = sqrt(a[i]);
            sum[p] += a[i];
        }
        for (int i = L[q]; i <= r; i ++ ) {
            sum[q] -= a[i]; a[i] = sqrt(a[i]); sum[q] += a[i];
        }
        for (int i = p+ 1; i <= q - 1; i ++ ) 
            sqrt_(i);
    }
}

int ask (int l,int r) {
    int p = pos[l], q = pos[r];
    int ans = 0;
    if (p ==q) {
        for (int i = l ; i<= r ; i++ ) ans += a[i];
    }else {
        for (int i =  l; i <= R[p]; i ++ ) ans += a[i];
        for (int i = L[q]; i <= r; i ++ ) ans += a[i];
        for (int i = p + 1; i <= q - 1; i ++ ) 
            ans += sum[i];
    }
    return ans;
}

signed main() {
    int n;
    cin >> n;
    int t = sqrt(n);
    for (int i =1 ; i<= n ; i++ ) cin >> a[i];
    for (int i = 1; i <= t;  i++ ) {
        L[i] = (i-1) *t + 1;
        R[i] = i *t;
    }
    if (R[t] < n) t++, L[t] = R[t-1] + 1,R[t] = n;
    for ( int i =1 ; i <= t; i ++ ) {
        for (int j = L[i]; j <= R[i]; j ++ ) {
            pos[j] = i;
            sum[i] += a[j];
        }
    }
   // for (int i = 1; i<= t; i ++ ) cout << L[i]<< ' ' <<R[i] << endl;
    //for (int i = 1; i <= n; i ++ ) cout << pos[i] << ' ';
    for (int i = 1; i <= n; i ++ ) {
        int op, l, r, d;
        cin >> op >> l >> r >> d;
        if (op == 0) change(l,r);
        else cout << ask(l,r) << endl;
    }
    return 0;
}

单间修改，跳点查询

https://www.luogu.com.cn/problem/P3396

思路

如果暴力来做，查询为n方，修改为o1，分块使两种操作复杂度均摊o根号n

把块大小设置为根号nn

大段暴力，因为每跳一次长度为根号n，时间复杂度为n/根号n

小段预处理，O（1）查询，根号n修改

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
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
const int N = 2e5 + 8;

int a[N],L[N],R[N],pos[N];
int res[400][400];
int t,len;
int n,m;

void change(int x,int y) {
    for (int i =1; i <= t; i ++ )
        res[i][x%i] += y - a[x];
    a[x] = y;
}

int ask(int x,int y) {
    int ans = 0;
    if (x <= len) {
        ans += res[x][y];return ans;
    }
    for (int i = y; i <= n; i += x) ans += a[i];
    return ans;
}

signed main() {
    cin >> n >> m;
    for (int i  =1 ;i <= n; i ++ ) cin >> a[i];
    t = sqrt(n), len = n / t;
    for (int i = 1 ;i <= t ; i ++ ) {
        L[i] = (i-1)*len + 1;
        R[i] = i*len;
    }
    if(R[t] < n) t++,L[t] = R[t-1] + 1,R[t] = n;
    for (int i =1 ; i <= t; i ++ )
        for (int j = 1; j<= len; j ++ )
            pos[j] = i;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= t; j ++ )
            res[j][i%j] += a[i];
    for (int i  =1; i <= m ; i ++ ) {
        char op[2];
        int x,y;
        cin >> op >> x >> y;
        if(*op == 'A') {
            cout << ask(x,y) << endl;
        }else change(x,y);
    }
}