# 朝田诗乃 的博客

### 题解 P3709 【大爷的字符串题】

posted on 2019-03-20 18:29:03 | under 题解 |

%%%莫队的神仙

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500050, BLNM = 5050;
void read(int &x) {
char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
int belong[MAXN], L[MAXN], R[MAXN], a[MAXN], MAX[BLNM][BLNM], blsz, n, q, w[MAXN], siz[MAXN], blnm, cnt[MAXN], lastans;
vector <int> lis[MAXN];
int main() {
for(int i = 1; i <= n; ++i) read(a[i]), w[i] = a[i], belong[i] = (i-1) / blsz + 1;
sort(a+1, a+n+1); int _n = unique(a+1, a+n+1) - a - 1;
for(int i = 1; i <= n; ++i) {
w[i] = lower_bound(a+1, a+_n+1, w[i]) - a;
siz[i] = lis[w[i]].size();
lis[w[i]].push_back(i);
} blnm = belong[n];
for(int i = 1; i <= blnm; ++i) L[i] = (i-1) * blsz, R[i] = L[i] + blsz - 1;
L[1] = 1; R[blnm] = n;
for(int i = 1; i <= blnm; ++i) {
memset(cnt, 0, sizeof cnt);
int mx = 0, ima = i;
for(int j = L[i]; j <= n; ++j) {
++cnt[w[j]];
mx = max(cnt[w[j]], mx);
if(j == R[ima]) {MAX[i][ima] = mx; ++ima;}
}
}
while(q--) {
int lblock = belong[l], rblock = belong[r]; lastans = 0;
if(lblock == rblock) {
for(int i = l; i <= r; ++i) while(siz[i] + lastans < lis[w[i]].size() && lis[w[i]][siz[i] + lastans] <= r) ++lastans;
} else {
if(lblock + 1 < rblock) lastans = MAX[lblock+1][rblock-1];
for(int i = l; i <= R[lblock]; ++i) while(siz[i] + lastans < lis[w[i]].size() && lis[w[i]][siz[i] + lastans] <= r) ++lastans;
for(int i = L[rblock]; i <= r; ++i) while(siz[i] >= lastans && lis[w[i]][siz[i] - lastans] >= l) ++lastans;
}
printf("%d\n", -lastans);
}
}