并非所有历史和都是吉司机
A - Just Another Game of Stones
https://www.luogu.com.cn/problem/P9631
- 发现如果选定了这一步取的位置 \(i\)，那么要拿的石子是定值 \(a_i-a_i\oplus s\)，当 \(a_i\le a_i\oplus s\) 时不合法。
可以用吉司机维护修改和区间异或和，那么询问需要转化。
答案为 \(a_i>a_i\oplus s\) 的次数，结合异或是不带进位的区间加的观点，考察『加数』\(s\) 的最高位，当且仅当 \(a_i\) 在这一位为 \(1\) 时有贡献。故再维护一下每一位为 \(1\) 的个数即可。复杂度 \(O(q\log n\log V)\)。
#include <bits/stdc++.h>
const int inf = 1 << 30;
const int maxn = 2e5 + 5;
struct {
std::array<int, 30> u;
int l, r, cnt, mn, se, d, s;
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
int a[maxn];
void pushup(int p) {
if (t[lt].mn == t[rt].mn) {
t[p].mn = t[lt].mn, t[p].cnt = t[lt].cnt + t[rt].cnt;
t[p].se = std::min(t[lt].se, t[rt].se);
}
else if (t[lt].mn < t[rt].mn) {
t[p].mn = t[lt].mn, t[p].cnt = t[lt].cnt;
t[p].se = std::min(t[lt].se, t[rt].mn);
}
else {
t[p].mn = t[rt].mn, t[p].cnt = t[rt].cnt;
t[p].se = std::min(t[lt].mn, t[rt].se);
}
t[p].s = t[lt].s ^ t[rt].s;
for (int i = 0; i < 30; ++i)
t[p].u[i] = t[lt].u[i] + t[rt].u[i];
return;
}
void bld(int p, int l, int r) {
t[p].d = -inf;
t[p].l = l, t[p].r = r;
if (l == r) {
for (int i = 0; i < 30; ++i)
t[p].u[i] = (a[l] >> i) & 1;
t[p].s = t[p].mn = a[l], t[p].cnt = 1, t[p].se = inf;
return;
}
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
pushup(p);
return;
}
void pushval(int p, int v) {
if (v > t[p].mn) {
for (int i = 0; i < 30; ++i) {
if ((t[p].mn >> i) & 1)
t[p].u[i] -= t[p].cnt;
if ((v >> i) & 1)
t[p].u[i] += t[p].cnt;
}
if (t[p].cnt & 1)
t[p].s ^= t[p].mn ^ v;
t[p].mn = t[p].d = v;
}
return;
}
void pushdown(int p) {
if (t[p].d != -inf) {
pushval(lt, t[p].d), pushval(rt, t[p].d);
t[p].d = -inf;
}
return;
}
void add(int p, int l, int r, int v) {
if (t[p].mn >= v)
return;
if (l <= t[p].l && t[p].r <= r && v < t[p].se) {
pushval(p, v);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r, v);
if (r > mid)
add(rt, l, r, v);
pushup(p);
return;
}
int askt(int p, int l, int r, int i) {
if (l <= t[p].l && t[p].r <= r)
return t[p].u[i];
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1, res = 0;
if (l <= mid)
res = askt(lt, l, r, i);
if (r > mid)
res += askt(rt, l, r, i);
return res;
}
int asks(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].s;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1, res = 0;
if (l <= mid)
res = asks(lt, l, r);
if (r > mid)
res ^= asks(rt, l, r);
return res;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m;
std::cin >> n >> m;
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
bld(1, 1, n);
for (int op, l, r, v; m--; ) {
std::cin >> op >> l >> r >> v;
if (op == 1)
add(1, l, r, v);
else {
int s = asks(1, l, r) ^ v;
if (s == 0) {
std::cout << 0 << '\n';
continue;
}
int t = std::__lg(s);
std::cout << askt(1, l, r, t) + ((v >> t) & 1) << '\n';
}
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}B - Prof. Pang’s sequence / C - TEST_90
https://www.luogu.com.cn/problem/P10822 / https://www.luogu.com.cn/problem/P9990
- 历史和维护子区间问题是一个固定的 trick，只需要对于每一个 \(r\)，给合法的 \(l\) 加一。
- 离线扫描线，对于当前右端点 \(r\)，记录每种数最后一次出现的位置 \(pos\)。令 \(r\) 的颜色为
1，从右到左，每碰到一个新的 \(pos\) 就切换颜色 - 显然对于当前 \(r\)，应该被加一的 \(l\) 就是颜色为
1的这些位置。 - 考虑更快地维护这个过程，也就是在 \(r\) 的颜色和 \(r-1\) 不同时就可以对 \([1,r)\) 做一次 flip，是可行的
- 在每个 \(r\) 处查询 \([l,r]\) 的区间和即可。
- 吐槽：并非所有历史和都是吉司机
#include <bits/stdc++.h>
const int maxn = 5e5 + 5;
struct {
long long s;
int l, r, d0, d1, df, ds, u0, u1;
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void pushup(int p) {
t[p].u0 = t[lt].u0 + t[rt].u0;
t[p].u1 = t[lt].u1 + t[rt].u1;
return;
}
void pushval(int p, long long v0, long long v1, bool f) {
if (f) {
t[p].df ^= 1;
std::swap(t[p].u0, t[p].u1);
std::swap(t[p].d0, t[p].d1);
}
t[p].d0 += v0, t[p].d1 += v1;
t[p].s += t[p].u0 * v0 + t[p].u1 * v1;
return;
}
void pushdown(int p) {
pushval(lt, t[p].d0, t[p].d1, t[p].df);
pushval(rt, t[p].d0, t[p].d1, t[p].df);
t[p].d0 = t[p].d1 = t[p].df = 0;
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
t[p].u0 = r - l + 1;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void flip(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r) {
pushval(p, 0, 0, 1);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
flip(lt, l, r);
if (r > mid)
flip(rt, l, r);
pushup(p);
return;
}
long long ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].s;
pushdown(p);
auto res(0ll);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
res = ask(lt, l, r);
if (r > mid)
res += ask(rt, l, r);
return res;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1), la(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
int m;
std::cin >> m;
std::vector<long long> res(m + 1);
std::vector<std::vector<std::pair<int, int> > > u(n + 1);
for (int i = 1, l, r; i <= m; ++i) {
std::cin >> l >> r;
u[r].emplace_back(l, i);
}
bld(1, 1, n);
for (int r = 1; r <= n; ++r) {
flip(1, la[a[r]] + 1, r);
pushval(1, 0, 1, 0);
for (auto [l, id] : u[r])
res[id] = ask(1, l, r);
la[a[r]] = r;
}
for (int i = 1; i <= m; ++i)
std::cout << res[i] << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}D - Stations
https://www.luogu.com.cn/problem/CF1572F
- 不太能直接维护 \(b\)，但发现如果维护每个 \(i\) 最远能到达的点，发现每次更新 \(j\) 会把 \(j\) 左边的所有点值和 \(j-1\) 取 min。
- 发现吉司机能够在取 min 的同时在另一个树状树组里维护差分
- 需要注意更新的时机，应该是每次线段树更新函数访问到完整节点时。
- 复杂度 \(O(q\log^2n)\)。但真的吗？单点修改似乎对势能有影响？然而并不会相关分析。
看起来有点激进了，没想到确实是正解。
可以发现树状数组在时间上确实是有优势的
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
const int inf = 0x3f3f3f3f;
struct {
int l, r, mx, se, d, cnt;
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
int n;
long long bit[maxn][2];
int lowbit(int x) { return x & -x; }
void add(int x, long long v) {
for (int i = x; i <= n; i += lowbit(i))
bit[i][0] += v, bit[i][1] += v * (x - 1);
return;
}
long long ask(int x) {
auto res = 0ll;
for (int i = x; i; i -= lowbit(i))
res += bit[i][0] * x - bit[i][1];
return res;
}
void pushup(int p) {
if (t[lt].mx == t[rt].mx) {
t[p].mx = t[lt].mx, t[p].cnt = t[lt].cnt + t[rt].cnt;
t[p].se = std::max(t[lt].se, t[rt].se);
}
else if (t[lt].mx > t[rt].mx) {
t[p].mx = t[lt].mx, t[p].cnt = t[lt].cnt;
t[p].se = std::max(t[lt].se, t[rt].mx);
}
else {
t[p].mx = t[rt].mx, t[p].cnt = t[rt].cnt;
t[p].se = std::max(t[lt].mx, t[rt].se);
}
return;
}
void bld(int p, int l, int r) {
t[p].d = inf;
t[p].l = l, t[p].r = r;
if (l == r) {
add(l, 1), add(l + 1, -1);
t[p].mx = l, t[p].se = -1, t[p].cnt = 1;
return;
}
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
pushup(p);
return;
}
void pushval(int p, int v) {
if (v <= t[p].mx)
t[p].mx = t[p].d = v;
return;
}
void pushdown(int p) {
if (t[p].d != inf) {
pushval(lt, t[p].d), pushval(rt, t[p].d);
t[p].d = inf;
}
return;
}
void add(int p, int l, int r, int v) {
if (t[p].mx <= v)
return;
if (l <= t[p].l && t[p].r <= r && v > t[p].se) {
add(t[p].mx + 1, t[p].cnt);
add(v + 1, -t[p].cnt);
pushval(p, v);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r, v);
if (r > mid)
add(rt, l, r, v);
pushup(p);
return;
}
void upd(int p, int x, int v) {
if (t[p].l == t[p].r) {
add(t[p].mx + 1, 1), add(v + 1, -1);
t[p].mx = v;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid)
upd(lt, x, v);
else
upd(rt, x, v);
pushup(p);
return;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int m;
std::cin >> n >> m;
bld(1, 1, n);
for (int op; m--; ) {
std::cin >> op;
if (op == 1) {
int x, v;
std::cin >> x >> v;
if (x != 1)
add(1, 1, x - 1, x - 1);
upd(1, x, v);
// for (int i = 1; i <= n; ++i)
// std::cout << ask(i) - ask(i - 1) << ' ';
// std::cout << '\n';
}
else {
int l, r;
std::cin >> l >> r;
std::cout << ask(r) - ask(l - 1) << '\n';
}
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}E - LuoTianyi and the Function
https://codeforces.com/problemset/problem/1824/D
- 由于 \(j\) 和函数关联更强，考虑把 \(j\) 这一维扫描线 + 差分掉
- 经典套路，维护每个 \(x\) 从右向左第一次出现的位置 \(pos_x\)
- 每次 \(j\) 移动一下，会更新一段区间（可能不存在）的 \(g\) 值，它们原本为 \(pos_{a_j}\)，需要被更新为下一个 \(pos\)。
- 记录值为 \(pos_x\) 的区间，做区间赋值历史和即可。
#include <bits/stdc++.h>
const int maxn = 1e6 + 5;
struct {
int l, r;
long long d1, d2, d3, u, s;
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void pushup(int p) {
t[p].u = t[lt].u + t[rt].u;
t[p].s = t[lt].s + t[rt].s;
return;
}
void pushval(int p, long long d1, long long d2, long long d3) {
t[p].s += t[p].u * d2 + d3 * (t[p].r - t[p].l + 1);
t[p].d3 += d3;
if (t[p].d1)
t[p].d3 += t[p].d1 * d2;
else
t[p].d2 += d2;
if (d1) {
t[p].u = d1 * (t[p].r - t[p].l + 1);
t[p].d1 = d1;
}
return;
}
void pushdown(int p) {
pushval(lt, t[p].d1, t[p].d2, t[p].d3);
pushval(rt, t[p].d1, t[p].d2, t[p].d3);
t[p].d1 = t[p].d2 = t[p].d3 = 0ll;
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r)
return;
int mid = (t[p].l + t[p].r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void upd(int p, int l, int r, long long v) {
if (l <= t[p].l && t[p].r <= r) {
pushval(p, v, 0ll, 0ll);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
upd(lt, l, r, v);
if (r > mid)
upd(rt, l, r, v);
pushup(p);
return;
}
long long ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].s;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
auto res = 0ll;
if (l <= mid)
res = ask(lt, l, r);
if (r > mid)
res += ask(rt, l, r);
return res;
}
signed main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, q;
std::cin >> n >> q;
std::vector<int> a(n + 1), la(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
struct query { int l, r, id, k; };
std::vector<long long> res(q + 1);
std::vector<std::vector<query> > u(n + 1);
for (int i = 1, l, r, x, y; i <= q; ++i) {
std::cin >> l >> r >> x >> y;
if (x != 1)
u[x - 1].push_back({ l, r, i, -1 });
u[y].push_back({ l, r, i, 1 });
}
bld(1, 1, n);
std::vector<int> pre(n + 2), nex(n + 2), l(n + 2);
pre[n + 1] = 0, nex[0] = n + 1;
for (int i = 1; i <= n; ++i) {
int p = la[a[i]];
nex[pre[n + 1]] = i, pre[i] = pre[n + 1], pre[n + 1] = i, nex[i] = n + 1;
l[i] = i;
if (p != 0) {
upd(1, l[p], p, nex[p]);
l[nex[p]] = l[p];
pre[nex[p]] = pre[p], nex[pre[p]] = nex[p];
}
upd(1, i, i, i);
pushval(1, 0, 1, 0);
for (auto [l, r, id, k] : u[i])
res[id] += k * ask(1, l, r);
la[a[i]] = i;
}
for (int i = 1; i <= q; ++i)
std::cout << res[i] << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}F - Yunli’s Subarray Queries (extreme version)
https://codeforces.com/problemset/problem/2009/G3
- 考虑对 \(\forall i\)，令 \(a_i\gets a_i-i\)，那么能够参与同一个连续子段的元素值应相同
显然对于任意一个长度为 \(k\) 的子段，其答案为 \(k\) 减去众数出现次数（\([l, r]\) 处答案记为 \(g_r\)）
这一点可以用类似莫队的方法来做那么对于更长的子段 \([l, r]\)，其 \(f\) 就是 \(\min\limits_{l+k-1\le i\le r}\{g_i\}\)
原问题中的一次 \([l, r]\) 的询问就可以转化为 \(\sum\limits_{i=l+k-1}^r\sum\limits_{j=i}^r\min\{ g_{i\sim j}\}\)这里有一个 trick：扫描线时可以用单调栈的想法来维护最小值操作，那么就把最值操作转化为一般的区间加历史和了。
#include <bits/stdc++.h>
const int maxn = 1e6 + 5;
struct {
int l, r;
long long d1, d2, d3, u, s;
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void pushup(int p) {
t[p].u = t[lt].u + t[rt].u;
t[p].s = t[lt].s + t[rt].s;
return;
}
void pushval(int p, long long d1, long long d2, long long d3) {
t[p].s += t[p].u * d2 + d3 * (t[p].r - t[p].l + 1);
t[p].d3 += d3 + t[p].d1 * d2;
t[p].d2 += d2;
t[p].u += d1 * (t[p].r - t[p].l + 1);
t[p].d1 += d1;
return;
}
void pushdown(int p) {
pushval(lt, t[p].d1, t[p].d2, t[p].d3);
pushval(rt, t[p].d1, t[p].d2, t[p].d3);
t[p].d1 = t[p].d2 = t[p].d3 = 0ll;
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
t[p].u = t[p].s = 0ll;
t[p].d1 = t[p].d2 = t[p].d3 = 0;
if (l == r)
return;
int mid = (t[p].l + t[p].r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void add(int p, int l, int r, long long v) {
if (l <= t[p].l && t[p].r <= r) {
pushval(p, v, 0ll, 0ll);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r, v);
if (r > mid)
add(rt, l, r, v);
pushup(p);
return;
}
long long ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].s;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
auto res = 0ll;
if (l <= mid)
res = ask(lt, l, r);
if (r > mid)
res += ask(rt, l, r);
return res;
}
signed main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, k, q;
std::cin >> n >> k >> q;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i], a[i] -= i;
bld(1, 1, n);
std::vector<int> g(n + 1);
std::unordered_map<int, int> cnt;
std::multiset<int> t;
for (int i = 1; i <= n; ++i) {
if (i > k) {
t.erase(t.find(cnt[a[i - k]]));
if (--cnt[a[i - k]])
t.insert(cnt[a[i - k]]);
}
if (cnt[a[i]])
t.erase(t.find(cnt[a[i]]));
t.insert(++cnt[a[i]]);
if (i >= k)
g[i] = k - *--t.end();
}
std::vector<long long> res(q + 1);
std::vector<std::vector<std::pair<int, int> > > u(n + 1);
for (int i = 1, l, r; i <= q; ++i) {
std::cin >> l >> r;
u[r].emplace_back(l + k - 1, i);
}
std::stack<std::pair<int, int> > st;
for (int i = 1; i <= n; ++i) {
std::pair<int, int> now(g[i], i);
add(1, i, i, g[i]);
for (; !st.empty() && st.top() > now; st.pop()) {
auto [v, p] = st.top();
add(1, p, now.second - 1, g[i] - v);
now.second = p;
}
st.push(now);
pushval(1, 0ll, 1ll, 0ll);
for (auto [l, id] : u[i])
res[id] = ask(1, l, i);
}
for (int i = 1; i <= q; ++i)
std::cout << res[i] << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}