The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online (The 2nd Universal Cup. Stage 1: Qingdao)
J - Press the Button
\(1 \leq a, b, c, d \leq 10^6\)
题解
- 容易发现存在循环节，每次位于\(gcd(a, c)\)的倍数的位置
- 所以我们考虑处理一个循环节内的情况
- 如果\(v \leq min(a, c)\)：我们考虑暴力处理一个循环节中的答案
- 如果\(v > min(a, c)\)：说明一旦灯亮起来就不会熄灭，特判第一次亮灯时的情况即可
int a, b, c, d, v, t, n;
void solve(){
cin >> a >> b >> c >> d >> v >> t;
if(v >= min(a, c)){
cout << (t/a) * b + (t/c) * d + b + d - 1 << endl;
return;
}
if(a > c){
swap(a, c);
swap(b, d);
}
int cur = a, cnt = b + d - 1;
n = (a * c) / __gcd(a, c);
while(cur < n){
int last = cur - (cur % c);
cnt += b - 1;
if(last > cur - a && last < cur){
cnt += d - 1;
if(cur - last <= v) cnt++;
if(last - (cur - a) <= v) cnt++;
}
cur += a;
}
int ans = (t / n) * cnt;
n = t % n;
cnt = b + d - 1;
cur = a;
// cerr << n << ' ' << cur << endl;
while(cur <= n){
int last = cur - (cur % c);
cnt += b - 1;
if(last > cur - a && last < cur){
cnt += d - 1;
if(cur - last <= v) cnt++;
if(last - (cur - a) <= v) cnt++;
}
// cerr << cur << ' ' << cnt << endl;
cur += a;
}
if(cur - a < n){
int last = cur - (cur % c);
if(last > cur - a && last <= n){
cnt += d - 1;
if(last - (cur - a) <= v) cnt++;
}
}
ans += cnt;
cout << ans << endl;
}
B - Red Black Tree
给定一颗有\(n\)个点的树，每个节点只有红色和黑色两种颜色，根节点为红色，树上的每条边都有边权\(w \geq 1\)，每个节点存在点权，如果节点的颜色为红色，那么点权为\(0\)，如果节点的颜色为黑色，那么点权为其最近红色祖先之间路径的边权之和
存在\(q\)个询问，每次询问给定\(k\)个节点，要求最多将树上最多一个节点变为红色节点，使得最小化\(k\)个节点中点权的最大值
保证\(\sum k \leq 2e6\)
题解
\[\begin{equation} \left\{ \begin{array}{lr} max(dis[v_1], dis[v_2], ... , dis[v_{i - 1}]) - dis[lca] \\ cost[v_i] \end{array} \right. \end{equation} \]
显然我们可以通过\(dfs\)计算出每个节点的点权，定义其为\(cost[u]\)
那么对于\(k\)个节点来说，我们不妨将\(k\)个节点按照点权降序排列，那么\(v_1\)就是当前未修改前的最大值
我们考虑枚举\(v_i\)成为答案，那么我们需要减小\(v_1, v_2,...,v_{i - 1}\)这些节点的点权，显然修改的最优策略一定是将\(v_1, v_2, ... ,v_{i - 1}\)的\(lca\)变为红色节点，我们定义\(dis[v]\)为\(v\)到根节点的路径之和，那么答案为
- 时间复杂度：\(O(nlogn)\)
int n, m, q, dis[N], col[N], last[N], fa[N][20], dep[N], cost[N];
vector<pair<int, int>> g[N];
void dfs(int u, int par)
{
fa[u][0] = par;
for (int i = 1; i <= 18; ++i)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
dep[u] = dep[par] + 1;
if (col[u])
last[u] = u;
else
last[u] = last[par];
cost[u] = dis[u] - dis[last[u]];
for (auto [v, w] : g[u])
{
if (v == par)
continue;
dis[v] = dis[u] + w;
dfs(v, u);
}
}
int LCA(int u, int v)
{
if (dep[u] < dep[v])
swap(u, v);
for (int i = 18; i >= 0; --i)
if (dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if (u == v)
return u;
for (int i = 18; i >= 0; --i)
if (fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
void solve()
{
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i)
g[i].clear(), col[i] = 0;
for (int i = 1; i <= m; ++i)
{
int u;
cin >> u;
col[u] = 1;
}
for (int i = 1; i < n; ++i)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 1);
while (q--)
{
int k;
cin >> k;
vector<int> node;
for (int i = 1, u; i <= k; ++i)
{
cin >> u;
node.push_back(u);
}
sort(all(node), [&](int x, int y)
{ return cost[x] > cost[y]; });
int ans = cost[node.front()];
int lca = node.front();
int mx = dis[node.front()];
for (int i = 0; i < k - 1; ++i)
{
if (!i)
ans = min(ans, max(mx - dis[lca], cost[node[i + 1]]));
else
{
lca = LCA(lca, node[i]);
mx = max(mx, dis[node[i]]);
ans = min(ans, max(mx - dis[lca], cost[node[i + 1]]));
}
}
lca = LCA(lca, node.back());
mx = max(mx, dis[node.back()]);
ans = min(ans, mx - dis[lca]);
cout << ans << endl;
}
}
G - Couleur
给定一个长度为\(n\)的序列\(a\)，一共\(n\)次操作，每次操作删除一个元素，使得序列\(a\)的某个区间分裂成两个区间，对于每个操作求出所有区间中最大的逆序对数
要求：强制在线
题解：启发式分裂 + 主席树
我们考虑用\(map\)来维护每段区间的逆序对数，\(mp[i]\)代表区间左端点为\(i + 1\)的区间中逆序对的数量
对于每次分裂区间的操作，我们定义区间为\([l,r]\)，分裂点\(x,l \leq x \leq r\)，\(rev(l,r)\)代表区间\([l,r]\)中的逆序对数量：
如果\(x - l < r - x\)，即分裂之后右边区间的元素多，则：
rev(x + 1, r) = rev(l, r) - rev(l, x - 1) - 一个元素在[l, x - 1]， 一个元素在[x + 1, r] 中的逆序对数量 - 元素 a[x] 产生的逆序对数量对于\(rev(l,x - 1)\)这一部分答案，我们暴力即可，所以我们需要一个数据结构支持这样一种操作：询问区间\([l,r]\)中数值位于\([ql, qr]\)的元素数量，显然主席树能够很好的支持这种操作，可持久化数组\(a\)即可
其他部分贡献的计算类似
如果\(x - l > r - x\)，同理
- 根据启发式分裂，每个元素最多只会被暴力遍历到\(logn\)次，所以复杂度为\(O(nlog^2n)\)
int n, a[N], p[N], rt[N], lson[M], rson[M], sum[M], idx;
map<int, int> mp;
multiset<int> st;
inline void up(int id) { sum[id] = sum[lson[id]] + sum[rson[id]]; }
void change(int &id, int pre, int l, int r, int x)
{
id = ++idx;
lson[id] = lson[pre], rson[id] = rson[pre], sum[id] = sum[pre];
if (l == r)
{
sum[id]++;
return;
}
int mid = l + r >> 1;
if (x <= mid)
change(lson[id], lson[pre], l, mid, x);
else
change(rson[id], rson[pre], mid + 1, r, x);
up(id);
}
int query(int id, int l, int r, int ql, int qr)
{
if (ql > qr)
return 0;
if (!id)
return 0;
if (ql <= l && r <= qr)
return sum[id];
int mid = l + r >> 1;
if (qr <= mid)
return query(lson[id], l, mid, ql, qr);
else if (ql > mid)
return query(rson[id], mid + 1, r, ql, qr);
else
return query(lson[id], l, mid, ql, qr) + query(rson[id], mid + 1, r, ql, qr);
}
void split(int l, int r, int x)
{
int pre_ans = mp[l];
st.erase(st.find(pre_ans));
// a[x] 在区间 [l, r] 中产生的逆序对数量
int cnt = query(rt[r - 1], 1, n, 1, a[x] - 1) - query(rt[x], 1, n, 1, a[x] - 1) + query(rt[x - 1], 1, n, a[x] + 1, n) - query(rt[l], 1, n, a[x] + 1, n);
// 左半区间元素个数少，枚举左半区间
if (x - l < r - x)
{
// lans 代表区间 [l, x - 1] 中的逆序对数量， sum 代表一个元素在 [l, x - 1] 中，一个元素在 [x + 1, r] 中的逆序对数量
int lans = 0, sum = 0;
for (int i = l + 1; i < x; ++i)
{
lans += query(rt[i - 1], 1, n, a[i] + 1, n) - query(rt[l], 1, n, a[i] + 1, n);
sum += query(rt[r - 1], 1, n, 1, a[i] - 1) - query(rt[x], 1, n, 1, a[i] - 1);
}
mp[l] = lans;
st.insert(lans);
mp[x] = pre_ans - lans - sum - cnt;
st.insert(pre_ans - lans - sum - cnt);
}
else
{
// rans 代表区间 [x + 1, r] 中的逆序对数量， sum 代表一个元素在 [l, x - 1] 中，一个元素在 [x + 1, r] 中的逆序对数量
int rans = 0, sum = 0;
for (int i = x + 1; i < r; ++i)
{
rans += query(rt[i - 1], 1, n, a[i] + 1, n) - query(rt[x], 1, n, a[i] + 1, n);
sum += query(rt[x - 1], 1, n, a[i] + 1, n) - query(rt[l], 1, n, a[i] + 1, n);
}
mp[x] = rans;
st.insert(rans);
mp[l] = pre_ans - rans - sum - cnt;
st.insert(pre_ans - rans - sum - cnt);
}
}
void solve()
{
cin >> n;
for (int i = 0; i <= idx; ++i)
lson[i] = rson[i] = sum[i] = 0;
for (int i = 0; i <= n; ++i)
rt[i] = 0;
mp.clear(), st.clear();
idx = 0;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
cin >> p[i];
for (int i = 1; i <= n; ++i)
change(rt[i], rt[i - 1], 1, n, a[i]);
int ans = 0;
for (int i = 1; i <= n; ++i)
ans += query(rt[i - 1], 1, n, a[i] + 1, n);
mp[0] = ans, mp[n + 1] = 0;
st.insert(ans), st.insert(0);
for (int i = 1; i <= n; ++i)
{
cout << ans << "\n "[i < n];
int pos = p[i] ^ ans;
auto it = mp.lower_bound(pos);
split(prev(it)->first, it->first, pos);
ans = *prev(st.end());
}
}