DDOSvoid's Blog

Luogu P2801 教主的魔法

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

题目描述

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

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，每次操作对 $[l,r]$ 内的 $a_i$ 区间加，或者查询区间 $[l,r]$ 有多少 $a_i$ 大于等于给定数字 $v$​

$n\le 10^6,m\le 3000$

Solution

首先我们注意到数值不能离散化，能够想到可以用到排序加二分的方法找到大于等于c的数

其次我们发现询问的次数极其少，考虑分块处理

每个块内直接排序

对于修改，整块直接打标记记录，因为整块加不影响内部顺序

边角直接修改原数组，然后整个块重新排序，复杂度为$O(\sqrt nlog\sqrt n)$​

对于查询，整块直接二分，边角暴力即可，复杂度为$O(\sqrt nlog\sqrt n)$​

总时间复杂度为$O(m\sqrt nlog\sqrt 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
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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#define maxn 1000010
#define maxm 1010
#define gc getchar
using namespace std;

int read() {
    int x = 0; char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return x;
}

int n, m, a[maxn];

int blo, num, l[maxm], r[maxm], bl[maxn], d[maxn], add[maxm];
void init_blo() {
    blo = sqrt(n); num = n / blo; if (n % blo) ++num;
    for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1, d[i] = a[i];
    for (int i = 1; i <= num; ++i) {
        l[i] = (i - 1) * blo + 1;
        r[i] = i * blo;
    } r[num] = n;
    for (int i = 1; i <= num; ++i) sort(d + l[i], d + r[i] + 1);
}

void update(int L, int R, int v) {
    if (bl[L] == bl[R]) {
        int Bl = bl[L];
        for (int i = L; i <= R; ++i)
            a[i] += v;
        for (int i = l[Bl]; i <= r[Bl]; ++i) d[i] = a[i];
        sort(d + l[Bl], d + r[Bl] + 1); return ;
    }
    
    for (int i = bl[L] + 1; i < bl[R]; ++i) add[i] += v;
    
    for (int i = L; i <= r[bl[L]]; ++i) a[i] += v;
    for (int i = l[bl[L]]; i <= r[bl[L]]; ++i) d[i] = a[i];
    sort(d + l[bl[L]], d + r[bl[L]] + 1);
    for (int i = l[bl[R]]; i <= R; ++i) a[i] += v;
    for (int i = l[bl[R]]; i <= r[bl[R]]; ++i) d[i] = a[i];
    sort(d + l[bl[R]], d + r[bl[R]] + 1);
}

int query(int L, int R, int v) {
    int ans = 0; 
    if (bl[L] == bl[R]) {
        for (int i = L; i <= R; ++i) ans += a[i] >= v - add[bl[L]];
        return ans;
    }
    
    for (int i = bl[L] + 1; i < bl[R]; ++i)
        if (d[r[i]] >= v - add[i]) ans += r[i] - (lower_bound(d + l[i], d + r[i] + 1, v - add[i]) - d) + 1;
    
    for (int i = L; i <= r[bl[L]]; ++i) ans += a[i] >= v - add[bl[L]];
    for (int i = l[bl[R]]; i <= R; ++i) ans += a[i] >= v - add[bl[R]];
    return ans;
}

inline void solve_1() {
    int l = read(), r = read(), v = read();
    update(l, r, v);
}

inline void solve_2() {
    int l = read(), r = read(), v = read();
    printf("%d\n", query(l, r, v));
}

int main() {
    n = read(); m = read(); 
    for (int i = 1; i <= n; ++i) a[i] = read();
    init_blo();
    for (int i = 1; i <= m; ++i) {
        char ch[5]; scanf("%s", &ch);
        switch (ch[0]) {
        case 'M' : solve_1(); break;
        case 'A' : solve_2(); break;
        }
    }
    return 0;
}