RE 记录

#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e5 + 5;

struct node
{
	int id, l, r;
} q[N];

int len, res, cn;
vector <int> num;
int a[N], pre[N], aft[N], la[N], clear[N], ans[N];

inline int get(int x)
{
	return x / len;
}

inline bool cmp(const node &x, const node &y)
{
	int xl = get(x.l), yl = get(y.l);
	if(xl != yl) return xl < yl;
	return x.r < y.r;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m; cin >> n;
	for(int i = 1; i <= n; ++ i)
		cin >> a[i], num.push_back(a[i]);
	sort(num.begin(), num.end());
	num.erase(unique(num.begin(), num.end()), num.end());
	for(int i = 1; i <= n; ++ i)
		a[i] = lower_bound(num.begin(), num.end(), a[i]) - num.begin();
	cin >> m;
	for(int i = 1; i <= m; ++ i)
	{
		q[i].id = i;
		cin >> q[i].l >> q[i].r;
	}
	len = sqrt(n);
	sort(q + 1, q + m + 1, cmp);
	for(int x = 1; x <= m;)
	{
		int y = x; cn = 0;
		while(y <= m && get(q[y].l) == get(q[x].l)) y ++ ;
		int right = get(q[x].l) * len + len - 1;
		while(q[x].r <= right)
		{
			res = 0;
			int l = q[x].l, r = q[x].r;
			for(int k = l; k <= r; ++ k)
				la[a[k]] = 0;
			for(int k = l; k <= r; ++ k)
				if(!la[a[k]]) la[a[k]] = k;
				else res = max(res, k - la[a[k]]);
			ans[q[x].id] = res, x ++ ;
		}
		res = 0;
		int i = right, j = right + 1;
		while(x < y)
		{
			int l = q[x].l, r = q[x].r;
			while(i < r)
			{
				i ++ , aft[a[i]] = i;
				if(!pre[a[i]]) pre[a[i]] = i, clear[ ++ cn] = a[i];
				res = max(res, i - pre[a[i]]);
			}
			int backup = res;
			while(j > l)
			{
				j -- ;
				if(aft[a[j]]) res = max(res, aft[a[j]] - j);
				else aft[a[j]] = j;
			}
			ans[q[x].id] = res, res = backup;
			while(j < right + 1)
			{
				if(aft[a[j]] == j) aft[a[j]] = 0;
				j ++ ;
			}
			x ++ ;
		}
		for(int k = 1; k <= cn; ++ k) pre[clear[k]] = aft[clear[k]] = 0;
	}
	for(int i = 1; i <= m; ++ i) cout << ans[i] << '\n';
}

在洛谷上 RE，下载数据在本地过了，离谱。