链接 : Yuno loves sqrt technology III
先考虑一道分块板子
在这道题中，将值离散化后，用了两个重要的数组
- \(p_{i,j}\) : 表示第\(i\)个块到第\(j\)个块的最小的众数
- \(s_{i,j}\) : 表示前\(i\)个块中\(j\)出现的次数
发现\(s\)的空间是\(O(n\sqrt{n})\)的
\(but\)，\(\huge{n\le 5\times 10^5}\)
所以肯定不能有s数组。
沿用上面的思想，用一个\(s\)数组记录第\(i\)个块到第\(j\)个块中众数的出现次数。
这个东西暴力求就可以，时间复杂度为\(O(n\sqrt{n})\)，这样就把整块的贡献算出来了。
然后考虑对散块的处理。
对于散块中的数，只需要判断这个值出现次数可否达到ans+1。
可以对于每一个值，开一个vector \(p\)记录这个值出现的位置。
记当前枚举到的值所在的位置在它所在的vector中的下标为\(p\)
对于左侧散块，如果\(p+ans\le r\) ，那么ans++
对于右侧散块，如果\(p-ans \ge l\) ， 那么ans++;
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
namespace IO{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define pc putchar_unlocked
template<typename T>
inline void read(T &x){
x = 0;bool f = false;char s = gc();
for(;s < '0'||'9' < s;s = gc()) f|=(s=='-');
for(;'0' <= s&&s <= '9';s = gc())
x = (x<<1) + (x<<3) + (s^48);
x = f?-x:x;
}
template<class T,class... Args>
inline void read(T &x,Args& ...args){read(x);read(args...);}
template<typename T>
inline void write(T x){
static char s[20],top;
top = 0;
if(x < 0) pc('-'),x = -x;
do{s[++top] = x%10 + '0';}while(x/=10);
while(top) pc(s[top--]);
}
}using namespace IO;
const int N = 5e5 + 10,M = 720;
int n,m,a[N],pos[N],len,L[M],R[M];
int tot[N],w[N],mx[M][M];
vector<int> P[N];
inline void init(){
read(n,m);
for(int i = 1;i <= n; ++i) read(a[i]);
len = sqrt(n);
for(int i = 1;i <= len; ++i) L[i] = R[i - 1] + 1,R[i] = i*len;
if(R[len] < n) len++,L[len] = R[len - 1] + 1,R[len] = n;
vector<int> num;
for(int i = 1;i <= n; ++i) num.emplace_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() + 1;
P[a[i]].emplace_back(i);
w[i] = P[a[i]].size() - 1;
}
int V = num.size();
for(int i = 1;i <= len; ++i){
for(int j = 1;j <= V; ++j) tot[j] = 0;
for(int j = L[i];j <= R[i]; ++j) pos[j] = i;
for(int j = i;j <= len; ++j){
int &res = mx[i][j];
res = mx[i][j-1];
for(int k = L[j];k <= R[j]; ++k)
res = max(res,++tot[a[k]]);
}
}
for(int i = 1;i <= V; ++i) tot[i] = 0;
}
inline int query(int left,int right){
int p = pos[left],q = pos[right],res = 0;
if(p == q){
for(int i = left;i <= right; ++i)
res = max(res,++tot[a[i]]);
for(int i = left;i <= right; ++i) tot[a[i]] = 0;
return res;
}
res = mx[p+1][q-1];
for(int i = left;i <= R[p]; ++i){
int it = w[i];
while(it + res < P[a[i]].size() && P[a[i]][it + res] <= right) ++res;
}
for(int i = L[q];i <= right; ++i){
int it = w[i];
while(it - res >= 0 && P[a[i]][it - res] >= left) ++res;
}
return res;
}
inline void solve(){
init();
int lastans = 0;
for(int i = 1,l,r;i <= m; ++i){
read(l,r);
l ^= lastans,r ^= lastans;
write(lastans = query(l,r));
pc('\n');
}
}
signed main(){
solve();
}
然后就可以拿这篇代码改一改水掉大爷的字符串题了