题面#

题目描述#

给定一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，询问区间内小于某个值 $x$ 的前驱（比其小的最大元素）。

输入格式#

第一行输入一个数字 $n$ 。

第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$ ，以空格隔开。

接下来输入 $n$ 行询问，每行输入四个数字 $\rm{opt}、l、r、c$ ，以空格隔开。

若 $\rm opt=0$ ，表示将位于 $\left[l, r\right]$ 的之间的数字都加 $c$ 。

若 $\rm opt=1$ ，表示询问 $\left[l, r\right]$ 中 $c$ 的前驱的值（不存在则输出 $\rm -1$ ）。

输出格式#

对于每次询问，输出一行一个数字表示答案。

样例（很水）#

Input

Output

数据范围与提示#

对于 $100\%$ 的数据， $1\leq n\leq 100000,-2^{31}\leq {\rm others}$ 、 ${\rm ans}\leq 2^{31}-1$ 。

对题目的吐槽#

这个样例是真的水，从样例中根本找不出自己程序任何错误。。。。

我一开始程序内层循环用的是i变量，样例居然给我过了？！

思路#

审题#

这道题他说要求前驱的值。要求前驱的值如果直接暴力查找的话肯定会T飞，所以需要用到分块来优化。

解法#

加c的核心代码如下：

1
for (int j = x; j <= r[b[x]]; j++) a[j] += k;         //左边不完整块暴力相加
2
for (int j = l[b[x]]; j <= r[b[x]]; j++) d[j] = a[j]; //将a[]数组复制一份给d[]数组，以此来达到将数组排序而不破坏原数组顺序
3
sort(d + l[b[x]], d + r[b[x]] + 1);                   //将d[]数组排序
4
for (int j = l[b[y]]; j <= y; j++) a[j] += k;         //右边不完整块暴力相加
5
for (int j = l[b[y]]; j <= r[b[y]]; j++) d[j] = a[j]; //将a[]数组复制一份给d[]数组，以此来达到将数组排序而不破坏原数组顺序
6
sort(d + l[b[y]], d + r[b[y]] + 1);                    //将d[]数组排序
7
for (int j = b[x] + 1; j <= b[y] - 1; j++)  lazy[j] += k; //用lazyp[]数组对中间完整块做标记，减少运算量

查询的核心代码如下：

1
for (int j = x; j <= r[b[x]]; j++) //暴力查询左边不完整块
2
  if ((lazy[b[x]] + a[j] < k) && (lazy[b[x]] + a[j] > maxx)/*需要保证这个比k小并且比maxx大*/)
3
    maxx = lazy[b[x]] + a[j];
4
for (int j = l[b[y]]; j <= y; j++) //暴力查询右边不完整块
5
  if ((lazy[b[y]] + a[j] < k) && (lazy[b[y]] + a[j] > maxx))
6
    maxx = lazy[b[y]] + a[j];
7
for (int j = b[x] + 1; j <= b[y] - 1; j++) {
8
  if (k - lazy[j] <= d[(j - 1) * block + 1]) continue;
9
  int num = lower_bound(d + l[j], d + r[j] + 1, k - lazy[j]) - d - 1;
10
  //lower_bound函数返回的是大于或等于k - lazy[j]的第一个数的地址（指针），减去d可得数组下标，再减一即可得到前驱
11
  maxx = maxx > (d[num] + lazy[j]) ? maxx : (d[num] + lazy[j]);
12
}
13
if (maxx == -1) write(-1); //如果maxx没变（即没找到），则输出-1
14
else write(maxx); //否则输出maxx（前驱）

代码#

这次的代码是LibreOJ格式化过的，总觉得有亿点奇怪

1
#include <iostream>
2
#include <algorithm> //sort()要用
3
#include <cstdio>
4
#include <cmath> //sqrt()y要用
5
#define int long long
6
using namespace std;
7

8
int a[1000005], d[1000005], l[1005], r[1005], b[1000005], lazy[1005];
9
int n, q, block, tot, x, y, k;
10
int c;
11

12
inline int read() { //快读
13
    int X = 0;
14
    bool flag = 1;
15
    char ch = getchar();
16

17
    while (ch < '0' || ch > '9') {
18
        if (ch == '-')
19
            flag = 0;
20

21
        ch = getchar();
22
    }
23

24
    while (ch >= '0' && ch <= '9') {
25
        X = (X << 1) + (X << 3) + ch - '0';
26
        ch = getchar();
27
    }
28

29
    if (flag)
30
        return X;
31

32
    return ~(X - 1);
33
}
34

