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$

2.$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()));
	}
}