D. Range and Partition

[Link](D. Range and Partition)

题意

给你一个长为 n n n的数组，让你分成 k k k段，满足每段在 [ x , y ] [x,y] [x,y]内的严格大于在在 [ x , y ] [x,y] [x,y]外的，请你最小化 y − x y-x y−x并输出切割方案。

思路

设 c n t 1 ： 在 [ x , y ] 内 的 个 数 ， c n t 2 ： 不 在 [ x , y ] 内 的 个 数 ， f ( l , r ) ： 原 数 组 a [ l ] , a [ l + 1 ] , . . . , a [ r ] 中 c n t 1 − c n t 2 的 值 cnt1：在[x,y]内的个数，cnt2：不在[x,y]内的个数，f(l,r)：原数组a[l],a[l+1],...,a[r]中cnt1-cnt2的值 cnt1：在[x,y]内的个数，cnt2：不在[x,y]内的个数，f(l,r)：原数组a[l],a[l+1],...,a[r]中cnt1−cnt2的值。

f ( ) f() f()的性质： 1. f ( l , r ) > 0 则 该 区 间 一 定 满 足 条 件 ， 2. f ( l , r ) = ( l , m i d ) + ( m i d + 1 , r ) 满 足 合 并 1.f(l,r)>0则该区间一定满足条件，2.f(l,r) = (l,mid)+(mid+1,r)满足合并 1.f(l,r)>0则该区间一定满足条件，2.f(l,r)=(l,mid)+(mid+1,r)满足合并

若 f ( l , r ) > 0 ， 不 妨 设 f ( l , r ) = = k ， f(l,r)>0，不妨设f(l,r)==k， f(l,r)>0，不妨设f(l,r)==k，则该区间可分为 k k k个满足条件的区间。

证明:

首先设 f ( l , r ) = = k > 0 f(l,r)==k>0 f(l,r)==k>0，如有一个位置 x x x使得 f ( l , x ) = = 1 f(l,x)==1 f(l,x)==1,那么我们就可以从这个位置切割，使得 f ( x + 1 , r ) = = k − 1 f(x +1,r)==k-1 f(x+1,r)==k−1。

又因为 f ( l , l − 1 ) = = 0 f(l,l-1)==0 f(l,l−1)==0，（空区间无意义），且 f ( l , r ) = = k f(l,r)==k f(l,r)==k， f ( l , x x ) → f ( l , x x + 1 ) f(l,xx)\to f(l,xx + 1) f(l,xx)→f(l,xx+1)时值最多边 1 1 1，因此类似于零点存在定理，一定存在某个点 x x x满足 f ( l , x ) = = 1 f(l,x)==1 f(l,x)==1。

如果我们知道想要分成 k k k段，则要满足 c n t 1 − c n 2 = = k , c n t 1 + c n t 2 = = n → c n t 1 = ⌈ ( n + k ) / 2 ⌉ cnt1-cn2==k,cnt1+cnt2==n\to cnt1=\lceil (n +k)/2\rceil cnt1−cn2==k,cnt1+cnt2==n→cnt1=⌈(n+k)/2⌉

因此我们可以拿双指针从头到尾扫一下值域判断一下满足条件 c n t 1 = ⌈ ( n + k ) / 2 ⌉ cnt1=\lceil (n +k)/2\rceil cnt1=⌈(n+k)/2⌉的最小区间，然后从头到尾暴力扫，如果当前 f ( ) = = 1 f()==1 f()==1输出这个区间即可。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
	e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N], s[N];
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	cin >> T;
	while (T -- ) {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++) cin >> a[i], s[a[i]] ++;
		int len = (n + k + 1) / 2, resl = 1, resr = n, mn = n, last = 1;	
		int sum = 0;
		for (int i = 1, j = 1; i <= n; i ++) {			
			while (j <= n && sum < len) sum += s[j ++];
			if (sum < len) break;
			if (j - i < mn) {
				mn = j - i;
				resl = i, resr = j - 1;				
			}
			sum -= s[i];
		}
		
		cout << resl << ' ' << resr << endl;
		sum = 0;
		for (int i = 1; i <= n; i ++) {
			if (a[i] >= resl && a[i] <= resr) sum ++;
			else sum --;
			
			if (sum > 0)  {
				if (k != 1)
					cout << last << ' ' << i << endl;
				else {
					cout << last << ' ' << n << endl;
					break;
				} 
				last = i + 1;
				k --;	
				sum = 0;				
			}
		}
		for (int i = 1; i <= n; i ++) s[i] = 0;
	}
	return 0;
}