35
inline void write(int X) { //快写
36
    if (X < 0) {
37
        putchar('-');
38
        X = ~(X - 1);
39
    }
40

41
    int s[50], top = 0;
42

43
    while (X) {
44
        s[++top] = X % 10;
45
        X /= 10;
46
    }
47

48
    if (!top)
49
        s[++top] = 0;
50

51
    while (top)
52
        putchar(s[top--] + '0');
53

54
    putchar('\n');
55
    return;
56
}
57

58

59
signed main() {
60
    n = read();
61

62
    for (int i = 1; i <= n; i++)
63
        a[i] = read();
64

65
    block = sqrt(n), tot = n / block;
66

67
    if (n % block)
68
        tot++; //如果数的个数不是块长的倍数的话，还要再增加一个块的个数
69

70
    for (int i = 1; i <= n; i++)
71
        b[i] = (i - 1) / block + 1, d[i] = a[i];
72

73
    for (int i = 1; i <= tot; i++)
74
        l[i] = (i - 1) * block + 1, r[i] = i * block;
75

76
    r[tot] = n;
77

78
    for (int i = 1; i <= tot; i++)
79
        sort(d + l[i], d + r[i] + 1);
80

81
    for (int i = 1; i <= n; i++) {
82
        c = read();
83
        x = read();
84
        y = read();
85
        k = read();
86

87
        if (c == 0) {
88
            if (b[x] == b[y]) { //如果x和y在同一个块内，就直接只能暴力相加
89
                for (int j = x; j <= y; j++)
90
                    a[j] += k;
91

92
                for (int j = l[b[x]]; j <= r[b[x]]; j++)
93
                    d[j] = a[j];
94

95
                sort(d + l[b[x]], d + r[b[x]] + 1);
96
            } else {
97
                for (int j = x; j <= r[b[x]]; j++) //左边不完整块暴力相加
98
                    a[j] += k;
99

100
                for (int j = l[b[x]]; j <= r[b[x]]; j++) //将a[]数组复制一份给d[]数组，以此来达到将数组排序而不破坏原数组顺序
101
                    d[j] = a[j];
102

103
                sort(d + l[b[x]], d + r[b[x]] + 1); //将d[]数组排序
104

105
                for (int j = l[b[y]]; j <= y; j++) //右边不完整块暴力相加
106
                    a[j] += k;
107

108
                for (int j = l[b[y]]; j <= r[b[y]]; j++) //将a[]数组复制一份给d[]数组，以此来达到将数组排序而不破坏原数组顺序
109
                    d[j] = a[j];
110

111
                sort(d + l[b[y]], d + r[b[y]] + 1); //将d[]数组排序
112

113
                for (int j = b[x] + 1; j <= b[y] - 1; j++) //用lazyp[]数组对中间完整块做标记，减少运算量
114
                    lazy[j] += k;
115
            }
116
        }
117

118
        if (c == 1) {
119
            int maxx = -1;
120

121
            if (b[x] == b[y]) { //如果x和y在同一个块内，就直接只能暴力求解
122
                for (int j = x; j <= y; j++)
123
                    if ((lazy[b[x]] + a[j] < k) && (lazy[b[x]] + a[j] > maxx))
124
                        maxx = lazy[b[x]] + a[j];
125

126
                if (maxx == -1)
127
                    write(-1);
128
                else
129
                    write(maxx);
130
                continue;
131
            } else {
132
                for (int j = x; j <= r[b[x]]; j++) //暴力查询左边不完整块
133
                    if ((lazy[b[x]] + a[j] < k) && (lazy[b[x]] + a[j] > maxx))
134
                        maxx = lazy[b[x]] + a[j];
135
                for (int j = l[b[y]]; j <= y; j++) //暴力查询右边不完整块
136
                    if ((lazy[b[y]] + a[j] < k) && (lazy[b[y]] + a[j] > maxx))
137
                        maxx = lazy[b[y]] + a[j];
138
                for (int j = b[x] + 1; j <= b[y] - 1; j++) {
139
                    if (k - lazy[j] <= d[(j - 1) * block + 1])
140
                        continue;
141
                    int num = lower_bound(d + l[j], d + r[j] + 1, k - lazy[j]) - d - 1;
142
                    //lower_bound函数返回的是大于或等于k - lazy[j]的第一个数的地址（指针），减去d可得数组下标，再减一即可得到前驱
143
                    maxx = (maxx > (d[num] + lazy[j])) ? maxx : (d[num] + lazy[j]);
144
                }
145
                if (maxx == -1) //如果maxx没变（即没找到），则输出-1
146
                    write(-1);
147
                else
148
                    write(maxx); //否则输出maxx（前驱）
149
            }
150
        }
151
    }
152

153
    return 0;
154
}