笔者语：
- 2023.2.28 突然想起来去写一下末日三问的题解，做这些题，包括 Ynoi 大分块系列使我受益良多，在此表示感谢。
在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的人们，人人本着正义之名。长存不灭的过去，逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。——世界上最幸福的女孩
珂朵莉，要永远幸福哦！
等这场战争结束之后
- 题意
给你一个图，每个点有点权，最开始没有边，实现以下操作：
1 x y，添加一条 \(x\) 与 \(y\) 之间的双向边。
2 x，回到第 \(x\) 次操作后的状态（注意这里的 \(x\) 可以是 \(0\)，即回到初始状态）。
3 x y，查询 \(x\) 所在联通块能到的点中点权第 \(y\) 小的值，如果不存在，那么输出 \(-1\)。
- 分析
哎呀，这个回到某个状态这么毒瘤，但是发现每个状态入读均为 \(1\)，那考虑直接把操作树建出来，那操作二就解决了！具体来讲就是对于操作二，\(x \rightarrow i\)
，对于其他操作 \(i-1 \rightarrow i\)。
回来看修改，发现是合并两个连通块，暴力合并的复杂度显是 \(\mathcal O(sz)\)，\(sz\) 为连通块大小，似乎不太行，所以我们稍微优化一下，用分块均摊，按值域离散化之后复杂度就讲到 \(\mathcal O(\sqrt n)\) 的了。具体来讲，设 \(f_{u,i}\)，表示已 \(u\) 为根的连通块中，在 \(i\) 值域块的数量。
最后一步修改，直接暴力找到在那个值域块内，再暴力枚举块内的数就行了，用上一个并查集，因为操作树上还得回溯，所以得支持撤销，复杂度 \(\mathcal O(\sqrt n\log n)\)。
于是稍微调一下块长理论复杂度 \(\mathcal O(n\sqrt{n\log n})\)。
仔细一看我的天呀，空间竟然只有 20mb，那 \(\mathcal O(n\sqrt{n\log n})\) 的空间复杂度不是当场暴毙！
仔细一看，先卡空间，直接把 \(f\) 开成 short。想了一想觉得并查集常数怎么小，稍微时间放宽一点不是不行，所以果断调大块长，发现块数大概到 \(46\) 的时候没啥问题。
- code
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
using namespace std;
namespace IO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
inline long long read () {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(long long x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using IO::read;
using IO::write;
const int maxn(1e5 + 7), B(47);
int n, m, sqn, len, head[maxn], tot, typ[maxn], a[maxn], b[maxn], ans[maxn], fa[maxn], sz[maxn];
short f[maxn][B];
struct edge {
int v, nxt;
} e[maxn];
struct Node {
int x, y;
inline bool operator < (const Node &rhs) const {
return x < rhs.x;
}
} p[maxn];
inline int find (int x) {
return fa[x] == x ? fa[x] : find(fa[x]);
}
inline void add_edge (int u, int v) {
e[++tot] = {v, head[u]};
head[u] = tot;
}
inline void dfs (int u) {
bool fl = 0;
if (typ[u] == 1) {
a[u] = find(a[u]), b[u] = find(b[u]);
int x = a[u], y = b[u];
if (x != y) {
fl = 1;
if (sz[x] > sz[y]) swap(x, y), swap(a[u], b[u]);
sz[y] += sz[x], fa[x] = y;
for (int i = 1; i <= len; i++) f[y][i] += f[x][i];
}
} else if (typ[u] == 3) {
int x = b[u], y = 0;
a[u] = find(a[u]);
if (x > sz[a[u]]) ans[u] = -1;
else {
for (int i = 1; i <= len && !y; i++)
if (x > f[a[u]][i]) x -= f[a[u]][i];
else y = i;
for (int i = (y - 1) * sqn + 1; i <= min(n, y * sqn) && x; i++)
if (find(p[i].y) == a[u])
--x, ans[u] = p[i].x;
}
}
for (int i = head[u]; i; i = e[i].nxt) dfs(e[i].v);
if (fl) {
int x = a[u], y = b[u];
for (int i = 1; i <= len; i++) f[y][i] -= f[x][i];
fa[x] = x, sz[y] -= sz[x];
}
}
int main() {
n = read(), m = read(), sqn = n / 46, len = (n - 1) / sqn + 1;
for (int i = 1; i <= n; i++) p[i] = {(int)read(), i}, fa[i] = i, sz[i] = 1;
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++) ++f[p[i].y][(i - 1) / sqn + 1];
for (int i = 1; i <= m; i++) {
typ[i] = read();
if (typ[i] == 2) {
add_edge(read(), i);
} else {
add_edge(i - 1, i);
a[i] = read(), b[i] = read();
}
}
dfs(0);
for (int i = 1; i <= m; i++) if (typ[i] == 3) write(ans[i]), puts("");
}
// I love WHQ!
我回来了
- 题意
对一个序列为一下两个操作：
1 x，向序列中加入数 \(x\)。
2 l r，随机在区间 \([l,r]\) 中选择一个数 \(d\)，不断重复一下步骤：
- 序列中所有数减 \(d\)
- 若有非正数，将所有非正数去除，重复上述操作；否则中止操作。
求操作次数的期望 \(E\)，乘 \(r-l+1\) 的值。
- 分析
靠率对于一个 \(d\) 的步数的含义，实际上就是满足对于任意 \(j \in [1,i]\)，均满足序列中有一个数属于 \((d(j-1),dj]\) 的最大 \(i\)。
所以问题可以转化成设 \(t_{i,j}\) 表示 \(d\) 等于 \(i\) 时，覆盖到第 \(j\) 段的最早时间，\(a_i\) 表示出现数 \(i\) 的最早时间，显然 \(t_{i,j}=\max\{t_{i,j-1},\min\limits_{k\in(i(j-1),ij]}\{a_k\}\}\)。显然 \(t\) 单调，那么我们按时间从小到大，在时间 \(t_{i,j}\) 对伤害 \(i\) 单点加，区间查询，用树状数组即可。
到这一步其实就已经做完了，考虑 \(t_{i,j}\) 只有 \(n\ln n\) 个值，树状数组复杂度 \(\mathcal O(\log n)\)，总时间复杂度 \(\mathcal O(n\ln n\log n)\)，常数巨小，可过。
- code
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
using namespace std;
namespace IO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#define FileIO(ch) void()
#else
#define gh() getchar()
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
#endif
inline long long read() {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(long long x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar((x % 10) | 48);
}
}
using IO::read;
using IO::write;
const int maxn(1e5 + 500), maxm(1e6 + 500);
int n, m, tot, a[maxn], f[maxn][23], lg[maxn];
vector<int> vc[maxm];
namespace BIT {
int tr[maxn];
#define lowbit(x) (x & (-x))
inline void upd (int x, int v) {
for (; x <= n; x += lowbit(x)) tr[x] += v;
}
inline int qry (int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += tr[x];
return res;
}
}
struct qNode {
int t, x, y;
} q[maxm];
inline int qry (int l, int r) {
int len = lg[r - l + 1];
return min(f[l][len], f[r - (1 << len) + 1][len]);
}
int main() {
n = read(), m = read();
for_each(a + 1, a + n + 1, [] (int &x) { x = m + 1; });
for (int i = 1; i <= m; i++) {
int opt = read();
if (opt == 1) {
int x = read();
a[x] = min(a[x], i);
} else {
++tot;
q[tot].x = read(), q[tot].y = read(), q[tot].t = i;
}
}
for (int i = 1; i <= n; i++) f[i][0] = a[i];
for (int j = 1; j < 23; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; i++) {
BIT::upd(i, 1);
int p = 0;
for (int j = 1; j <= n; j += i) {
p = max(p, qry(j, min(i + j - 1, n)));
vc[p].push_back(i);
}
}
for (int i = 1, t = 0; i <= tot; i++) {
while (t < q[i].t) {
++t;
for (int x : vc[t]) BIT::upd(x, 1);
}
writeln(BIT::qry(q[i].y) - BIT::qry(q[i].x - 1));
}
fprintf(stderr, "Time: %d ms", clock());
}
// I love WHQ!
纵使日薄西山
- 题意
给定长度为 \(n\) 的序列 \(a\)，每次操作选择最大的数 \(a_x\)，并将 \(a_{x-1},a_x,a_{x+1}\) 减 \(1\)，问多少次操作能使序列全部数变为 \(0\)。
支持单点修改。
- 分析
仔细思考发现对于一个 \(x\)，显然它左右两个数都不可能备选到了，因此这个数对答案的贡献显然是 \(a_x\)，即这个数本身。
考虑将这个记录搬到一个极长单调子段，显然只能取到最大，第三大，第五大……
总之就是跳着取。那我们可以考虑用奇和偶两颗树状数组分别维护其和，并每次取与最大值奇偶性相同的那颗查询。
你发现当你修改 \(a_i\) 的值的时候，只会影响到 \(a_{i-1},a_i,a_{i+1}\) 是否为极值，所以用 set 暴力修改就可以了！
- code
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define iter set<int>::iterator
using namespace std;
namespace IO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#define FileIO(ch) void()
#else
#define gh() getchar()
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
#endif
inline long long read() {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(long long x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar((x % 10) | 48);
}
}
using IO::read;
using IO::write;
const int maxn(1e5 + 500);
int n, m, a[maxn];
LL ans;
set<int> st;
struct BIT {
LL tr[maxn];
#define lowbit(x) (x & (-x))
inline void upd (int x, int v) {
for (; x <= n; x += lowbit(x)) tr[x] += v;
}
inline LL qry (int x) {
LL res = 0;
for (; x; x -= lowbit(x)) res += tr[x];
return res;
}
} bt[2];
inline void chk (int x) {
if (!((a[x - 1] < a[x]) ^ (a[x] < a[x + 1]))) st.erase(x);
else st.insert(x);
}
inline void calc (iter l, iter r, int cf) {
while (l != r) {
iter p = prev(r);
if (a[*r] > a[*p]) {
int t = *r & 1;
ans += (bt[t].qry(*r) - bt[t].qry(*p)) * cf;
} else {
int t = *p & 1;
ans += (bt[t].qry(*r - 1) - bt[t].qry(*p)) * cf;
iter q = next(r);
if (q == st.end()) --q;
if (!(*r - *p & 1) && !(*q - *r & 1)) ans += a[*r] * cf;
}
--r;
}
if (a[*r] >= a[*r + 1]) return;
iter p = r, q = next(r);
if (p != st.begin()) --p;
if (q == st.end()) --q;
if (!(*r - *p & 1) && !(*q - *r & 1)) ans += a[*r] * cf;
}
inline void upd (int x, int y) {
iter r = next(st.upper_bound(x)), l = prev(st.lower_bound(x));
if (l != st.begin()) --l;
if (r == st.end()) --r;
calc(l, r, -1);
bt[x & 1].upd(x, y - a[x]), a[x] = y;
if (x > 1) chk(x - 1);
if (x < n) chk(x + 1);
chk(x);
calc(l, r, 1);
}
int main() {
n = read();
st.insert(0), st.insert(n + 1);
for (int i = 1; i <= n; i++) upd(i, read());
m = read();
while (m--) {
int x = read(), y = read();
upd(x, y);
writeln(ans);
}
fprintf(stderr, "Time: %d ms", clock());
}
// I love WHQ!
盼君勿忘
- 题意
珂朵莉给了你一个序列，每次查询一个区间 \([l,r]\) 中所有子序列分别去重后的和 \(\bmod p\)。
- 分析
首先对于一个数 \(x\)，它对长度为 \(L\) 的区间贡献为 \(x(2^L-2^{cnt})\)。注意到对于一个固定的区间贡献次数只跟出现次数有关，考虑将所有出现次数相同的 \(x\) 放到一起算，用莫队解决。
你仔细一算，发现长度不同的区间不超过 \(\mathcal O(\sqrt n)\) 个，我们要支持 \(\mathcal O(1)\) 插入，删除，求 \(2\) 的次幂，直接上链表解决插入删除，光速幂解决次幂，总复杂度 \(\mathcal O(n\sqrt n)\)。
- code
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;
namespace IO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
inline long long read() {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(long long x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar((x % 10) | 48);
}
}
using IO::read;
using IO::write;
const int maxn(2e5 + 500), maxk(500);
int n, m, a[maxn], sqn, cnt[maxn], mod, ans[maxn];
LL sum[maxn];
namespace ksm {
int p[maxk], q[maxk];
inline void init (int _mod) {
mod = _mod;
p[0] = 1;
for (int i = 1; i <= sqn; i++) p[i] = p[i - 1] * 2 % mod;
q[0] = 1;
for (int i = 1; i <= 400; i++) q[i] = (LL)q[i - 1] * p[sqn] % mod;
}
inline int qry (int x) {
return (LL)q[x / sqn] * p[x % sqn] % mod;
}
}
struct qNode {
int id, l, r, mod;
qNode (int _id = 0, int _mod = 0, int _r = 0, int _l = 0) : id(_id), l(_l), r(_r), mod(_mod) {}
inline bool operator < (const qNode &rhs) const {
return l / sqn == rhs.l / sqn ? ((l / sqn & 1) ? r < rhs.r : r > rhs.r) : l < rhs.l;
}
} q[maxn];
namespace List {
int nx[maxn], pr[maxn];
inline void insert (int x) {
pr[x] = 0, nx[x] = nx[0], pr[nx[x]] = nx[0] = x;
}
inline void erase (int x) {
nx[pr[x]] = nx[x], pr[nx[x]] = pr[x], nx[x] = pr[x] = 0;
}
}
inline void add (int x) {
sum[cnt[x]] -= x;
if (!sum[cnt[x]]) List::erase(cnt[x]);
++cnt[x];
if (!sum[cnt[x]]) List::insert(cnt[x]);
sum[cnt[x]] += x;
}
inline void del (int x) {
sum[cnt[x]] -= x;
if (!sum[cnt[x]]) List::erase(cnt[x]);
--cnt[x];
if (!sum[cnt[x]]) List::insert(cnt[x]);
sum[cnt[x]] += x;
}
int main() {
n = read(), m = read(), sqn = sqrt(n);
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= m; i++) q[i] = qNode(i, read(), read(), read());
sort(q + 1, q + m + 1);
for (int i = 1, l = 1, r = 0; i <= m; i++) {
while (l > q[i].l) add(a[--l]);
while (r < q[i].r) add(a[++r]);
while (l < q[i].l) del(a[l++]);
while (r > q[i].r) del(a[r--]);
ksm::init(q[i].mod);
int U = ksm::qry(r - l + 1);
for (int x = List::nx[0]; x; x = List::nx[x]) ans[q[i].id] = (ans[q[i].id] + sum[x] * (U - ksm::qry(r - l + 1 - x) + mod) % mod) % mod;
}
for (int i = 1; i <= m; i++) writeln(ans[i]);
}
// I love WHQ!
世界上最幸福的女孩
- 题意
长度为 \(n\) 的序列 \(a\)，\(m\) 次操作：
- 全局加 \(x\)。
- 查询区间 \([l,r]\) 的最大子段和。
- 分析
前置知识
- 闵可夫斯基和，不会的话出门右转 P4557 [JSOI2018]战争，我的学习笔记。
- 线段树，不会的话建议闭关三年在来打这题。
- 极高超的卡常技术，不具备的话建议多打几道 Ynoi。
- 线段树维护区间最大子段和，不会的话出门右转 P4513 小白逛公园。
正题
考虑去掉全局加就是简单线段树维护，但是加上全局加后，最大子段和就跟子段长度有关了，这样的话，我们就必须考虑维护跟长度有关的几个函数。
令 \(lmx(x)\)，表示长度为 \(x\) 的时候的最大前缀，\(rmx(x)\) 和 \(ans(x)\) 同理。
显然根据最大子段和的经典套路，有：
\[lmx(x) = \max(lmx_{ls}(x),sum_{ls} + lmx_{rs}(x))
\]
\[rmx(x) = \max(rmx_{rs}(x),sum_{rs} + rmx_{ls}(x))
\]
\[ans(x) \leftarrow \max(ans_{ls}(x),ans_{rs}(x))
\]
显然可以发现还漏了一部分：
\[rmx_{ls}(x)+lmx_{rs}(x) \rightarrow ans(x+y)
\]
为了处理这种情况，我们可以将其看成二位平面上的点 \((x,f(x))\)，这里 \(f\) 可以是 \(lmx,rmx,ans\)。
那么这种特殊的转移可以被看成是两个向量相加，做过闵可夫斯基和就能一眼看出来 \(ans = rmx_{ls}+lmx_{rs}\)。
对于每一个全局加的 \(k\) 就可以看成最大化 \(kx + y\) 的形式，那直接在凸包上二分就好了，时间复杂度 \(\mathcal O(n\log^2 n)\)。
考虑如果将所有全局加累加到每一个询问上，我们就能保证 \(k\) 单调递增，那在凸包上记一下上次的决策在什么地方，让后继续往下跑就行了，时间复杂度 \(\mathcal O(n\log n)\)。
让后你可以得到这份代码 (用 vector 实现)。
还没结束！！！
#include <bits/stdc++.h>
#define ll long long
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
using namespace std;
namespace IO{
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define reg register
inline long long read () {
reg char ch = gh();
reg long long x = 0;
reg char t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? -x : x;
}
inline void write(long long x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using IO::read;
using IO::write;
const int maxn(3e5 + 500), maxm(6e5 + 500);
const ll inf(1e16 + 233);
struct Point {
ll x, y;
inline Point operator + (const Point &rhs) const {
return {x + rhs.x, y + rhs.y};
}
inline Point operator - (const Point &rhs) const {
return {x - rhs.x, y - rhs.y};
}
inline ll operator * (const Point &rhs) const {
return x * rhs.y - rhs.x * y;
}
inline bool operator < (const Point &rhs) const {
return (*this) * rhs >= 0;
}
};
ll tg, a[maxn], ans[maxm];
struct Hull {
vector <Point> a;
int pnt;
Hull () { pnt = 0; }
inline Point operator [] (const int& pos) const {
return a[pos];
}
inline void insert (const Point &rhs) {
a[rhs.x].y = max(a[rhs.x].y, rhs.y);
}
inline void pb (const Point &rhs) {
a.push_back(rhs);
}
inline void reset (const int len) {
a.clear();
a.push_back({0, 0});
for (int i = 1; i <= len; i++) a.push_back({i, -inf});
}
inline void Convex () {
int sz = a.size();
if (sz <= 2) return;
int top = 1;
for (int i = 2; i < sz; i++) {
if (a[i].y == -inf) continue;
while (top > 0 && a[top] - a[top - 1] < a[i] - a[top - 1]) top--;
a[++top] = a[i];
}
for (int i = 1; i < sz - top; i++) a.pop_back();
}
inline ll maxv () {
int sz = a.size();
while (pnt < sz - 1 && tg * (a[pnt + 1].x - a[pnt].x) + (a[pnt + 1].y - a[pnt].y) > 0) pnt++;
return tg * a[pnt].x + a[pnt].y;
}
};
struct Node {
ll l, r, mid, s;
inline Node operator + (const Node &rhs) const {
return {max(l, s + rhs.l), max(rhs.r, rhs.s + r), max({mid, rhs.mid, r + rhs.l}), s + rhs.s};
}
};
struct SGT {
Hull lmx[maxn << 2], rmx[maxn << 2], ans[maxn << 2];
ll sum[maxn << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
inline void preMerge (Hull &c, const Hull &a, const Hull &b, const Point &addv) {
int sza = a.a.size(), szb = b.a.size();
for (int i = 0; i < sza; i++) c.pb(a[i]);
for (int i = 0; i < szb; i++) c.pb(b[i] + addv);
c.Convex();
}
inline void Minkowski (Hull &c, const Hull &a, const Hull &b) {
int i = 0, j = 0, sza = a.a.size(), szb = b.a.size();
c.insert(a[i] + b[j]);
while (i < sza - 1 && j < szb - 1) {
if (a[i + 1] - a[i] < b[j + 1] - b[j]) j++;
else i++;
c.insert(a[i] + a[j]);
}
while (i < sza - 1) ++i, c.insert(a[i] + b[j]);
while (j < szb - 1) ++j, c.insert(a[i] + b[j]);
}
inline void build (int l, int r, int p) {
if (l == r) {
lmx[p].pb({0, 0});
lmx[p].pb({1, a[l]});
ans[p].pb({0, 0});
ans[p].pb({1, a[l]});
rmx[p].pb({0, 0});
rmx[p].pb({1, a[l]});
sum[p] = a[l];
return;
}
const int mid = (l + r) >> 1;
build(l, mid, ls);
build(mid + 1, r, rs);
preMerge(lmx[p], lmx[ls], lmx[rs], {mid - l + 1, sum[ls]});
preMerge(rmx[p], rmx[rs], rmx[ls], {r - mid, sum[rs]});
ans[p].reset(r - l + 1);
int sz = ans[ls].a.size();
for (int i = 0; i < sz; i++) ans[p].insert(ans[ls][i]);
sz = ans[rs].a.size();
for (int i = 0; i < sz; i++) ans[p].insert(ans[rs][i]);
Minkowski(ans[p], rmx[ls], lmx[rs]);
ans[p].Convex();
sum[p] = sum[ls] + sum[rs];
}
inline Node query (int s, int t, int l, int r, int p) {
if (s <= l && r <= t) return {lmx[p].maxv(), rmx[p].maxv(), ans[p].maxv(), sum[p] + 1ll * (r - l + 1) * tg};
const int mid = (l + r) >> 1;
if (mid < s) return query(s, t, mid + 1, r, rs);
else if (t <= mid) return query(s, t, l, mid, ls);
else return query(s, t, l, mid, ls) + query(s, t, mid + 1, r, rs);
}
} s;
int n, m, tot;
struct Query {
int l, r, id;
ll tg;
inline bool operator < (const Query &rhs) const {
return tg < rhs.tg;
}
} q[maxm];
int main () {
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= m; i++) {
int opt = read();
if (opt == 1) tg += read();
else q[++tot] = {read(), read(), tot, tg};
}
m = tot;
sort(q + 1, q + m + 1);
for (int i = 1; i <= n; i++) a[i] += q[1].tg;
for (int i = m; i; i--) q[i].tg -= q[1].tg;
s.build(1, n, 1);
for (int i = 1; i <= m; i++) {
tg = q[i].tg;
ans[q[i].id] = s.query(q[i].l, q[i].r, 1, n, 1).mid;
}
for (int i = 1; i <= m; i++) write(ans[i]), puts("");
}
让后就可以开心的 MLE。
空间优化
- 第一种优化，用指针的动态分配内存，少量优化空间，但是无法解决问题。
- 接下来你发现可以一边建树，一边查询，这样始终只需要一层空间，当前节点的左右儿子可以从
build里面返回。具体的，对于当前区间 \([l,r]\) 只需要用到内存中 \([l,r]\) 的部分，应为长度不可能超过 \(r-l+1\)，向下递归时使用空间 \([l,mid]\)，\([mid+1,r]\) 即可。 - 如果你用
vector对每个节点存储询问，那你仍然会祭，于是你想到，询问可以在 build 的过程中递归传下去，这样就不用存了，空间复杂度变为了 \(\mathcal O(n)\)。
如果完成了上述过程，恭喜你通过了此题！
- \(\mathcal {AC}\) code
#include <bits/stdc++.h>
#define ll long long
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
using namespace std;
namespace IO{
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define reg register
inline long long read () {
reg char ch = gh();
reg long long x = 0;
reg char t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? -x : x;
}
inline void write(long long x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using IO::read;
using IO::write;
const int maxn(3e5 + 5), maxm(6e5 + 5);
const ll inf(1e16 + 233);
struct Point {
ll x, y;
inline Point operator + (const Point &rhs) const {
return {x + rhs.x, y + rhs.y};
}
inline Point operator - (const Point &rhs) const {
return {x - rhs.x, y - rhs.y};
}
inline ll operator * (const Point &rhs) const {
return x * rhs.y - rhs.x * y;
}
inline bool operator < (const Point &rhs) const {
return (*this) * rhs >= 0;
}//判断左右关系
};//定义向量
ll tg, a[maxn];
struct Hull {
Point* a;
int sz, pnt;
Hull () { sz = pnt = 0; }
inline Point& operator [] (const int &pos) const {
return a[pos];
}
inline void insert (const Point &rhs) {
a[rhs.x].y = max(a[rhs.x].y, rhs.y);
}
inline void pb (const Point &rhs) {
a[++sz] = rhs;
}
inline void reset (const int len) {
for (int i = 1; i <= len; i++) a[i] = {i, -inf};
sz = len;
}
inline void Convex () {
if (sz <= 2) return;
int top = 2;
for (int i = 3; i <= sz; i++) {
if (a[i].y == -inf) continue;
while (top > 1 && a[top] - a[top - 1] < a[i] - a[top - 1]) top--;
a[++top] = a[i];
}
sz = top;
pnt = 1;
}
inline ll maxv () {
while (pnt < sz && tg * (a[pnt + 1].x - a[pnt].x) + (a[pnt + 1].y - a[pnt].y) > 0) pnt++;
return tg * a[pnt].x + a[pnt].y;
}
};//对于一个凸函数，需要支持求凸包，单点取 max，和插入
struct Node {
ll l, r, mid, s;
inline Node operator + (const Node &rhs) const {
Node res = {max(l, s + rhs.l), max(rhs.r, rhs.s + r), max({mid, rhs.mid, r + rhs.l}), s + rhs.s};
return res;
}
} ans[maxm];
vector <int> qry;
struct Query {
int l, r, id;
ll tg;
inline bool operator < (const Query &rhs) const {
return tg < rhs.tg;
}
} q[maxm];
struct SGT {
struct SGTNode { Hull lmx, rmx, ans; ll sum; };
Point bl[maxn << 1], br[maxn << 1], bm[maxn << 1], tl[maxn], tr[maxn], tm[maxn];
Point *tmpl = bl, *tmpr = br, *tmpm = bm;//这里动态的维护空间
inline void preMerge (Hull &c, const Hull &a, const Hull &b, const Point &addv) {
for (int i = 1; i <= a.sz; i++) c.pb(a[i]);
for (int i = 1; i <= b.sz; i++) c.pb(b[i] + addv);
c.Convex();
}//lmx 和 rmx 的维护
inline void Minkowski (Hull &c, const Hull &a, const Hull &b) {
int i = 1, j = 1;
c.insert(a[i] + b[j]);
while (i < a.sz && j < b.sz) c.insert((a[i + 1] - a[i] < b[j + 1] - b[j]) ? a[i] + b[++j] : a[++i] + b[j]);
while (i < a.sz) c.insert(a[++i] + b[j]);
while (j < b.sz) c.insert(a[i] + b[++j]);
}//闵可夫斯基和
#define ls (p << 1)
#define rs (p << 1 | 1)
inline SGTNode build (int l, int r, int p) {
const int mid = (l + r) >> 1;
SGTNode lc, rc, now;
vector <int> tmp, whq;//这里分别存储要想下传的询问，和需要在这里查询的询问
now.lmx.a = tl, now.rmx.a = tr, now.ans.a = tm;
for (int x : qry) {
if (q[x].r < l || q[x].l > r) continue;
if (q[x].l <= l && r <= q[x].r) whq.push_back(x);//查询的区间没有继续递归的必要
else tmp.push_back(x);
}
if (l == r) {
now.lmx.a[1] = now.rmx.a[1] = now.ans.a[1] = {0, 0};
now.lmx.a[2] = now.rmx.a[2] = now.ans.a[2] = {1, a[l]};
now.lmx.sz = now.rmx.sz = now.ans.sz = 2;
now.sum = a[l];
lc.lmx.a = tmpl, lc.rmx.a = tmpr, lc.ans.a = tmpm;
tmpl += 2, tmpr += 2, tmpm += 2;
goto end;
}
qry = tmp;
lc = build(l, mid, ls);
qry = tmp;
rc = build(mid + 1, r, rs);
preMerge(now.lmx, lc.lmx, rc.lmx, {mid - l + 1, lc.sum});
preMerge(now.rmx, rc.rmx, lc.rmx, {r - mid, rc.sum});//转移 1，2
now.ans.a++;
now.ans.reset(r - l + 1);//区间长度 [1, r - l + 1]
for (int i = 1; i <= lc.ans.sz; i++) now.ans.insert(lc.ans[i]);
for (int i = 1; i <= rc.ans.sz; i++) now.ans.insert(rc.ans[i]);//转移 3
Minkowski(now.ans, lc.rmx, rc.lmx);// 转移 4
now.ans.a--;
now.ans[1] = {0, 0};//可以不选
now.ans.sz++;
now.ans.Convex();
now.sum = lc.sum + rc.sum;
end:
now.lmx.pnt = now.rmx.pnt = now.ans.pnt = 1;
for (int i : whq) {
tg = q[i].tg;
Node res = {now.lmx.maxv(), now.rmx.maxv(), now.ans.maxv(), now.sum + (r - l + 1) * tg};
ans[q[i].id] = ans[q[i].id] + res;
}
Point *xl = lc.lmx.a, *xr = lc.rmx.a, *xm = lc.ans.a;
for (int i = 1; i <= now.lmx.sz; i++) xl[i] = now.lmx.a[i];
for (int i = 1; i <= now.rmx.sz; i++) xr[i] = now.rmx.a[i];
for (int i = 1; i <= now.ans.sz; i++) xm[i] = now.ans.a[i];
now.lmx.a = xl, now.rmx.a = xr, now.ans.a = xm;//由于可以不选，空间并非紧密相连，所以从做儿子的位置开始存储当前区间的答案
return now;
}
} s;
int n, m, tot;
int main () {
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= m; i++) {
int opt = read();
if (opt == 1) tg += read();
else q[++tot] = {read(), read(), tot, tg};
}
m = tot;
sort(q + 1, q + m + 1);
for (int i = 1; i <= m; i++) qry.push_back(i);
s.build(1, n, 1);
for (int i = 1; i <= m; i++) write(ans[i].mid), puts("");
}
// I love WHQ!