Description

给一个序列(<=2*10^5)，求问最长的字典序最小的一个序列的子串，该子串满足如下性质：将该子串的所有元素取出组成与子串长度相等的新数列，在新数列中至多添加K个数字，使得数列为D等差数列，D等差数列即数列为等差数列且公差为D。

Solution：

可以发现，如果a[i] - a[i-1]不能被D整除，那么i和i-1一定不能连续出现，而且重复也是不能的，所以可以按照上面的两个性质，有了左边界。

如果一段序列l..r排序后可以通过添加数字来使得其变成一个D等差，那么这段序列必须要满足

(max{a[l..r]} - min{a[l..r]}) / D - (r - l) <= K

即 max{a[l..r]} - min{a[l..r]} - (r - l) * D <= K * D

可以发现，我们用单调队列维护max与min时，对于右移右端点，增量都是可以算出来的。

查询以r为右端点的最小l的时候，如果我们用线段树维护左式的最小值，那么显然可以知道查询的时候是向左走还是向右走

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
typedef long long LL;
const int MAXN = 200010;
const LL inf = 1LL << 50;
int N, K, D, ans, ansl, ansr, a[MAXN];
int pos1[MAXN], pos2[MAXN], mx[MAXN], mi[MAXN];
map<int, int> pre;
struct Tseg
{
	int L, R, mid; LL key, flag; Tseg *lch, *rch;
	void Init(int l, int r)
	{
		lch = rch = 0x0; flag = 0;
		mid = ((L = l) + (R = r)) / 2;
		if(L == R) { key = 0; return; }
		(lch = new Tseg()) -> Init(l, mid);
		(rch = new Tseg()) -> Init(mid + 1, r);
		key = min(lch -> key, rch -> key);
	}
	void Pushdown()
	{
		if(!flag) return; LL d = flag; flag = 0;
		if(lch) lch -> flag += d, lch -> key += d;
		if(rch) rch -> flag += d, rch -> key += d;
	}
	void Modify(int l, int r, LL v)
	{
		if(l > r) return; Pushdown();
		if(L == l && R == r) { flag += v; key += v; return; }
		if(l > mid) rch -> Modify(l, r, v); else
		if(r <=mid) lch -> Modify(l, r, v); else
		lch -> Modify(l, mid, v), rch -> Modify(mid + 1, r, v);
		key = min(lch -> key, rch -> key);
	}
	int Query()
	{
		Pushdown(); if(L == R) return L;
		return (lch->key <= (LL) K * D) ? lch->Query() : rch->Query();
	}
} T;
int main()
{
	scanf("%d%d%d", &N, &K, &D);
	for(int i = 1; i <= N; ++i) scanf("%d", &a[i]);
	if(D == 0)
	{
		int last = 0;
		for(int i = 1; i <= N; ++i)
		{
			if(i == 1 || a[i] != a[i-1]) last = i;
			if(i - last + 1 > ans) ans = i - last + 1, ansl = last, ansr = i;
		}
		printf("%d %d\n", ansl, ansr);
		return 0;
	}
	T.Init(1, N); int last = 1, t1 = 0, t2 = 0;
	for(int i = 1; i <= N; ++i)
	{
		if(i != 1 && (a[i] - a[i-1]) % D) T.Modify(last, i - 1, inf), last = i;
		if(pre[a[i]] >= last) T.Modify(last, pre[a[i]], inf), last = pre[a[i]] + 1;
		for(; t1 > 0 && a[i] > a[mx[t1]]; --t1) T.Modify(mx[t1-1] + 1, mx[t1], a[i] - a[mx[t1]]);
		for(; t2 > 0 && a[i] < a[mi[t2]]; --t2) T.Modify(mi[t2-1] + 1, mi[t2], a[mi[t2]] - a[i]);
		if((mx[++t1] = mi[++t2] = pre[a[i]] = i) != 1) T.Modify(last, i - 1, -D); int temp = T.Query();
		if(i - temp + 1 > ans) ans = i - temp + 1, ansl = temp, ansr = i;
	}
	printf("%d %d\n", ansl, ansr);
	return 0;
}