T2
洛谷 P2839 Middle
对于中位数，考虑二分，将数据中大于等于该数的标为 \(1\)，小于的标为 \(0\)，求和大于（等于）\(0\)则合法，否则非法。对于这个题，每次询问可以发现 \([b, c]\) 必选，前后两端不必全选。因此考虑前后两端的最大后 / 前缀和。接下来考虑如何快速标记。注意到当二分的数每次增加 \(1\) 时，只有一种数的权值会变化。于是对值域建主席树，每次查询在对应的树上查即可。
代码
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int n, q;
int a[200005];
int d[200005], dcnt;
int rt[200005];
pair<int, int> p[200005];
struct node {
int l, r, s, lmx, rmx;
} T[10000005];
node operator+(node a, node b) {
node ret;
ret.s = a.s + b.s;
ret.lmx = max(a.lmx, a.s + b.lmx);
ret.rmx = max(b.rmx, b.s + a.rmx);
ret.l = ret.r = 0;
return ret;
}
struct Segment_Tree {
int ncnt;
void pushup(int o) {
T[o].s = T[T[o].l].s + T[T[o].r].s;
T[o].lmx = max(T[T[o].l].lmx, T[T[o].l].s + T[T[o].r].lmx);
T[o].rmx = max(T[T[o].r].rmx, T[T[o].r].s + T[T[o].l].rmx);
}
void Build(int& o, int l, int r) {
o = ++ncnt;
if (l == r) {
T[o].s = T[o].lmx = T[o].rmx = -1;
return;
}
int mid = (l + r) >> 1;
Build(T[o].l, l, mid);
Build(T[o].r, mid + 1, r);
pushup(o);
// cout << o << " " << l << " " << r << " " << T[o].s << " " << T[o].lmx << " " << T[o].rmx << "\n";
}
void Insert(int& p, int q, int l, int r, int x) {
p = ++ncnt;
T[p] = T[q];
if (l == r) {
T[p].s = T[p].lmx = T[p].rmx = 1;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
Insert(T[p].l, T[q].l, l, mid, x);
else
Insert(T[p].r, T[q].r, mid + 1, r, x);
pushup(p);
}
node Query(int o, int l, int r, int L, int R) {
if (L > R)
return (node) { 0, 0, 0, 0, 0 };
if (L <= l && r <= R)
return T[o];
int mid = (l + r) >> 1;
if (R <= mid)
return Query(T[o].l, l, mid, L, R);
if (L > mid)
return Query(T[o].r, mid + 1, r, L, R);
return Query(T[o].l, l, mid, L, R) + Query(T[o].r, mid + 1, r, L, R);
}
} seg;
int vrt[200005];
map<int, int> mp;
bool chk(int k, int a, int b, int c, int d) {
// cout << k << " " << vrt[k] << "\n";
int s = seg.Query(vrt[k], 1, n, b + 1, c - 1).s;
int l = seg.Query(vrt[k], 1, n, a, b).rmx;
int r = seg.Query(vrt[k], 1, n, c, d).lmx;
// cout << s << " " << l << " " << r << "\n";
return s + l + r >= 0;
}
int _mp[200005];
int pp;
int Answer(int a, int b, int c, int d) {
// cout << a << " " << b << " " << c << " " << d << "\n";
if (b == c) {
if (a == b) {
if (c == d)
return _mp[::a[a]];
else
return max(_mp[::a[a]], Answer(a, a, c + 1, d));
} else
return max(Answer(a, b - 1, c, d), Answer(b, b, c, d));
}
int l = 1, r = dcnt, mid, ans = -1;
while (l <= r) {
mid = (l + r) >> 1;
if (chk(mid, a, b, c, d))
ans = mid, l = mid + 1;
else
r = mid - 1;
}
return _mp[ans];
}
int main() {
freopen("middle.in", "r", stdin);
freopen("middle.out", "w", stdout);
cin >> n >> pp;
for (int i = 1; i <= n; i++) cin >> a[i], d[i] = a[i];
sort(d + 1, d + n + 1);
d[0] = -1;
for (int i = 1; i <= n; i++) (d[i] != d[i - 1]) ? (_mp[mp[d[i]] = mp[d[i - 1]] + 1] = d[i]) : 0;
dcnt = mp[d[n]];
for (int i = 1; i <= n; i++) p[i] = make_pair(a[i] = mp[a[i]], i);
// for (int i = 1; i <= n; i++) cout << a[i] << " ";
// cout << "\n";
sort(p + 1, p + n + 1);
seg.Build(rt[n + 1], 1, n);
for (int i = n; i; i--) {
seg.Insert(rt[i], rt[i + 1], 1, n, p[i].second);
// cout << p[i].second << " " << rt[i] << " " << T[rt[i]].s << " " << T[rt[i]].lmx << " " << T[rt[i]].rmx << "\n";
if (p[i].first != p[i - 1].first)
vrt[p[i].first] = rt[i];
}
cin >> q;
int lans = 0;
while (q--) {
int tmp[4];
cin >> tmp[0] >> tmp[1] >> tmp[2] >> tmp[3];
tmp[0] = (tmp[0] + pp * lans) % n + 1;
tmp[1] = (tmp[1] + pp * lans) % n + 1;
tmp[2] = (tmp[2] + pp * lans) % n + 1;
tmp[3] = (tmp[3] + pp * lans) % n + 1;
sort(tmp, tmp + 4);
cout << (lans = Answer(tmp[0], tmp[1], tmp[2], tmp[3])) << "\n";
}
return 0;
}
T6
洛谷 P2824 排序
考虑二分答案，把所有大于等于当前数的都变成 \(1\)，小于的变成 \(0\)，然后就变成了 \(01\) 序列区间排序。只需要每次统计区间 \(1\) 的个数然后区间推平即可。由于 \(x\) 单增时 \([x \ge a_p]\) 这个东西是单不降的，所以可以二分。
代码
#include <iostream>
using namespace std;
int n, m;
int p[1000005], l[1000005], r[1000005], t[1000005];
struct Segment_Tree {
int s[4000005], tg[4000005];
void Build(int o, int l, int r) {
s[o] = 0, tg[o] = -1;
if (l == r)
return;
int mid = (l + r) >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
}
void tag(int o, int l, int r, int t) {
s[o] = t * (r - l + 1);
tg[o] = t;
}
void pushdown(int o, int l, int r) {
if (tg[o] == -1)
return;
int mid = (l + r) >> 1;
tag(o << 1, l, mid, tg[o]);
tag(o << 1 | 1, mid + 1, r, tg[o]);
tg[o] = -1;
}
void Cover(int o, int l, int r, int L, int R, int v) {
if (L > R)
return;
if (L <= l && r <= R) {
tag(o, l, r, v);
return;
}
pushdown(o, l, r);
int mid = (l + r) >> 1;
if (L <= mid)
Cover(o << 1, l, mid, L, R, v);
if (R > mid)
Cover(o << 1 | 1, mid + 1, r, L, R, v);
s[o] = s[o << 1] + s[o << 1 | 1];
}
int Query(int o, int l, int r, int L, int R) {
if (L <= l && r <= R)
return s[o];
pushdown(o, l, r);
int mid = (l + r) >> 1, ret = 0;
if (L <= mid)
ret += Query(o << 1, l, mid, L, R);
if (R > mid)
ret += Query(o << 1 | 1, mid + 1, r, L, R);
return ret;
}
} seg;
int q;
bool chk(int k) {
seg.Build(1, 1, n);
for (int i = 1; i <= n; i++) seg.Cover(1, 1, n, i, i, p[i] >= k);
for (int i = 1; i <= m; i++) {
int s = seg.Query(1, 1, n, l[i], r[i]);
if (t[i]) {
seg.Cover(1, 1, n, l[i], l[i] + s - 1, 1);
seg.Cover(1, 1, n, l[i] + s, r[i], 0);
} else {
seg.Cover(1, 1, n, l[i], r[i] - s, 0);
seg.Cover(1, 1, n, r[i] - s + 1, r[i], 1);
}
}
return seg.Query(1, 1, n, q, q);
}
int main() {
int tc;
cin >> tc;
while (tc--) {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 1; i <= m; i++) cin >> t[i] >> l[i] >> r[i];
cin >> q;
int l = 1, r = n, mid, ans = -1;
while (l <= r) {
mid = (l + r) >> 1;
if (chk(mid))
ans = mid, l = mid + 1;
else
r = mid - 1;
}
cout << ans << "\n";
}
return 0;
}
T7
CF1523G Try Booking
先不考虑长度限制，我们考虑类似分治的东西，设 \(calc(l, r)\) 表示 \([l, r]\) 中会租出多少，则每次只需要找编号最小的一次尝试使得该尝试被 \([l, r]\) 完全包含，然后由于左右是独立的，可以直接分治下去。然后考虑倒序枚举区间长度，相当于每次加入一个区间，要支持二维最小值查询。直接上树套树维护即可。对每个长度都做一遍，由于每次做的最多次数是 \(\frac{n}{x}\)，总次数是调和级数的，再乘上树套树的两个 \(\log\)，可以通过。
代码
#include <iostream>
#include <algorithm>
#define lowbit(x) ((x) & (-(x)))
using namespace std;
const int inf = 1000000000;
int n, m;
struct P {
int l, r, id;
} a[100005];
int ans[100005];
struct node {
int l, r, mn;
} T[10000005];
struct Segment_Tree {
int rt, ncnt;
void Add(int& o, int l, int r, int x, int y) {
if (!o) {
// cout << l << " " << r << " " << x << " new\n";
T[o = ++ncnt].mn = inf;
}
if (l == r) {
// cout << l << " " << r << " " << y << " l r y\n";
T[o].mn = min(T[o].mn, y);
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
Add(T[o].l, l, mid, x, y);
else
Add(T[o].r, mid + 1, r, x, y);
T[o].mn = min(T[T[o].l].mn, T[T[o].r].mn);
}
int Query(int o, int l, int r, int L, int R) {
if (!o)
return inf;
if (L <= l && r <= R) {
// cout << l << " " << r << " " << T[o].mn << "\n";
return T[o].mn;
}
int mid = (l + r) >> 1;
int ret = inf;
if (L <= mid)
ret = min(ret, Query(T[o].l, l, mid, L, R));
if (R > mid)
ret = min(ret, Query(T[o].r, mid + 1, r, L, R));
// cout << l << " " << r << " " << ret << " ret\n";
return ret;
}
} seg;
struct BIT {
int bit[100005];
void add(P x) { for (; x.r <= 100000; x.r += lowbit(x.r)) seg.Add(bit[x.r], 1, 100000, x.l, x.id); }
int query(int l, int r) {
int ret = inf;
// cout << l << " " << r << " query ";
for (; r; r -= lowbit(r)) ret = min(ret, seg.Query(bit[r], 1, 100000, l, 100000));
// cout << ret << "\n";
return ret;
}
} bit;
int p[100005];
int calc(int l, int r, int x) {
if (l > r)
return 0;
int cur = bit.query(l, r);
if (cur >= inf)
return 0;
// cout << l << " " << r <<"\n";
// cout << cur << " cur\n";
cur = p[cur];
// cout << cur << " cur\n";
return calc(l, a[cur].l - 1, x) + a[cur].r - a[cur].l + 1 + calc(a[cur].r + 1, r, x);
}
int main() {
T[0].mn = inf;
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> a[i].l >> a[i].r, a[i].id = i;
sort(a + 1, a + m + 1, [](P a, P b) { return a.r - a.l + 1 > b.r - b.l + 1; });
for (int i = 1; i <= m; i++) p[a[i].id] = i;
for (int i = n, j = 1; i; i--) {
// cout << i <<"\n";
while (j <= m && a[j].r - a[j].l + 1 >= i) bit.add(a[j]), ++j;
ans[i] = calc(1, n, i);
// if (i == n - 1)
// return 0;
}
for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
return 0;
}
T8
Partially Free Meal
按 \(b\) 排序，枚举选的最大的 \(b_i\)，相当于一个查询前 \(k\) 大和的东西。注意到当个数增加时，最优的 \(b_i\) 具有单调性，于是直接分治，需要支持任意前缀中前 \(k\) 大和，主席树维护即可。
代码
#include <iostream>
#include <algorithm>
#include <map>
#define int long long
using namespace std;
int n;
pair<int, int> a[200005];
int d[200005], dcnt;
int _mp[200005];
int rt[200005];
struct node {
int l, r, s, S;
} T[10000005];
struct Persistent_Segment_Tree {
int ncnt;
void Insert(int& p, int q, int l, int r, int x) {
p = ++ncnt;
T[p] = T[q];
T[p].s++;
T[p].S += _mp[x];
if (l == r)
return;
int mid = (l + r) >> 1;
if (x <= mid)
Insert(T[p].l, T[q].l, l, mid, x);
else
Insert(T[p].r, T[q].r, mid + 1, r, x);
}
int Query(int p, int l, int r, int k) {
if (l == r)
return _mp[l] * k;
int mid = (l + r) >> 1;
if (T[T[p].l].s >= k)
return Query(T[p].l, l, mid, k);
else
return T[T[p].l].S + Query(T[p].r, mid + 1, r, k - T[T[p].l].s);
}
} seg;
int ans[200005];
void Solve(int l, int r, int ql, int qr) {
if (l > r)
return;
// cout << l << " " << r << "\n";
int mid = (l + r) >> 1;
int k = ql;
ans[mid] = 3000000000000000;
for (int i = max(ql, mid); i <= qr; i++) {
int tmp = seg.Query(rt[i - 1], 1, dcnt, mid - 1) + _mp[a[i].first] + a[i].second;
// cout << i - 1 << " " << tmp << " " << mid - 1 << " s\n";
// int tmp = 0;
if (tmp < ans[mid])
ans[mid] = tmp, k = i;
}
// cout << mid << " " << k << " k\n";
Solve(l, mid - 1, ql, k);
Solve(mid + 1, r, k, qr);
}
map<int, int> mp;
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].second >> a[i].first, d[i] = a[i].second;
sort(d + 1, d + n + 1);
for (int i = 1; i <= n; i++) d[i] != d[i - 1] ? (_mp[mp[d[i]] = mp[d[i - 1]] + 1] = d[i]) : 0;
dcnt = mp[d[n]];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
swap(a[i].first, a[i].second);
// cout << a[i].first << " " << a[i].second << "\n";
a[i].first = mp[a[i].first];
seg.Insert(rt[i], rt[i - 1], 1, dcnt, a[i].first);
}
Solve(1, n, 1, n);
for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
return 0;
}