[题解] CF407E k-d-sequence

k-d-sequence

给你一个长为 \(n\) 的序列，求最长的子区间使得它加入至多 \(k\) 个数后，重排后是公差为 \(d\) 的等差数列。
\(n, k \le 2 \times 10^5\)，\(0 \le d \le 10^9\)。

公差是 \(d\) 的等差数列模 \(p\) 的值应该相等，所以把序列按极长模 \(p\) 同余的连续段分组。

对于同一组，我们将每个数都除以 \(d\)，然后就转化成了求公差为 \(1\) 的等差数列。

如果一段区间 \([l, r]\) 满足要求，这就相当于要求 \([l, r]\) 中的数是值域上连续的一段且互不相等。然后套上 Good Subsegments 的判定方法就做完了（也就是判定 \(\max - \min - (r - l) \le k\)）。

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

constexpr int MAXN = 2e5 + 9, DLT = 1e9 + 1;
int n, k, d, a[MAXN], lst[MAXN], ans = 0, ansl, ansr;
vector<int> stk[2];
map<int, int> vis;

struct Node {
	ll mn, tag;
} sgt[MAXN << 2]; 

void Push_Up(int p) {
	sgt[p].mn = min(sgt[p << 1].mn, sgt[p << 1 | 1].mn);
	return;
}
void Push_Tag(int p, ll k) {
	sgt[p].mn += k, sgt[p].tag += k;
	return;
}
void Push_Down(int p) {
	if (sgt[p].tag) {
		Push_Tag(p << 1, sgt[p].tag);
		Push_Tag(p << 1 | 1, sgt[p].tag);
		sgt[p].tag = 0;
	}
	return;
}
void Build(int L = 1, int R = n, int p = 1) {
	if (L == R) return sgt[p].mn = L - k, void();
	int Mid = L + R >> 1;
	Build(L, Mid, p << 1), Build(Mid + 1, R, p << 1 | 1);
	Push_Up(p); return;
}
void Update(int l, int r, ll k, int L = 1, int R = n, int p = 1) {
	if (l <= L && R <= r) return Push_Tag(p, k);
	Push_Down(p); int Mid = L + R >> 1;
	if (l <= Mid) Update(l, r, k, L, Mid, p << 1);
	if (Mid < r) Update(l, r, k, Mid + 1, R, p << 1 | 1);
	Push_Up(p); return;
}
int Query(int l, int r, int L = 1, int R = n, int p = 1) {
	if (l <= L && R <= r) {
		if (sgt[p].mn > 0) return -1;
		while (L < R) {
			Push_Down(p); int Mid = L + R >> 1;
			if (sgt[p << 1].mn <= 0) R = Mid, p <<= 1;
			else L = Mid + 1, p = (p << 1 | 1);
		}
		return L;
	}
	Push_Down(p); int Mid = L + R >> 1;
	if (r <= Mid) return Query(l, r, L, Mid, p << 1);
	if (Mid < l) return Query(l, r, Mid + 1, R, p << 1 | 1);
	int ret = Query(l, r, L, Mid, p << 1);
	if (~ret) return ret;
	return Query(l, r, Mid + 1, R, p << 1 | 1);
}

int qry(int pos, int L = 1, int R = n, int p = 1) {
	if (L == R) return sgt[p].mn;
	Push_Down(p); int Mid = L + R >> 1;
	if (pos <= Mid) return qry(pos, L, Mid, p << 1);
	else return qry(pos, Mid + 1, R, p << 1 | 1);
}

void slv() {
	n = Read<int>(), k = Read<int>(), d = Read<int>();
	for (int i = 1; i <= n; i ++) a[i] = Read<int>() + DLT, vis[a[i]] = 0;
	for (int i = 1; i <= n; i ++) lst[i] = vis[a[i]], vis[a[i]] = i;
	if (d == 0) {
		for (int l = 1, r; l <= n; l = r + 1) {
			r = l;
			while (r + 1 <= n && a[r + 1] == a[l]) r ++;
			if (r - l + 1 > ans) ans = r - l + 1, ansl = l, ansr = r;
		}
		Write(ansl, ' '), Write(ansr, '\n');
		return;
	}
	Build();
	for (int l = 1, r; l <= n; l = r + 1) {
		r = l; int mx = l;
		while (r + 1 <= n && a[r + 1] % d == a[r] % d) r ++;
		stk[0].clear(), stk[0].emplace_back(l - 1);
		stk[1].clear(), stk[1].emplace_back(l - 1);
		Update(l, r, - (l - 1));
		for (int i = l; i <= r; i ++) {
			cmax(mx, lst[i] + 1), a[i] /= d;
			while (stk[0].size() > 1 && a[stk[0].back()] <= a[i])
				Update(stk[0][stk[0].size() - 2] + 1, stk[0].back(), - a[stk[0].back()]), stk[0].pop_back();
			Update(stk[0].back() + 1, i, a[i]), stk[0].emplace_back(i);
			while (stk[1].size() > 1 && a[stk[1].back()] >= a[i])
				Update(stk[1][stk[1].size() - 2] + 1, stk[1].back(), a[stk[1].back()]), stk[1].pop_back();
			Update(stk[1].back() + 1, i, - a[i]), stk[1].emplace_back(i);
			Update(l, r, -1);
			int j = Query(mx, i);
			if (~j && i - j + 1 > ans) ans = i - j + 1, ansl = j, ansr = i;
		}
	}
	Write(ansl, ' '), Write(ansr, '\n');
	return;
}
``