codechef QCHEF(不删除莫队)

题意

题目链接

给出长度为\(n\)的序列，每次询问区间\([l, r]\)，要求最大化

\(max |x − y| : L_i ≤ x, y ≤ R_i and A_x = A_y\)

Sol

标算神仙的一批看不懂。

维护好每个数出现的左右位置之后直接上不删除莫队就行了

#include<bits/stdc++.h>

const int MAXN = 1e5 + 10, INF = 1e9 + 7;

using namespace std;

template<typename A, typename B> inline bool chmax(A &x, B y) {

	if(y > x) {x = y; return 1;}

	else return 0;

}

template<typename A, typename B> inline bool chmin(A &x, B y) {

	if(y < x) {x = y; return 1;}

	else return 0;

}

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, K, M, a[MAXN], l[MAXN], r[MAXN], tl[MAXN], tr[MAXN], belong[MAXN], block, cnt, ans[MAXN];

struct query {

	int l, r, id;

	bool operator < (const query &rhs) const {

		return belong[l] == belong[rhs.l] ? r < rhs.r : belong[l] < belong[rhs.l];

	}

};

vector<query> q[MAXN];

int solve(int l, int r) {

	for(int i = l; i <= r; i++) tl[a[i]] = INF, tr[a[i]] = 0;

	int ans = 0;

	for(int i = l; i <= r; i++) {

		int x = a[i];

		chmin(tl[x], i), chmax(tr[x], i);

		chmax(ans, tr[x] - tl[x]);

	}

	return ans;

}

int update(int x) {

	chmax(tr[a[x]], x);

	chmin(tl[a[x]], x);

	return tr[a[x]] - tl[a[x]];

}

int update2(int x) {

	int v = a[x];

	chmax(r[v], x);

	chmin(l[v], x);

	return max(tr[v] - l[v], r[v] - l[v]);

}

void LxlDuLiu(vector<query> v, int id) {

	int base = id * block, ll = base, rr = ll - 1, pre = 0, now = 0;

	memset(tr, 0, sizeof(tr)); memset(r, 0, sizeof(r));

	memset(tl, 0x3f, sizeof(tl)); memset(l, 0x3f, sizeof(l));

	for(auto &x : v) {

		//memset(l, 0x3f, sizeof(l)); memset(r, 0, sizeof(r));

		while(rr < x.r) chmax(now, update(++rr));

		pre = now;

		while(ll > x.l) chmax(now, update2(--ll));

		chmax(ans[x.id], now);

		while(ll < base) r[a[ll]] = 0, l[a[ll]] = INF, ll++;

		now = pre;

	}

}

int main() {

//	freopen("a.in", "r", stdin);

	//freopen("b.out", "w", stdout);

	N = read(); K = read(); M = read(); block = sqrt(N); int mx = 0;

	for(int i = 1; i <= N; i++) a[i] = read(), belong[i] = (i - 1) / block + 1, chmax(mx, belong[i]);

	for(int i = 1; i <= M; i++) {

		int l = read(), r = read();

		if(belong[l] == belong[r]) ans[i] = solve(l, r);

		else q[belong[l]].push_back({l, r, i});

	}

	for(int i = 1; i <= mx; i++) sort(q[i].begin(), q[i].end());

	for(int i = 1; i <= mx; i++)

		LxlDuLiu(q[i], i);

	for(int i = 1; i <= M; i++) printf("%d\n", ans[i]);

	return 0;

}