解题报告——灵活利用题目单调性省下复杂度

有一种题目，需要直接/间接查询全局最值，并且带修改。

直接 set/priority_queue 不完了吗？

然而，这类题目通常具有巨大的操作量，朴素的需要额外复杂度来维护内部性质的数据结构（例如需要带一个 \(\log\)）往往无法通过此类题目。

但是，这种题目本身一般具有某种单调性质，这使得我们可以使用一些复杂度更低的方法来维护此题的答案。

例题一：洛谷 P6033 [NOIP2004 提高组] 合并果子 加强版

一个小贪心：肯定是每次选最小的两个合并最优。

直接全插入堆中模拟不完了？哈夫曼树板子好吧！

数据范围：\(n\le 10^7,a_i\le 10^5\)。

复杂度 \(n \log n\) 直接爆炸。

显然是要线性做法。

发现 \(a_i\le 10^5\)，桶排序可以做到 \(O(n)\)。

这样原序列就是单调不减的了。

性质：合并得越晚，合并所得到的值越大。

显然的吧，不证了。

注意到每次的最小值一定是没合并的最小值与合并后的最小值之一。

而合并后的值单调不降。

考虑建两个队列，一个队列存没有合并过的，另一个存合并得到的。

这样每次的最小值一定是两个队列的队首部分。

复杂度线性。

const int N=1e7+10,M=1e5+10;
int n,a[N],cnt[M];
ll ans;
deque<ll>q1,q2;
main() {
	n=read();
	FOR(i,1,n) a[i]=read(),++cnt[a[i]];
	FOR(i,0,M-1) while(cnt[i]) q1.push_back(i),--cnt[i];
	while(q1.size()||q2.size()) {
		ll k=1e18,x=1e18,y=1e18,z=1e18;
		if(q1.size()>1) x=q1[0]+q1[1];
		if(q1.size()&&q2.size()) y=q1[0]+q2[0];
		if(q2.size()>1) z=q2[0]+q2[1];
		if(!(q1.size()>1||(q1.size()&&q2.size())||q2.size()>1)) {
			cout<<ans<<"\n";
			return 0;
		}
		k=min(x,min(y,z));
		if(k==z) q2.pop_front(),q2.pop_front();
		else if(k==y) q1.pop_front(),q2.pop_front();
		else if(k==x) q1.pop_front(),q1.pop_front();
		q2.push_back(k);
		ans+=k;
	}
	return 0;
}

太简单了？

上强度！

例题二：[NOIP2016 提高组] 蚯蚓

先按照蚯蚓长度从小到大排序。

发现直接暴力 \(+q\) 肯定不可取。

考虑偏移量，每次取真实长度时加上 \(\Delta\)。

问题来了，怎么找最长的蚯蚓呢，查询 \(5\times 10^6\) 肯定不能用堆。

性质：每一种蚯蚓（没被切，左半部分，右半部分）长度单调不升。

证明：

首先没被切的肯定单调（排好序了）。

先考虑 \(q=0\)。

设当前最长为 \(x_0\)，次长为 \(x_1\)。

先证左半部分。

\[∵ x_0\ge x_1\\ ∴ p x_0\ge p x_1\\ ∴ \lfloor p x_0\rfloor \ge \lfloor p x_1\rfloor. \]

再证右半部分。

\(x_1 \ge x_2 \land x_1, x_2 \in \Z\Rightarrow x_1 - x_2 \in \N\)。又 $ ∵ 0 <p < 1$，故有：

\[\begin{aligned}x_1 - x_2 &\ge p(x_1 - x_2) \\ x_1 - x_2 + p x_2 & \ge px_1 \\ \lfloor px_2 + (x_1 - x_2) \rfloor & \ge\lfloor px_1 \rfloor \\ \lfloor px_2\rfloor + (x_1 - x_2) & \ge \lfloor px_1 \rfloor \\ x_1 - \lfloor px_1 \rfloor & \ge x_2 - \lfloor px_2 \rfloor \end{aligned} \]

再考虑 \(q>0\)。

则后面切的为 \(x_1+q\)。

左半部分：

