526互联

AtCoder Regular Contest 168 F Up-Down Queries

发布时间 2023-12-27 18:03:18作者: zltzlt

洛谷传送门

AtCoder 传送门

貌似是第三道问号题？感觉前面这个转化不是人能想到的。。。

考虑维护 \(y\) 的差分序列。更进一步地，我们类比 slope trick，维护一个可重集，里面有 \(y_{i + 1} - y_i\) 个 \(i\)（为了方便我们让每次操作时 \(y_{m + 1}\) 加 \(1\)）。那么一次操作就相当于，插入两个 \(a_i\)，删去最小值。

考虑统计答案。如果不考虑 \(\max\) 操作就是 \(\sum\limits_{i = 1}^n m - 2a_i\)。考虑 \(\max\) 操作，相当于每次有最小值个数避免了减 \(1\)。所以答案每次再加上最小值。

于是求 \(f(a)\) 可以转化为：从左往右遍历 \(a\)，往可重集中加入 \(2\) 个 \(a_i\)，把此时可重集的最小值累加进答案，再删除最小值。

考虑倒着操作，转化为从右往左遍历 \(a\)，往可重集中加入 \(2\) 个 \(a_i\)，删除可重集中的最大值。最后可重集中的数的和就是答案。

这样就转化成了一个比较标准的 P9168 [省选联考 2023] 人员调度 的链的问题了。简单讲一下这个问题的做法。

考虑初始时一个数也没有，然后我们在一些位置加数。加数的同时维护最后还在可重集中的数。

设当前要加的数的位置是 \(u\)，数值是 \(x\)。我们找到 \(u\) 的祖先即 \([1, u]\) 中最后一个满的位置 \(v\)（一个点 \(v\) 满了指 \(v\) 的子树即 \([v, n]\) 中数的个数 \(= sz_v = n - v + 1\)）。

如果 \(v\) 不存在我们放心把这个数加入即可，因为不会造成 pop。

否则，我们找到 \(v\) 的子树中的最大值，设其权值为 \(w\)。

若 \(x > w\)，那么 \(x\) 加入后在 \(v\) 位置一定会被 pop，所以不用加入。

否则，因为 \(w\) 不会被 pop，所以 \(x\) 也不会被 pop。于是我们直接用 \(x\) 替换 \(w\) 即可。

实现时需要一棵线段树维护每个位置的 \(sz\) 减去其子树内数的个数，一棵线段树维护子树中所有数的最大值，配合 \(n\) 个可重集维护每个点上的数。

时间复杂度 \(O(n \log^2 n)\)，需要卡常。卡常主要两点，第一棵线段树不要用 pair 维护最小值及其位置，改成线段树上二分；注意到可重集中至多两个元素，所以可以手写。

卡常前的代码 
// Problem: F - Up-Down Queries
// Contest: AtCoder - ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168）
// URL: https://atcoder.jp/contests/arc168/tasks/arc168_f
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 500100;
const int inf = 0x3f3f3f3f;

int n, m, q, b[maxn], tot, c[maxn];
ll ans[maxn], res;
vector<int> vc[maxn << 2];
multiset<pii> S[maxn];

struct node {
	int x, y;
	node(int a = 0, int b = 0) : x(a), y(b) {}
} a[maxn];

void update(int rt, int l, int r, int ql, int qr, int x) {
	if (ql > qr) {
		return;
	}
	if (ql <= l && r <= qr) {
		vc[rt].pb(x);
		vc[rt].pb(x);
		return;
	}
	int mid = (l + r) >> 1;
	if (ql <= mid) {
		update(rt << 1, l, mid, ql, qr, x);
	}
	if (qr > mid) {
		update(rt << 1 | 1, mid + 1, r, ql, qr, x);
	}
}

struct {
	pii a[maxn << 2];
	int tag[maxn << 2];
	
	inline pii get(pii a, pii b) {
		return (a.fst < b.fst || (a.fst == b.fst && a.scd > b.scd)) ? a : b;
	}
	
	inline void pushup(int x) {
		a[x] = get(a[x << 1], a[x << 1 | 1]);
	}
	
	inline void pushdown(int x) {
		if (!tag[x]) {
			return;
		}
		a[x << 1].fst += tag[x];
		a[x << 1 | 1].fst += tag[x];
		tag[x << 1] += tag[x];
		tag[x << 1 | 1] += tag[x];
		tag[x] = 0;
	}
	
