2019十一集训二分与倍增专题

第K大区间

定义一个区间的值为其众数出现的次数。现给出一个数列a[1…n]，求将所有区间的值排序后，第K大的值为多少。区间大小为1的不计。$1≤n≤10^5$

我们首先可以发现这个玩意是有一个单调性的，就是对于一个区间$[L, R]$，如果将它向右扩展，那么这个区间的价值（也就是众数）一定是不降的。那么满足单调性我们显然可以二分，直接二分出一个答案$Ans$表示第K大值，病假设一个函数$F(X)$表示价值大于等于$X$的区间个数。则题目转化为$F(Ans) \geq K$的基础上最大化$Ans$。二分这个$X$,$F(X) \geq K$那么范围缩小到$[X, R]$，反之就缩小到$[L, X - 1]$。

基本的思路有了，接下来就剩一个求$F(X)$了。关于这个东西有一个叫做$two ~pointers$的算法可以很好地解决，简而言之就是维护两个指针$l, r$和一个表示$i$出现了几次的桶$T[i]$，从左向右扫就可以维护价值大于等于$X$的区间。

r = 0 ;
for (int i = 1 ; i <= N ; i ++) {
    T[A[l - 1]] -- ;
    while(T[A[r]] < X) r ++ ;
    F += N - r +1 ;
}

时间复杂度$O(NlogN)$

聪明的质检员

小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1 到 n 逐一编号，每个矿石都有自己的重量 $w_i$ 以及价值$v_i$ 。

检验矿产的流程是：

1.给定 $m$ 个区间$[L_i，R_i]$；

2.选出一个参数 $W$；

3.对于一个区间 $[L_i，R_i ]$，计算矿石在这个区间上的检验值 $y$ ：

$$y_{i}=\left(\sum_{j} 1\right) \times\left(\sum_{j} v_{j}\right), j \in\left[L_{i j}, R_{i}\right] 且 w_{j} \geq W$$

也就是 $w$ 大于等于 $W$ 的个数和乘以价值和。

这批矿产的检验结果 $Y=∑_{i=1}^ny_i$

上头给了个标准值$S$，他希望你帮他调整参数 $W$ 的值，使 $|S-Y|$ 最小。

Noip2011

这个显然是要求我们二分$W$，但是如果你真的直接去二分$W$然后一个一个地计算检验的话，时间复杂度是$O(NMLogN)$显然是会炸掉的。

首先考虑单调性，我们发现当$W$变大的时候，$y$显然是会变小的，因为符合条件的矿石变少了嘛。所以$Y$也显然会跟着变小，那么$S - Y$就会变大。而至于加上绝对值，就需要分类讨论一下了。

不管这个，因为Y可以被表示成一个关于W的函数，我们设这个函数位$F(W)$，那么因为其单调不升，所以我们就可以将问题转化为求$|F(W) - S|$的最小值。而这个$F(W)$我们显然不能直接按照给的式子进行计算，我们统计对于已经确定的$W$，有贡献的$A[i]$个数的前缀和$Sum0$和$A[i]$的前缀和$Sum1$。然后计算就变成：

$$y_i = (Sum0_{R_i} - Sum0_{L_i - 1}) * (Sum1_{R_i} - Sum1_{L_i - 1})$$

就变成了$O(N)$的啦，配合上二分就可以$O(NlogN)$解决啦。

数比较大，记得开$long~long$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std ;

typedef long long LL ;
const LL MAXN = 200010 ;
const LL MAXM = 200010 ;
const LL INF = 0x3f3f3f3f3f3f3f3f ;
LL N, M, S, W[MAXN], V[MAXN], Sum0[MAXN], Sum1[MAXN], Max = - INF, Min = INF, Ans = INF ;
struct SQU {
	LL L, R ;
}	E[MAXN << 1] ;