\[\lfloor p x_0\rfloor \ge \lfloor p x_1+pq \rfloor=\lfloor p(x_1+q) \rfloor \]

右半部分：

\[x_1 - \lfloor px_1\rfloor+ q \ge x_2 +q - \lfloor px_2\rfloor \ge x_2 + q - \lfloor p(x_2 +q) \rfloor \]

证毕。

综上所述，可以用 \(3\) 个队列分别维护 \(3\) 种蚯蚓，不断取出 \(3\) 个队头最大值。

时间复杂度 \(O(n\log n+m)\)。

const int N=1e5+10,M=7e6+10;
int n,m,q,u,v,t,k,in,a[N];
ll Delta;
queue<ll>A,B,C;
int cmp(int x,int y) {return x>y;}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>q>>u>>v>>t;
	for(int i=1;i<=n;++i) cin>>a[i];
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;++i) A.push(a[i]);
	for(int i=1;i<=m;++i) {
		ll x=-1e9;
		if(A.size()) x=A.front();
		if(B.size()) x=max(x,B.front());
		if(C.size()) x=max(x,C.front());
		if(A.size()&&A.front()==x) A.pop();
		else if(B.size()&&B.front()==x) B.pop();
		else if(C.size()&&C.front()==x) C.pop();
		x+=Delta;
		if(i%t==0) cout<<x<<" ";
		ll num1=x*u/v-q-Delta,num2=x-x*u/v-q-Delta;
		B.push(num1);
		C.push(num2);
		Delta+=q;
	}
	cout<<"\n";
	while(A.size()||B.size()||C.size()) {
		ll x=-1e9;
		if(A.size()) x=A.front();
		if(B.size()) x=max(x,B.front());
		if(C.size()) x=max(x,C.front());
		if(A.size()&&A.front()==x) A.pop();
		else if(B.size()&&B.front()==x) B.pop();
		else if(C.size()&&C.front()==x) C.pop();
		if((++in)%t==0) cout<<x+Delta<<" ";
	}
	cout<<"\n";
	return 0;
}

下面来一道 NOI/NOI+/CTSC 的题目！

例题三：[CSP-S2020] 贪吃蛇

个人感觉比例题二要简单一些。

思路证明

单调性：吃东西后的蛇越往后越弱。

证明：显然最强的蛇吃东西后越来越弱，最弱的蛇被吃掉后越来越强。

两者相减即得原命题。

证毕。

直接建两个队列维护没吃过的和吃过的蛇，直接模拟。

复杂度线性。

const int N=1e6+10;
int t,n,a[N],ans;
deque<pair<int,int> >q1,q2;
void Solve() {
	q1.clear(),q2.clear();
	FOR(i,1,n) q1.pb(mkp(a[i],i));
	while(1) {
		if(q1.size()+q2.size()==2) {
			ans=1;
			break;
		}
		auto z=q1.front();q1.pt();
		pair<int,int>x;
		if(!q2.size()||q1.size()&&q1.back()>q2.back()) x=q1.back(),q1.pk();
		else x=q2.back(),q2.pk();
		auto et=mkp(x.fr-z.fr,x.se);
		if(!q1.size()||q1.front()>et) {
			ans=q1.size()+q2.size()+2;
			int cnt=0;
			while(1) {
				++cnt;
				if(q1.size()+q2.size()+1==2) {
					ans-=(1-(cnt&1));
					break; 
				}
				pair<int,int>x;
				if(!q2.size()||q1.size()&&q1.back()>q2.back()) x=q1.back(),q1.pk();
				else x=q2.back(),q2.pk();
				et=mkp(x.fr-et.fr,x.se);
				if(!((!q1.size()||q1.front()>et)&&(!q2.size()||q2.front()>et))) {
					ans-=(1-(cnt&1));
					break; 
				} 
			} 
			break;
		} else q2.pf(et);
	} 
	cout<<ans<<"\n";
} 
main() {
	t=read()-1;
	cin>>n;
	FOR(i,1,n) a[i]=read();
	Solve();
	while(t--) {
		int k=read();
		FOR(i,1,k) {
			int x=read(),y=read();
			a[x]=y;
		}
		Solve();
	}
	return 0;
}

听说有拿 set 水过的。