	void build(int rt, int l, int r) {
		if (l == r) {
			a[rt] = mkp(n - l + 1, l);
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
		pushup(rt);
	}
	
	void update(int rt, int l, int r, int ql, int qr, int x) {
		if (ql <= l && r <= qr) {
			a[rt].fst += x;
			tag[rt] += x;
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	pii query(int rt, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return a[rt];
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		pii res = mkp(inf, 0);
		if (ql <= mid) {
			res = get(res, query(rt << 1, l, mid, ql, qr));
		}
		if (qr > mid) {
			res = get(res, query(rt << 1 | 1, mid + 1, r, ql, qr));
		}
		return res;
	}
} t1;

struct {
	pii a[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = max(a[x << 1], a[x << 1 | 1]);
	}
	
	void build(int rt, int l, int r) {
		a[rt].fst = -inf;
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
	}
	
	void update(int rt, int l, int r, int x, pii y) {
		if (l == r) {
			a[rt] = y;
			return;
		}
		int mid = (l + r) >> 1;
		(x <= mid) ? update(rt << 1, l, mid, x, y) : update(rt << 1 | 1, mid + 1, r, x, y);
		pushup(rt);
	}
	
	pii query(int rt, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return a[rt];
		}
		int mid = (l + r) >> 1;
		pii res = mkp(-inf, 0);
		if (ql <= mid) {
			res = max(res, query(rt << 1, l, mid, ql, qr));
		}
		if (qr > mid) {
			res = max(res, query(rt << 1 | 1, mid + 1, r, ql, qr));
		}
		return res;
	}
} t2;

void dfs(int rt, int l, int r) {
	vector<pii> v1, v2;
	ll lstres = res;
	for (int i : vc[rt]) {
		int u = a[i].x, x = a[i].y;
		pii p = t1.query(1, 1, n, 1, u);
		// printf("u, x: %d %d\n", u, x);
		if (p.fst) {
			// printf("%d %d\n", u, x);
			v1.pb(u, -1);
			v2.pb(i, 1);
			t1.update(1, 1, n, 1, u, -1);
			S[u].emplace(x, i);
			res += x;
			t2.update(1, 1, n, u, *(--S[u].end()));
			continue;
		}
		int v = p.scd;
		// printf("v: %d\n", v);
		p = t2.query(1, 1, n, v, n);
		int w = p.scd;
		if (x < a[w].y) {
			// printf("%d -%d\n", x, a[w].y);
			res += x - a[w].y;
			t1.update(1, 1, n, 1, u, -1);
			t1.update(1, 1, n, 1, a[w].x, 1);
			v1.pb(u, -1);
			v1.pb(a[w].x, 1);
			S[a[w].x].erase(S[a[w].x].find(mkp(a[w].y, w)));
			t2.update(1, 1, n, a[w].x, *(--S[a[w].x].end()));
			S[u].emplace(x, i);
			t2.update(1, 1, n, u, *(--S[u].end()));
			v2.pb(w, 0);
			v2.pb(i, 1);
		}
	}
	if (l == r) {
		// printf("res: %lld\n", res);
		ans[l] += res;
	} else {
		int mid = (l + r) >> 1;
		dfs(rt << 1, l, mid);
		dfs(rt << 1 | 1, mid + 1, r);
	}
	res = lstres;
	reverse(v1.begin(), v1.end());
	reverse(v2.begin(), v2.end());
	for (pii p : v1) {
		t1.update(1, 1, n, 1, p.fst, -p.scd);
	}
	for (pii p : v2) {
		int i = p.fst;
		if (p.scd) {
			S[a[i].x].erase(S[a[i].x].find(mkp(a[i].y, i)));
		} else {
			S[a[i].x].emplace(a[i].y, i);
		}
		t2.update(1, 1, n, a[i].x, *(--S[a[i].x].end()));
	}
}

void solve() {
	scanf("%d%d%d", &n, &m, &q);
	ll s = 0;
	for (int i = 1; i <= n; ++i) {
		b[i] = i;
		a[i].x = i;
		S[i].emplace(-inf, 0);
		scanf("%d", &a[i].y);
		s += m - a[i].y * 2;
	}
	tot = n;
	for (int i = 1, x, y; i <= q; ++i) {
		scanf("%d%d", &x, &y);
		s -= m - a[b[x]].y * 2;
		update(1, 1, q, max(c[x], 1), i - 1, b[x]);
		c[x] = i;
		a[++tot] = node(x, y);
		b[x] = tot;
		s += m - a[b[x]].y * 2;
		ans[i] = s;
	}
	for (int i = 1; i <= n; ++i) {
		update(1, 1, q, max(c[i], 1), q, b[i]);
	}
	t1.build(1, 1, n);
	t2.build(1, 1, n);
	dfs(1, 1, q);
	for (int i = 1; i <= q; ++i) {
		printf("%lld\n", ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}
卡常后的代码 
// Problem: F - Up-Down Queries
// Contest: AtCoder - ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168）
// URL: https://atcoder.jp/contests/arc168/tasks/arc168_f
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

namespace IO {
    char ibuf[1 << 20], *iS, *iT, obuf[1 << 20], *oS = obuf;
#define writesp(x) write(x), pc(' ')
#define writeln(x) write(x), pc('\n')
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, 1 << 20, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
	template<typename T = int>
    inline T read() {
        char ch = gh();
        T x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    inline void flush () {
    	fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
	}
    inline void pc (char ch) {
    	if (oS == obuf + (1 << 20)) flush(); 
    	*oS++ = ch;
	}
	template<typename _Tp>
    inline void write (_Tp x) {
    	static char stk[64], *tp = stk;
    	if (x < 0) x = ~(x - 1), pc('-');
		do *tp++ = x % 10, x /= 10;
		while (x);
		while (tp != stk) pc((*--tp) | 48);
    }
}

using IO::read;
using IO::write;
using IO::pc;
using IO::flush;

const int maxn = 500100;
const int inf = 0x3f3f3f3f;

int n, m, q, b[maxn], tot, c[maxn];
ll ans[maxn], res;
vector<int> vc[maxn << 2];
db tim;

struct {
	pii x, y;
	
	inline void init() {
		x = y = mkp(-inf, 0);
	}
	
	inline void insert(pii p) {
		(x.fst == -inf) ? (x = p) : (y = p);
	}
	
	inline void erase(pii p) {
		(x == p ? x : y) = mkp(-inf, 0);
	}
	
	inline pii query() {
		return max(x, y);
	}
} S[maxn];

struct node {
	int x, y;
	node(int a = 0, int b = 0) : x(a), y(b) {}
} a[maxn];

void update(int rt, int l, int r, int ql, int qr, int x) {
	if (ql > qr) {
		return;
	}
	if (ql <= l && r <= qr) {
		vc[rt].pb(x);
		vc[rt].pb(x);
		return;
	}
	int mid = (l + r) >> 1;
	if (ql <= mid) {
		update(rt << 1, l, mid, ql, qr, x);
	}
	if (qr > mid) {
		update(rt << 1 | 1, mid + 1, r, ql, qr, x);
	}
}

struct {
	int a[maxn << 2], tag[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = min(a[x << 1], a[x << 1 | 1]);
	}
	
	inline void pushdown(int x) {
		if (!tag[x]) {
			return;
		}
		a[x << 1] += tag[x];
		a[x << 1 | 1] += tag[x];
		tag[x << 1] += tag[x];
		tag[x << 1 | 1] += tag[x];
		tag[x] = 0;
	}
	
	void build(int rt, int l, int r) {
		if (l == r) {
			a[rt] = n - l + 1;
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
		pushup(rt);
	}
	
	void update(int rt, int l, int r, int ql, int qr, int x) {
		if (ql <= l && r <= qr) {
			a[rt] += x;
			tag[rt] += x;
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	inline int find(int rt, int l, int r) {
		while (l != r) {
			pushdown(rt);
			int mid = (l + r) >> 1;
			(a[rt << 1 | 1] == 0) ? (rt = rt << 1 | 1, l = mid + 1) : (rt <<= 1, r = mid);
		}
		return l;
	}
	
	int find(int rt, int l, int r, int ql, int qr) {
		if (a[rt] > 0) {
			return -1;
		}
		if (ql <= l && r <= qr) {
			return find(rt, l, r);
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		if (qr > mid) {
			int t = find(rt << 1 | 1, mid + 1, r, ql, qr);
			if (t != -1) {
				return t;
			}
		}
		if (ql <= mid) {
			int t = find(rt << 1, l, mid, ql, qr);
			if (t != -1) {
				return t;
			}
		}
		return -1;
	}
} t1;

struct {
	pii a[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = max(a[x << 1], a[x << 1 | 1]);
	}
	
	void build(int rt, int l, int r) {
		a[rt].fst = -inf;
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
	}
	
	void update(int rt, int l, int r, int x, pii y) {
		if (l == r) {
			a[rt] = y;
			return;
		}
		int mid = (l + r) >> 1;
		(x <= mid) ? update(rt << 1, l, mid, x, y) : update(rt << 1 | 1, mid + 1, r, x, y);
		pushup(rt);
	}
	
	inline void upd(int x, pii y) {
		int rt = 1, l = 1, r = n;
		while (1) {
			a[rt] = max(a[rt], y);
			if (l == r) {
				return;
			}
			int mid = (l + r) >> 1;
			(x <= mid) ? (rt <<= 1, r = mid) : (rt = rt << 1 | 1, l = mid + 1);
		}
	}
	
	inline pii query(int x) {
		int rt = 1, l = 1, r = n;
		pii res = mkp(-inf, 0);
		while (1) {
			if (x <= l) {
				return max(res, a[rt]);
			}
			int mid = (l + r) >> 1;
			if (x <= mid) {
				res = max(res, a[rt << 1 | 1]);
				rt = rt << 1;
				r = mid;
			} else {
				rt = rt << 1 | 1;
				l = mid + 1;
			}
		}
	}
} t2;

void dfs(int rt, int l, int r) {
	vector<pii> v1, v2;
	ll lstres = res;
	for (int i : vc[rt]) {
		int u = a[i].x, x = a[i].y;
		int v = t1.find(1, 1, n, 1, u);
		// printf("u, x: %d %d\n", u, x);
		if (v == -1) {
			// printf("%d %d\n", u, x);
			v1.pb(u, -1);
			v2.pb(i, 1);
			t1.update(1, 1, n, 1, u, -1);
			pii t = S[u].query();
			S[u].insert(mkp(x, i));
			res += x;
			if (S[u].query() != t) {
				t2.update(1, 1, n, u, S[u].query());
			}
			continue;
		}
		pii p = t2.query(v);
		int w = p.scd;
		if (x < a[w].y) {
			// printf("%d -%d\n", x, a[w].y);
			res += x - a[w].y;
			t1.update(1, 1, n, 1, u, -1);
			t1.update(1, 1, n, 1, a[w].x, 1);
			v1.pb(u, -1);
			v1.pb(a[w].x, 1);
			pii t = S[a[w].x].query();
			S[a[w].x].erase(mkp(a[w].y, w));
			if (S[a[w].x].query() != t) {
				t2.update(1, 1, n, a[w].x, S[a[w].x].query());
			}
			t = S[u].query();
			S[u].insert(mkp(x, i));
			if (S[u].query() != t) {
				t2.upd(u, S[u].query());
			}
			v2.pb(w, 0);
			v2.pb(i, 1);
		}
	}
	if (l == r) {
		// printf("res: %lld\n", res);
		ans[l] += res;
	} else {
		int mid = (l + r) >> 1;
		dfs(rt << 1, l, mid);
		dfs(rt << 1 | 1, mid + 1, r);
	}
	res = lstres;
	reverse(v1.begin(), v1.end());
	reverse(v2.begin(), v2.end());
	for (pii p : v1) {
		t1.update(1, 1, n, 1, p.fst, -p.scd);
	}
	for (pii p : v2) {
		int i = p.fst;
		pii t = S[a[i].x].query();
		if (p.scd) {
			S[a[i].x].erase(mkp(a[i].y, i));
			if (S[a[i].x].query() != t) {
				t2.update(1, 1, n, a[i].x, S[a[i].x].query());
			}
		} else {
			S[a[i].x].insert(mkp(a[i].y, i));
			if (S[a[i].x].query() != t) {
				t2.upd(a[i].x, S[a[i].x].query());
			}
		}
	}
}

void solve() {
	scanf("%d%d%d", &n, &m, &q);
	ll s = 0;
	for (int i = 1; i <= n; ++i) {
		b[i] = i;
		a[i].x = i;
		S[i].init();
		a[i].y = read();
		s += m - a[i].y * 2;
	}
	tot = n;
	for (int i = 1, x, y; i <= q; ++i) {
		x = read();
		y = read();
		s -= m - a[b[x]].y * 2;
		update(1, 1, q, max(c[x], 1), i - 1, b[x]);
		c[x] = i;
		a[++tot] = node(x, y);
		b[x] = tot;
		s += m - a[b[x]].y * 2;
		ans[i] = s;
	}
	for (int i = 1; i <= n; ++i) {
		update(1, 1, q, max(c[i], 1), q, b[i]);
	}
	t1.build(1, 1, n);
	t2.build(1, 1, n);
	dfs(1, 1, q);
	fprintf(stderr, "tim: %.5lf\n", tim);
	for (int i = 1; i <= q; ++i) {
		writeln(ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	flush();
	return 0;
}