TIOJ 2202：King Game
TIOJ 2202：King Game
題目大意：給你兩個大小為 $n$ 的陣列 $a_1\sim a_n,w_1\sim w_n$，有 $q$ 筆獨立的詢問，每次給你 $l, r, x, y$，將 $a_i$ 改變的花費為 $w_i$，問你最少要花費多少讓 $a_l\sim a_r$ 相異數字數界在 $[x,y]$。
解法：可以分成三種 $\text{case}$，令 $\text{tot}$ 為 $[l, r]$ 相異數字數，第一種是 $x\leq\text{tot}\leq y$，那答案就是 $0$，第二種是 $\text{tot} < x$，那要增加 $x-\text{tot}$ 個新的數字，做法就是把所有種類數值中 $w$ 最大的去掉，剩下的選前 $x-\text{tot}$ 小的，第三種是 $y>\text{tot}$，那有 $y-\text{tot}$ 種數值要去掉，可以把所有數值的 $w$ 加總，然後取前 $y-\text{tot}$ 小的。
我第一個做法是莫隊 $\text{+ multiset}$ 和用 $\text{Treap}$ 維護前 $k$ 小的總和，然後就 $\text{TLE + WA}$ 了，我的第二個做法是改成用 $\text{Trie}$ 維護前 $k$ 小，$\text{multiset}$ 改用回滾莫隊，結果還是 $\text{TLE}$ 😭。
最終的做法是用分塊去記錄，這樣可以把 $\text{log}$ 壓掉，$\text{debug}$ 了一整天$\dots$。
$\text{Code：}$
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 1e5 + 5;
int n, q, sq;
ll ans[SIZE], sum[SIZE];
int a[SIZE], w[SIZE], B[SIZE];
vector<tuple<int, int, int>> op;
int q1, q2, tot, cnt[SIZE], mx[SIZE];
struct Ask {
int l, r, x, y, id;
bool operator < (const Ask& rhs) const {
return B[l] != B[rhs.l] ? l < rhs.l : r < rhs.r;
}
} ask[SIZE], ask1[SIZE], ask2[SIZE];
struct SqrtDs {
int c0[SIZE], c1[SIZE];
ll sum[SIZE];
void clear() {
memset(c0, 0, sizeof(c0));
memset(c1, 0, sizeof(c1));
memset(sum, 0, sizeof(sum));
}
void add(int val, int coef) {
if (val == 0) return;
c0[val] += coef;
c1[val / sq] += coef;
sum[val / sq] += coef > 0 ? val : -val;
}
ll que(int k) {
int p = 0;
ll re = 0;
for (; k && c1[p] <= k; p++) if (c1[p]) {
k -= c1[p];
re += sum[p];
}
for (p = sq * p; k; p++) if (c0[p]) {
int num = min(k, c0[p]);
k -= num;
re += 1ll * num * p;
}
return re;
}
} ds;
struct SqrtDs2 {
const static int BSIZ = 2500;
unordered_map<ll, int> mp;
int c1[BSIZ * BSIZ + 5], c2[BSIZ + 5];
ll sum1[BSIZ * BSIZ + 5], sum2[BSIZ + 5];
void add(ll val, int coef) {
if (val == 0) return;
mp[val] += coef;
if (mp[val] == 0) mp.erase(val);
c1[val / BSIZ] += coef;
c2[val / BSIZ / BSIZ] += coef;
sum1[val / BSIZ] += coef > 0 ? val : -val;
sum2[val / BSIZ / BSIZ] += coef > 0 ? val : -val;
}
ll que(int k) {
ll p = 0, re = 0;
for (; k && c2[p] <= k; p++) if (c2[p]) {
k -= c2[p];
re += sum2[p];
}
for (p = BSIZ * p; k && c1[p] <= k; p++) if (c1[p]) {
k -= c1[p];
re += sum1[p];
}
for (p = BSIZ * p; k; p++) if (mp.count(p)) {
int num = min(k, mp[p]);
k -= num;
re += num * p;
}
return re;
}
} ds2;
void solve() {
cin >> n >> q;
FOR (i, 1, n) cin >> a[i];
FOR (i, 1, n) cin >> w[i];
sq = sqrt(n);
FOR (i, 1, n) B[i] = (i - 1) / sq;
FOR (i, 1, q) {
auto &[l, r, x, y, id] = ask[i];
cin >> l >> r >> x >> y;
id = i;
}
sort(ask + 1, ask + q + 1, [](auto lhs, auto rhs) {
return B[lhs.l] != B[rhs.l] ? lhs.l < rhs.l : (B[lhs.l] & 1) ? lhs.r > rhs.r : lhs.r < rhs.r;
});
for (int i = 1, l = 1, r = 0; i <= q; i++) {
auto [ql, qr, x, y, id] = ask[i];
auto add = [](int i) {
tot += cnt[a[i]]++ == 0;
};
auto del = [](int i) {
tot -= --cnt[a[i]] == 0;
};
while (l > ql) add(--l);
while (r < qr) add(++r);
while (l < ql) del(l++);
while (r > qr) del(r--);
if (tot < x) ask1[++q1] = {ql, qr, x - tot, 0, id};
if (tot > y) ask2[++q2] = {ql, qr, tot - y, 0, id};
}
sort(ask1 + 1, ask1 + q1 + 1);
FOR (i, 1, q1) {
auto [l, r, x, y, id] = ask1[i];
if (B[l] == B[r]) {
vector<int> v;
FOR (j, l, r) {
if (w[j] > mx[a[j]]) {
if (mx[a[j]]) v.pb(mx[a[j]]);
mx[a[j]] = w[j];
} else {
v.pb(w[j]);
}
}
FOR (j, l, r) mx[a[j]] = 0;
x--;
nth_element(v.begin(), v.begin() + x, v.end());
FOR (j, 0, x) ans[id] += v[j];
continue;
}
int ri = i + 1, mxl = 0;
while (ri <= q1 && B[l] == B[ask1[ri].l]) ri++;
ri--;
FOR (j, i, ri) mxl = max(mxl, ask1[j].l);
auto addl = [](int i) {
if (w[i] > mx[a[i]]) {
op.pb(a[i], mx[a[i]], mx[a[i]]);
ds.add(mx[a[i]], 1);
mx[a[i]] = w[i];
} else {
op.pb(a[i], w[i], mx[a[i]]);
ds.add(w[i], 1);
}
};
auto addr = [](int i) {
if (w[i] > mx[a[i]]) {
ds.add(mx[a[i]], 1);
mx[a[i]] = w[i];
} else {
ds.add(w[i], 1);
}
};
auto rollback = []() {
reverse(op.begin(), op.end());
for (auto [x, val, ori] : op) {
ds.add(val, -1);
mx[x] = ori;
}
op.clear();
};
int rp = mxl - 1;
FOR (j, i, ri) {
auto [l, r, x, y, id] = ask1[j];
while (rp < r) addr(++rp);
FOR (k, l, mxl - 1) addl(k);
ans[id] = ds.que(x);
rollback();
}
FOR (j, mxl, rp) mx[a[j]] = 0;
ds.clear();
i = ri;
}
for (int i = 1, l = 1, r = 0; i <= q2; i++) {
auto [ql, qr, x, y, id] = ask2[i];
auto add = [](int i) {
ds2.add(sum[a[i]], -1);
sum[a[i]] += w[i];
ds2.add(sum[a[i]], 1);
};
auto del = [](int i) {
ds2.add(sum[a[i]], -1);
sum[a[i]] -= w[i];
ds2.add(sum[a[i]], 1);
};
while (l > ql) add(--l);
while (r < qr) add(++r);
while (l < ql) del(l++);
while (r > qr) del(r--);
ans[id] = ds2.que(x);
}
FOR (i, 1, q) cout << ans[i] << '\n';
}
int main() {
Waimai;
solve();
}我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！
留言
張貼留言