水题笔记_ [Hnoi2016]序列 [莫队, 清奇脑回路, 前缀和, 翻车, LL]

前缀和有很好的性质

但是…

long long! long long! long long!

天呐…我好像写了整整10天…其实主要是被期中考试×了

然后我期中考试还是炸了 数学73你敢信?

懵逼的 题目

LL

扯淡的 题解

day1的题感觉大部分的参赛选手都能想到算法啊..根本没有什么技术含量啊

——某联赛的毒瘤出题人

不过这题的思维难度确实没有NOIpD1T1大www

真 没什么用的思路

Part1
Part2
Part3
Part4
Part5

到底 为什么$fr[]$没有可减性

qwq

就上面这幅图说一下…

如果我要添加浅蓝色的这一小段

于是我加上了lefr[ri], 减去了lefr[le - 1]

然后我发现, 在$[le, ri]$之间, 最小值a[wz]所占的横杆(橘色)超过了le, 一直到了leqwq[wz] + 1才结束, 以$1$为左端点的子集们的最小值才不是a[wz](黑色的横杆)

这样一来, 其实我们减去的lefr[le - 1](粉色), 和我们应该减去的a[wz] * (le - 1 - leqwq[wz]) + lefr[leqwq[wz]], 就不一样了…所以是错的

假 没什么用的实现方法

  • 我需要一个数组lefr[MAXN]: lefr[i]存储的是$1 \to i$中所有以$i$为右端点的子集的最小值的和
    • 我需要一个数组leqwq[MAXN]: leqwq[i]存储了: 在$i$的左边, 比a[i]小的数中最靠右的(也就是最接近$i$的), 数的位置(注意: a[leqwq[x]] < a[x], 注意区间元素个数, 且如果没有找到比当前数小的数, leqwq[i] = 0)
      • 我需要一个单调栈(要手写, 在init()函数中修改, 查询):
        • 开两个栈first[], second[]: first代表数值, second代表位置
        • 从头到尾加数, 传入两个参数(大小, 位置), 并进行如下操作:
          • 查询: 二分一个比当前数小的数, 并返回这个数的位置即可
          • 修改: 如果新进的数比栈顶小(或等于), 弹栈(两个栈一同弹出); 直到新进的数比栈顶大为止(也就是这个栈是从下至上单调递增的)
    • 这样就可以预处理lefr[]了(这个预处理和莫队的add()基本上是一模一样的):
      • lefr[i] = a[i] * (i - leqwq[i]) + lefr[leqwq[i]]
  • 我需要一个数组rifr[MAXN]: rifr[i]存储的是$i \to n$中所有以$i$为左端点的子集的最小值的和
    • 我需要一个数组riqwq[MAXN]: riqwq[i]存储了: 在$i$的右边, 比a[i]小的数中最靠右的(也就是最接近$i$的), 数的位置(注意: 如果没有找到比当前数小的数, riqwq[i] = n + 1)
      • 单调栈同上即可(写一个结构体就行), 但加数要反着来
    • 这样我们就可以预处理rifr[]了:
      • rifr[i] = a[i] * (riqwq[i] - i) + rifr[riqwq[i]]
  • 我需要一个solve()函数来进行莫队操作(注意: 不可以再使用诸如add(ri++)等写法了…因为在add(int)中, 全局变量ri已经改变了)
  • 我需要一个函数cx(int le, int ri)返回$[le, ri]$中的最小值的位置
    • ST表乱搞就好啦
    • 我需要一个函数LL lecal(): 他能够计算在前缀和运算中在左边应该减去多少
    • wz为当前区间内的最小值的位置, xleqwq[wz]
      • return a[wz] * (le - 1 - x) + lefr[x];
  • 我需要一个函数LL rical(): 他能够计算在前缀和运算中在右边应该减去多少
    • wz为当前区间内的最小值的位置, xriqwq[wz]
      • return a[wz] * (x - ri - 1) + rifr[x];
  • 我需要一个函数leadd(int x): 向当前的区间内加入一个数a[x](--le)
    • 如果riqwq[x] > ri也就是因当前添加的数而增加的所有子集的最小值都为a[x]: 那么直接ans += a[x] * (ri - le + 1)即可
    • 否则, 有一部分的区间的最小值并非a[x]:
      • ans += rifr[ri];
      • ans -= rical();
  • 我需要一个函数riadd(int x): 向当前的区间内的右边加入一个数a[x](++ri)
    • 如果leqwq[x] < le也就是因当前添加的数而增加的所有子集的最小值都为a[x]: 那么直接ans += a[x] * (ri - le + 1)即可
    • 否则, 有一部分的区间的最小值并非a[x]:
      • ans += lefr[x];
      • ans -= lecal();
  • 我需要一个函数ledel(int x): 从当前的区间内的左边删除一个数a[x](le++)
    • 删除嘛…就是增加的反操作啊…
    • 如果riqwq[x] > ri: ans -= (ri - le + 1) * a[x]
    • 否则:
      • ans -= riqwq[x];
      • ans += rical();
  • 我需要一个函数ridel(int x): 从当前的区间内的右边删除一个数a[x](ri--)
    • 如果leqwq[x] < le: ans -= (ri - le + 1) * a[x]
    • 否则:
      • ans -= leqwq[x];
      • ans += lecal();

Maya…我怎么感觉…这个题比tree难搞多~~~了…

真 简单明了的 代码

