CF1477E - Nezzar and Tournaments

Posted on Edited on In

CF1477E - Nezzar and Tournaments

题目大意

有两队人 \(a_i,i\in[1,n],b_j,j\in[1,m]\) ，现在把他们放在一起排成一行 \(c_i\)

顺次给每个人计分，初始 \(s_0=k\)

\(s_i=\max\{0,s_{i-1}+c_i-c_{\max\{i-1,1\}}\}\)

现在要最大化每个 \(a_i\) 所在位置的 \(s_i\) 之和 与 \(b_i\) 所在 \(s_i\) 之和 的差

支持修改和对于不同 \(k\) 查询


分析

考虑 \(k=0\) 简单情况

1.若 \(s_i\) 不清零，则 \(s_i=c_i-lst\) ，其中 \(lst\) 表示上一个被清零位置的 \(c_j\)

  1. \(s_i\) 清零，则 \(c_i<lst\)

容易发现， \(\displaystyle s_i=c_i-\min_{j\leq i}\{ c_j\}\)


那么对于含 \(k\) 的情况，类似可以得到

\(\displaystyle s_i=k-c_1+c_i+\max\{0,c_1-k-\min_{j\leq i}\{c_j\}\}\)

假设我们固定了一个 \(c_1\) ，现在考虑对于剩下的 \(a_i,b_j\) 排出一个最优的排列

容易发现， \(k-c_1+c_i\) 的贡献时固定的，只有前缀最小值会影响答案

我们希望对于 \(b_i\) ，前缀最小值较大， \(a_i\) 反之

那么容易发现可以先降序排列 \(b_j\) ，再正序排列 \(a_i\)

此时 \(b_{\min}\) 可以贡献给 \(a_i\) 的前缀最小值，同时 \(b_j\) 的前缀最小值能够取到最大


此时，不妨设 \(c_1=t\) ， \(\min\{a_i,b_i\}=Min\)

在 \(\min\{c_j\}=c_1\) 时， \(\max\) 里的东西没有贡献，故可以得到

1.对于每个 \(a_i\) ，若它没有被放在 \(c_1\) ，则贡献 \(k-t+a_i+\max\{0,t-k-Min\}\)

2.对于每个 \(b_i\) （不特殊考虑第一个），则贡献 \(-(k-t+b_i+\max\{0,t-k-b_i\})\) （忽略最小值为 \(t\) 的情况）

则最终式子为

\(\displaystyle f(t)=(n-[t\in a_i])\cdot \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\)

容易发现 \(f(t)\) 是关于 \(t\) 的分段一次函数，根据斜率变化情况分析，极值位置仅 \(O(1)\) 个

那么对于 \(a_i\) 作为 \(t\) 和 \(b_j\) 作为 \(t\) 的情况，分别计算 \(f(t)\) 的极值位置

极值位置需要一个 \(k\) 大查询和 \(\text{lower_bound}\)

计算 \(f(t)\) 需要一个前缀查询

我用 \(\text{BIT}\) 充当平衡树来维护，复杂度为 \(O((n+m+q)\log 10^6)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
const int N=1e6+10,INF=1e9+10;

int n,m,q;
int a[N],b[N];
struct BIT{
	ll s[N];
	int c[N],n;
	void Init(int m){ n=m; }
	void Add(int p,int x,int y){
		p++;
		while(p<N) s[p]+=x,c[p]+=y,p+=p&-p;
	}
	ll Que(int p){
		p++;
		if(p<=0) return 0;
		ll sum=0,cnt=0,t=p-1;
		while(p) sum+=s[p],cnt+=c[p],p-=p&-p;
		return t*cnt-sum;
	}
	int Rank(int p){
		if(p<0) return 0; // 一些奇怪的边界特判 ，防止查询越界
		p++,cmin(p,N-1);
		int res=0;
		while(p) res+=c[p],p-=p&-p;
		return res;
	}
	int Kth(int k){ // 注意一定要避免找到并不存在的数值
		cmin(k,n),cmax(k,1);
		int p=0;
		drep(i,19,0) if(p+(1<<i)<N && c[p+(1<<i)]<k) k-=c[p+=1<<i];
		return p;
	}
	int Prev(int x) { return Kth(Rank(x)); }
	int Next(int x) { return Kth(min(n,Rank(x)+1)); }
} A,B;

ll delta;
void AddA(int x,int k){
	delta+=x*k;
	A.Add(x,x*k,k);
}
void AddB(int x,int k){
	delta-=x*k;
	B.Add(x,x*k,k);
}

ll QueA(ll k){
	ll Min=min(A.Kth(1),B.Kth(1));
	auto F=[&](ll t){ return (n-1)*max(0ll,t-k-Min)-B.Que(t-k)+(m-n)*t; };
	ll ans=max(F(A.Kth(1)),F(A.Kth(n)));
	int p=B.Kth(m-1)+k;
	cmax(ans,F(A.Prev(p))),cmax(ans,F(A.Next(p)));
	return ans;
}

ll QueB(ll k){
	ll Min=min(A.Kth(1),B.Kth(1));
	auto F=[&](ll t){ return n*max(0ll,t-k-Min)-B.Que(t-k)+(m-n)*t; };
	ll ans=max(F(B.Kth(1)),F(B.Kth(m)));
	int p=B.Kth(m)+k;
	cmax(ans,F(B.Prev(p))),cmax(ans,F(B.Next(p)));
	return ans;
}

ll Que(ll k){
	return max(QueA(k),QueB(k))+delta+(n-m)*k;
}

int main(){
	n=rd(),m=rd(),q=rd(),A.Init(n),B.Init(m);
	rep(i,1,n) AddA(a[i]=rd(),1);
	rep(i,1,m) AddB(b[i]=rd(),1);
	while(q--) {
		int opt=rd();
		if(opt==1) {
			int x=rd(),y=rd();
			AddA(a[x],-1),AddA(a[x]=y,1);
		} else if(opt==2) {
			int x=rd(),y=rd();
			AddB(b[x],-1),AddB(b[x]=y,1);
		} else printf("%lld\n",Que(rd()));
	}
}