inline LL Read() {
	LL X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

int main() {
	N = Read() ; M = Read() ; S = Read() ;
	for (LL i = 1 ; i <= N ; i ++)
		W[i] = Read(), V[i] = Read(),
		Max = max(Max, W[i]), Min = min(Min, W[i]) ;
	for (LL i = 1 ; i <= M ; i ++)
		E[i].L = Read(), E[i].R = Read() ;
	LL L = Min - 1, R = Max + 2, WW ;
	while (L <= R) {
		WW = (L + R) >> 1 ;
		for (LL i = 1 ; i <= N ; i ++)
			Sum0[i] = Sum1[i] = 0 ;
		for (LL i = 1 ; i <= N ; i ++) {
			if (W[i] >= WW)
				Sum0[i] = Sum0[i - 1] + 1, 
				Sum1[i] = Sum1[i - 1] + V[i] ;
			else
				Sum0[i] = Sum0[i - 1], 
				Sum1[i] = Sum1[i - 1] ;
		}
		LL Y = 0 ;
		for (LL i = 1 ; i <= M ; i ++)
			Y += (Sum0[E[i].R] - Sum0[E[i].L - 1]) * 
				 (Sum1[E[i].R] - Sum1[E[i].L - 1]) ;
		if (Y > S) L = WW + 1 ;
		else R = WW - 1 ;
		if (abs(Y - S) < Ans) Ans = abs(Y - S) ;
	}
	printf("%lld\n", Ans) ;
	return 0 ;
}

跳石头

一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块距离为 L 的岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石(不含起点和终点的岩石)。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。

$0≤M≤N≤50000, 1≤L≤10^9$。

Noip2015

额，这时间上就是一个很纯的二分，考虑单调性，显而易见地发现移走的石头越多，那么最短跳跃的最大值就越大，额，起码不会减就是了。然后就直接枚举最短跳跃的最大值，然后从头开始判断，记录最少要移走的石头的个数与M比较一下看看是否合法就可以了。

怎么算这个最少要移走的石头的个数其实可以人类智慧法，你发现如果枚举到一个$i$与$i - 1$的距离，它是小于我们二分的值$Mid$的，那么我们把这块石头移走就可以了。这样的答案一定是最优的，好像可以用反证法来证明，但是我觉得直觉就足以告诉你最优解了，这也是为什么目前普遍认为这道题的水平并不是很高的原因。

至于怎么操作叫移去这个石头，你可以记录一下上一个石头的下标嘛。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std ;

typedef long long LL ;
const int MAXN = 200010 ;
const int MAXM = 200010 ;
const int INF = 0x7fffffff ;
int Len, N, M, D[MAXN], Cnt = 0, Ans ;
inline int Read() {
	int X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

int main() {
	Len = Read() ; N = Read() ; M = Read() ;
	for (int i = 1 ; i <= N ; i ++) D[i] = Read() ;
	int L = 0, R = Len ;
	while (L <= R) {
		int Mid = (L + R) >> 1, Pas = 0 ; Cnt = 0 ;
		for (int i = 1 ; i <= N ; i ++) {
			if (D[i] - D[Pas] < Mid)
				Cnt ++ ;
			else Pas = i ;
		}
		if (Cnt > M) R = Mid - 1 ;
		else L = Mid + 1, Ans = Mid ;
	}
	printf("%d\n", Ans) ;
}

借教室

我们需要处理$n$天的借教室信息，其中第 i 天学校有$ r_i $个教室可供租借。

共有$m$份订单，每份订单用三个正整数描述，分别为$d_j,s_j,t_j，$表示某租借者需要从第$s_j$天到第$t_j$天租借教室（包括第$s_j$天和第$t_j$天），每天需要租借$d_j$个教室。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第$s_j$天到第$t_j$天中有至少一天剩余的教室数量不足$d_j$个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

$1≤n,m≤10^6, 0≤r_i,d_j≤10^9,1≤s_j≤t_j≤n$。

Noip2012

首先依然是考虑单调性，很容易发现，第$i$天肯定比$i + 1$天更容易满足需求，并且如果$i$天满足不了，那么接下来也不可能满足。单调性已有，那么考虑二分。

如何验证前 i 天是否满足条件？ 由于天数已经固定了，需求也就固定了。问题转化为，有很多次离线区间加，最后要求判断每一个元素是否小于$ d $。离线区间加我们可以差分后使用前缀和的技巧来解决：设数组$s[1..n]$，对于所有区间$[l,r]$整体$+c$的操作，我们令$s[l]+=c,s[r+1]-=c$这样做完之后，我们枚举位置$i=1~n$,同时设变量add。每当访问到一个位置$i$，$add+=s[i]，a[i]+=add$。这样就解决了区间加的问题。

复杂度：$O((n+m) log⁡m)$。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAXN 1000010
#define Inf 0x7fffffff
#define LL long long
using namespace std ;
LL Read(){
	LL X = 0 ; char ch = getchar() ;
	while(ch > '9' || ch < '0') ch = getchar() ;
	while(ch >= '0' && ch <= '9')
	X = (X << 1) + (X << 3) + (ch ^ 48), ch = getchar() ;
	return X ;
}
LL Before[MAXN] ;
LL N, M, Room[MAXN] ;
LL Rest[MAXN + 1] ;
struct Make{
	LL Data, L, R ;
}Edge[MAXN] ;
LL L, R, Mid;
bool Search(LL Now){
	for(int i = 1; i <= Now; i ++){
		Rest[Edge[i].L] += Edge[i].Data ;
		Rest[Edge[i].R + 1] -= Edge[i].Data ;
	}
	for(int i = 1; i <= N ; i ++){
		Room[i] = Rest[i] + Room[i - 1] ;
		if(Room[i] > Before[i])
			return 0 ;
	}
	return 1 ;
}
int main(){
	N = Read(), M = Read() ;
	for(int i = 1; i <= N; i ++)
		Before[i] = Read() ;
	for(int i = 1; i <= M; i ++){
		Edge[i].Data = Read() ;
		Edge[i].L = Read() ;
		Edge[i].R = Read() ;
	}
	L = 0; R = M + 1 ;
	while(L < R){
		memset(Rest, 0, sizeof(Rest)) ;
		memset(Room, 0, sizeof(Room)) ;
		Mid = (L + R) >> 1 ;
		int Num = Search(Mid) ;
		if(! Num) R = Mid ;
		else L = Mid + 1 ;
	}
	if(0 < L && L <= M) printf("-1\n%d", L) ;
	else puts("0") ;
	return 0 ;
}

这种做法是有可能被卡的，因此还可以用一些数据结构进行优化，但是已经超出了本题的范围，在这里不再探究。

妮厨的愤怒

对于一个字符串$S[1…n]$，询问$q$次，每次询问$[l,r]$内最长的回文串。

$1≤n ,q≤10^5，0≤l≤r<n$ ，只包含小写拉丁字母