ds is fun ——@crashed
Warm up! I
多重集 / 彩虹蛋糕
http://222.180.160.110:61235/contest/6010/problem/7
好像并不是第一次见了？像是把几个二元组的同一维拿来整活，可以考虑恒等变形转化为偏序问题。
若 \(a_{i,0}+b_{j,0}\ge a_{i,1}+b_{j,1}\)，则 \(a_{i,0}-a_{i,1}\ge b_{j,1}-b_{j,0}\)。如果我们把 \(a\) 按照 \(a_{i,0}-a_{i,1}\) 排序并把 \(b\) 按照 \(b_{j,1}-b_{j,0}\) 排序，那么若需要求某个时刻的答案，需要对于每一个 \(i\)，找到最小的 \(b_{j,0}\)，使得 \(b_{j,1}-b_{j,0}\) 在 \([-\infty, a_{i,0}-a_{i,1}]\) 中，同时找到最小的 \(b_{j,1}\)，使得 \(b_{j,1}-b_{j,0}\) 在 \([a_{i, 0}-a_{i,1},+\infty]\) 中。
那么有一个很神的方法（似乎也不是第一次遇到了但总结不出来 
），我们在线段树 pushup 的时候，尝试用左边的 \(b_{j,0}\) 更新右边的答案。
牢游说之所以觉得很熟悉是因为我之前 % 你赛做到过这道题还 A 了？？？离谱的。
为啥 llsw 一定说是离线啊 想不到什么好的离线解决时间限制的方案 所以还是在线。
#include <bits/stdc++.h>
const int inf = 2e9 + 1;
struct _ { long long aa, ab, ba, bb, u; int l, r, id; };
std::vector<_> t(1);
std::vector<std::multiset<long long> > aa(1), ab(1), ba(1), bb(1);
int tot, cnt;
#define lt t[p].l
#define rt t[p].r
void pushup(int p) {
t[p].aa = t[p].ab = t[p].ba = t[p].bb = t[p].u = inf;
if (lt) {
t[p].u = t[lt].u;
t[p].aa = t[lt].aa, t[p].ab = t[lt].ab, t[p].ba = t[lt].ba, t[p].bb = t[lt].bb;
}
if (rt) {
t[p].u = std::min(t[p].u, t[rt].u);
t[p].aa = std::min(t[p].aa, t[rt].aa), t[p].ab = std::min(t[p].ab, t[rt].ab), t[p].ba = std::min(t[p].ba, t[rt].ba), t[p].bb = std::min(t[p].bb, t[rt].bb);
}
if (lt && rt)
t[p].u = std::min({ t[p].u, t[lt].ba + t[rt].aa, t[lt].ab + t[rt].bb });
return;
}
int adda(int p, long long l, long long r, int x, int a, int b) {
if (!p)
p = ++tot, t.emplace_back(), t[p].aa = t[p].ab = t[p].ba = t[p].bb = t[p].u = inf;
if (l == r) {
if (!t[p].id)
t[p].id = ++cnt, aa.emplace_back(), ab.emplace_back(), ba.emplace_back(), bb.emplace_back();
int id = t[p].id;
aa[id].insert(a), ab[id].insert(b);
t[p].aa = *aa[id].begin(), t[p].ab = *ab[id].begin();
if (!aa[id].empty() && !ba[id].empty())
t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
else
t[p].u = inf;
return p;
}
long long mid = (l + r) >> 1;
if (x <= mid) {
auto s(adda(lt, l, mid, x, a, b));
lt = s;
}
else {
auto s(adda(rt, mid + 1, r, x, a, b));
rt = s;
}
pushup(p);
return p;
}
int addb(int p, long long l, long long r, int x, int a, int b) {
if (!p)
p = ++tot, t.emplace_back(), t[p].aa = t[p].ab = t[p].ba = t[p].bb = t[p].u = inf;
if (l == r) {
if (!t[p].id)
t[p].id = ++cnt, aa.emplace_back(), ab.emplace_back(), ba.emplace_back(), bb.emplace_back();
int id = t[p].id;
ba[id].insert(a), bb[id].insert(b);
t[p].ba = *ba[id].begin(), t[p].bb = *bb[id].begin();
if (!aa[id].empty() && !ba[id].empty())
t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
else
t[p].u = inf;
return p;
}
long long mid = (l + r) >> 1;
if (x <= mid) {
auto s(addb(lt, l, mid, x, a, b));
lt = s;
}
else {
auto s(addb(rt, mid + 1, r, x, a, b));
rt = s;
}
pushup(p);
return p;
}
void dela(int p, long long l, long long r, int x, int a, int b) {
if (l == r) {
int id = t[p].id;
aa[id].erase(aa[id].find(a)), ab[id].erase(ab[id].find(b));
t[p].aa = (aa[id].empty() ? inf : *aa[id].begin());
t[p].ab = (ab[id].empty() ? inf : *ab[id].begin());
if (!aa[id].empty() && !ba[id].empty())
t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
else
t[p].u = inf;
return;
}
long long mid = (l + r) >> 1;
if (x <= mid)
dela(lt, l, mid, x, a, b);
else
dela(rt, mid + 1, r, x, a, b);
pushup(p);
return;
}
void delb(int p, long long l, long long r, int x, int a, int b) {
if (l == r) {
int id = t[p].id;
ba[id].erase(ba[id].find(a)), bb[id].erase(bb[id].find(b));
t[p].ba = (ba[id].empty() ? inf : *ba[id].begin());
t[p].bb = (bb[id].empty() ? inf : *bb[id].begin());
if (!aa[id].empty() && !ba[id].empty())
t[p].u = std::min(*aa[id].begin() + *ba[id].begin(), *ab[id].begin() + *bb[id].begin());
else
t[p].u = inf;
return;
}
long long mid = (l + r) >> 1;
if (x <= mid)
delb(lt, l, mid, x, a, b);
else
delb(rt, mid + 1, r, x, a, b);
pushup(p);
return;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("set.in", "r", stdin);
std::freopen("set.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int q, rt = 0;
std::cin >> q;
for (int i = 1; i <= q; ++i) {
int op, d, a, b;
std::cin >> op >> d >> a >> b;
if (op == 0 && d == 0)
dela(rt, -inf, inf, a - b, a, b);
else if (op == 0)
delb(rt, -inf, inf, b - a, a, b);
else if (d == 0)
rt = adda(rt, -inf, inf, a - b, a, b);
else
rt = addb(rt, -inf, inf, b - a, a, b);
std::cout << (t[1].u == inf ? -1 : t[1].u) << '\n';
}
return 0;
}青蛙题
http://222.180.160.110:61235/contest/6010/problem/1
全程都是被牵着鼻子走捏。自己的大脑完全没有运转捏。开摆！
llsw：哎其实 碰到这种区间里面找区间的问题的话 扫描线 算是常见思路了。
我们会发现想到区间种类数我们会有几种思路：集合哈希、前驱后继 + 人类智慧、莫队之类的。这道题感觉是可以用集合哈希做的，但是看了一眼原题出自 Ynoi，哈哈，这道题感觉是不能用集合哈希做的 
。
大致思路是，对于 \(i=1\sim n\)，依次考虑 \(i\) 作为右端点的情况。线段树维护每个 \(j\) 作为左端点时的 \(i-r_j\)，其中 \([j, r_j]\) 是与 \([j,i]\) 种类相同的最小区间。
那么询问的时候，只需要找到最大的 \(j'\)，满足 \([j, r]\) 与 \([l, r]\) 种类相同，求解 \([l, j']\) 的区间和即可。怎么找到 \(j'\) 呢？这里就用到了前驱后继 + 人类智慧法。初始每个 \(l\) 对应的 \(j'\) 就是自己，若加入了一个与 \(l\) 相同的新元素，那么 \(l\) 就不再有贡献，此时 \(l\) 的 \(j'\) 就会继承 \(l+1\) 的 \(j'\)，这个过程用并查集即可简单维护。
#include <bits/stdc++.h>
const int lim = 2e6;
const int maxn = 2e6 + 5;
const int maxm = 5e7 + 5;
const int inf = 0x3f3f3f3f;
struct { int l, r, u, d; } t[maxn << 2];
int tot;
#define lt (p << 1)
#define rt (lt | 1)
void pushdown(int p) {
if (~t[p].d) {
t[lt].d = t[rt].d = t[p].d;
t[lt].u = t[p].d - t[lt].r + 1;
t[rt].u = t[p].d - t[rt].r + 1;
t[p].d = -1;
}
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r, t[p].d = -1;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void upd(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d = v, t[p].u = v - t[p].r + 1;
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);
t[p].u = std::min(t[lt].u, t[rt].u);
return;
}
int ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].u;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1, res = inf;
if (l <= mid)
res = ask(lt, l, r);
if (r > mid)
res = std::min(res, ask(rt, l, r));
return res;
}
#undef lt
#undef rt
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);
#endif
int n, q;
std::cin >> n;
std::vector<int> a(n + 1), la(lim + 1), pre(n + 1), f(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
pre[i] = la[a[i]], la[a[i]] = i, f[i] = i;
}
std::cin >> q;
std::vector<int> res(q + 1);
std::vector<std::vector<std::pair<int, int> > > t(n + 1);
for (int i = 1, l, r; i <= q; ++i) {
std::cin >> l >> r;
t[r].emplace_back(l, i);
}
bld(1, 1, n);
std::function<int(int)> find = [&](int x) {
return x == f[x] ? x : f[x] = find(f[x]);
};
auto merge = [&](int x, int y) {
x = find(x), y = find(y);
f[std::min(x, y)] = std::max(x, y);
return;
};
for (int r = 1; r <= n; ++r) {
if (pre[r])
merge(pre[r], pre[r] + 1);
upd(1, pre[r] + 1, r, r);
for (auto [l, i] : t[r])
res[i] = ask(1, l, find(l));
}
for (int i = 1; i <= q; ++i)
std::cout << res[i] << '\n';
return 0;
}