跳过的 坑

  • ST表: le + (t << 1) - 1 <= n 以及 le + (1 << t) <= n…直接给我$RE$成零分了…
  • 没有把a[]开成LL, 这样在预处理进行乘法的时候就已经炸了…
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
/**************************************************************
Problem: 4540
User: Cansult
Language: C++
Result: Accepted
Time:9876 ms
Memory:18424 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <cmath>
#define MAXN (100000 + 5)
#define INF (0x7fffffff)
#define MAXL (20 + 5)
#define pii pair<int, int>
#define LL long long
using namespace std;
struct question
{
int le, ri, bh;
}que[MAXN];
struct dds
{
int first[MAXN], second[MAXN], re0;
dds(int x): re0(x) { first[0] = second[0] = 1, first[1] = -INF, second[1] = x; }
int cx(int dqfr, int dqsec)
{
if (!first[0])
{
first[++first[0]] = dqfr, second[++second[0]] = dqsec;
return re0;
}
int re = upper_bound(first + 1, first + first[0] + 1, dqfr) - first - 1;
if (!re) re = re0;
else re = second[re];
while (first[0] && first[first[0]] >= dqfr)
--first[0], --second[0];
first[++first[0]] = dqfr, second[++second[0]] = dqsec;
return re;
}
};
struct ST
{
int f[MAXN][MAXL], n, lgn;
LL a[MAXN];
int lg(int x)
{
int re = 0;
while ((1 << re) < x)
++re;
return re;
}
void init(int xn, LL *xa)
{
memset(a, 0x8f, sizeof(a));
n = xn, lgn = lg(n);
for (int i = 1; i <= n; i++)
f[i][0] = i, a[i] = xa[i];
for (int t = 1; t <= lgn; t++)
for (int i = 1; i <= n; i++)
if (i + (1 << t) - 1 <= n)
{
if (a[f[i][t - 1]] < a[f[i + (1 << (t - 1))][t - 1]])
f[i][t] = f[i][t - 1];
else
f[i][t] = f[i + (1 << (t - 1))][t - 1];
}
}
int cx(int le, int ri)
{
int lglr = lg(ri - le + 1), lex = f[le][lglr - 1], rix = f[ri - (1 << (lglr - 1)) + 1][lglr - 1];
if (a[lex] < a[rix])
return lex;
else
return rix;
}
};
ST QAQ;
int n, q, leqwq[MAXN], riqwq[MAXN], le, ri, block;
LL lefr[MAXN], rifr[MAXN], ans, outans[MAXN], a[MAXN];
void init()
{
dds led(0), rid(n + 1);
QAQ.init(n, a);
// leqwq && riqwq:
for (int i = 1; i <= n; i++)
leqwq[i] = led.cx(a[i], i);
for (int i = n; i >= 1; i--)
riqwq[i] = rid.cx(a[i], i);
// lefr && rifr:
for (int i = 1; i <= n; i++)
lefr[i] = a[i] * (i - leqwq[i]) + lefr[leqwq[i]];
for (int i = n; i >= 1; i--)
rifr[i] = a[i] * (riqwq[i] - i) + rifr[riqwq[i]];
}
/*inline LL lecal(int x)
{
LL re = a[x] * (x - leqwq[x] - 1) + lefr[leqwq[x]];
return re;
}
inline LL rical(int x)
{
LL re = a[x] * (riqwq[x] - x - 1) + rifr[riqwq[x]];
return re;
}*/
inline LL lecal()
{
int wz = QAQ.cx(le, ri), x = leqwq[wz];
LL re = a[wz] * (le - 1 - x) + lefr[x];
return re;
}
inline LL rical()
{
int wz = QAQ.cx(le, ri), x = riqwq[wz];
LL re = a[wz] * (x - ri - 1) + rifr[x];
return re;
}
void leadd(int x)
{
if (riqwq[x] > ri)
ans += a[x] * (ri - le + 1);
else
{
ans += rifr[x];
ans -= rical();
}
}
void riadd(int x)
{
if (leqwq[x] < le)
ans += a[x] * (ri - le + 1);
else
{
ans += lefr[x];
ans -= lecal();
}
}
void ledel(int x)
{
if (riqwq[x] > ri)
ans -= a[x] * (ri - le + 1);
else
{
ans -= rifr[x];
ans += rical();
}
}
void ridel(int x)
{
if (leqwq[x] < le)
ans -= a[x] * (ri - le + 1);
else
{
ans -= lefr[x];
ans += lecal();
}
}
bool cmp(const question x, const question y)
{
if (x.le / block == y.le / block)
return x.ri < y.ri;
else
return x.le < y.le;
}
void solve()
{
sort(que + 1, que + q + 1, cmp);
ri = le = que[1].le;
for (int i = le; i <= que[1].ri; i++)
riadd(ri), ++ri;
--ri;
outans[que[1].bh] = ans;
for (int i = 2; i <= q; i++)
{
while (le < que[i].le)
ledel(le), ++le;
while (le > que[i].le)
leadd(--le);
if (le > ri)
ri = le - 1, ans = 0;
while (ri < que[i].ri)
riadd(++ri);
while (ri > que[i].ri)
ridel(ri), --ri;
outans[que[i].bh] = ans;
}
}
int main()
{
scanf("%d%d", &n, &q);
block = sqrt(n) + 1;
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (int i = 1; i <= q; i++)
scanf("%d%d", &que[i].le, &que[i].ri), que[i].bh = i;
init();
/*for (int i = 1; i <= n; i++)
printf("%d ", leqwq[i]);
puts("");
for (int i = 1; i <= n; i++)
printf("%d ", riqwq[i]);
puts("\n---------------");
for (int i = 1; i <= n; i++)
printf("%d ", lefr[i]);
puts("");
for (int i = 1; i <= n; i++)
printf("%d ", rifr[i]);
puts("");*/
solve();
for (int i = 1; i <= q; i++)
printf("%lld\n", outans[i]);
return 0;
}

/*
5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5
*/

听说还有线段树做法?

被吓尿了 改天去参拜一下

By … Cansult