P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

Sol

蒲公英题意基本相同，但是注意到空间限制 62.5MB，显然不能用蒲公英的做法。

考虑先把整块的答案算出来，然后把小块的部分补上去，显然大块可以预处理，小块可以直接暴力查询是否越界。

代码很简单。

Code

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cassert>
#include <chrono>
#include <random>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define desktop "C:\\Users\\MPC\\Desktop\\"
#define IOS ios :: sync_with_stdio (false),cin.tie (0),cout.tie (0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
template <typename T1,typename T2> bool tomax (T1 &x,T2 y) {
    if (y > x) return x = y,true;
    return false;
}
template <typename T1,typename T2> bool tomin (T1 &x,T2 y) {
    if (y < x) return x = y,true;
    return false;
}
LL power (LL a,LL b,LL p) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
int fastio = (IOS,0);
#define endl '\n'
#define puts(s) cout << s << endl
const int N = 500010,M = 1010;
int n,m;
int L[M],R[M],pos[N];
int a[N];
vector <int> v[N];
int posv[N];
int res[M][M];
int cnt[N];
int main () {
	cin >> n >> m;
	int len = sqrt (n);
	for (int i = 1;i <= len;i++) L[i] = (i - 1) * len + 1,R[i] = i * len;
	R[len] = n;
	for (int i = 1;i <= len;i++) {
		for (int j = L[i];j <= R[i];j++) pos[j] = i;
	}
	for (int i = 1;i <= n;i++) cin >> a[i],v[a[i]].pb (i),posv[i] = v[a[i]].size () - 1;
	for (int i = 1;i <= len;i++) {
		for (int j = 1;j < N;j++) cnt[j] = 0;
		for (int j = i;j <= len;j++) {
			res[i][j] = res[i][j - 1];
			for (int k = L[j];k <= R[j];k++) tomax (res[i][j],++cnt[a[k]]);
		}
	}
	for (int i = 1;i < N;i++) cnt[i] = 0;
	int lastans = 0;
	while (m--) {
		int l,r;
		cin >> l >> r;
		l ^= lastans,r ^= lastans;
		int p = pos[l],q = pos[r];
		if (p == q) {
			int ans = 0;
			for (int i = l;i <= r;i++) tomax (ans,++cnt[a[i]]);
			for (int i = l;i <= r;i++) cnt[a[i]] = 0;
			cout << (lastans = ans) << endl;
			continue;
		}
		int ans = res[p + 1][q - 1];
		for (int i = l;i <= R[p];i++) {
			int t = posv[i];
			while (t + ans < v[a[i]].size () && v[a[i]][t + ans] <= r) ans++;
		}
		for (int i = L[q];i <= r;i++) {
			int t = posv[i];
			while (t - ans >= 0 && v[a[i]][t - ans] >= l) ans++;
		}
		cout << (lastans = ans) << endl;
	}
	return 0;
}