CF1477E Nezzar and Tournament【数据结构，贪心】

不容易发现 \(s_i=k-c_1+c_i+\max\{0,c_1-k-\min_{j\le i}\{c_j\}\}\)。

若固定了 \(c_1\)，则 \(\max\) 外面的贡献固定，只需要让 \(b_i\) 位置的前缀最小值较大，\(a_i\) 位置的前缀最小值较小。

所以应该先降序排列 \(b\)，然后再升序排列 \(a\)。

设 \(c_1=t\)，\(Min=\min\{a,b\}\)，因为前缀最小值为 \(t\) 的时候 \(\max\) 里的东西没有贡献，所以可以得到

• 对于每个 \(b_i\)，贡献为 \(-(k-t+b_i+\max\{0,t-k-b_i\})\)。
• 对于每个没有被放在 \(c_1\) 的 \(a_i\)，贡献为 \(k-t+a_i+\max\{0,t-k-Min\}\)。

所以 \(f(t)=(n-[t\in a])\max\{0,t-k-Min\}-\sum\max\{0,t-k-b_i\}+(m-n)t+C\)，其中 \(C=(n-m)k+\sum a_i-\sum b_i\) 是与 \(t\) 无关的常数。

分类讨论 \([t\in a]\) 的两种情况，然后计算最大值，可以发现这东西是严格上凸的，只需要找到斜率的符号分界处，也就是对 \(\{b\}\) 的求 \(k\) 小值和 \(\{a\},\{b\}\) 的查询前驱/后继。

因为值域比较小所以可以用树状数组维护，时间复杂度 \(O((n+m+q)\log V)\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1000003;
template<typename T>
void read(T &x){
	int ch = getchar(); x = 0;
	for(;ch < ‘0‘ || ch > ‘9‘;ch = getchar());
	for(;ch >= ‘0‘ && ch <= ‘9‘;ch = getchar()) x = x * 10 + ch - ‘0‘; 
}
template<typename T>
bool chmin(T &a, const T &b){if(a > b) return a = b, 1; return 0;}
template<typename T>
bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
int n, m, q, a[N], b[N];
LL delta;
struct BIT {
	int n, c[N]; LL s[N];
	void upd(int p, int x, int y){
		for(++ p;p < N;p += p & -p){c[p] += x; s[p] += y;}
	}
	LL qry(int p){
		if(p < 0) return 0;
		LL S = 0, C = 0, _ = p++;
		for(;p;p -= p & -p){C += c[p]; S += s[p];}
		return C * _ - S;
	}
	int rnk(int p){
		if(p < 0) return 0;
		int r = 0;
		for(p = min(p+1, N-1);p;p -= p & -p)
			r += c[p];
		return r;
	}
	int kth(int k){
		chmin(k, n); chmax(k, 1);
		int p = 0;
		for(int i = 19;~i;-- i)
			if(p+(1<<i) < N && c[p+(1<<i)] < k)
				k -= c[p += 1<<i];
		return p;
	}
	int pre(int x){return kth(rnk(x));}
	int nxt(int x){return kth(rnk(x)+1);}
} A, B;
void upda(int p, int v){
	delta += p * v;
	A.upd(p, v, p * v);
}
void updb(int p, int v){
	delta -= p * v;
	B.upd(p, v, p * v);
}
LL qrya(int k){
	int a1 = A.kth(1), b1 = B.kth(1), an = A.kth(n), bm = B.kth(m-1), Min = min(a1, b1);
	auto F = [&](int t){return (n-1ll)*max(0,t-k-Min)-B.qry(t-k)+(LL)t*(m-n);};
	return max(F(a1), max(F(an), max(F(A.pre(bm+k)), F(A.nxt(bm+k)))));
}
LL qryb(int k){
	int b1 = B.kth(1), bm = B.kth(m), Min = min(A.kth(1), b1);
	auto F = [&](int t){return (LL)n*max(0,t-k-Min)-B.qry(t-k)+(LL)t*(m-n);};
	return max(F(b1), max(F(bm), max(F(B.pre(bm+k)), F(B.nxt(bm+k)))));
}
int main(){
	read(n); read(m); read(q); A.n = n; B.n = m;
	for(int i = 1;i <= n;++ i){read(a[i]); upda(a[i], 1);}
	for(int i = 1;i <= m;++ i){read(b[i]); updb(b[i], 1);}
	while(q --){
		int op, k, y;
		read(op); read(k);
		if(op == 3) printf("%lld\n", max(qrya(k), qryb(k)) + (LL)k*(n-m) + delta);
		else { read(y);
			if(op == 1){
				upda(a[k], -1);
				upda(a[k] = y, 1);
			} else {
				updb(b[k], -1);
				updb(b[k] = y, 1);
			}
		}
	}
}

CF1477E Nezzar and Tournament【数据结构，贪心】

原文：https://www.cnblogs.com/AThousandMoons/p/14805971.html