给侧栏加了音乐播放器，其实一般，不过一般也没人会打开吧。
把序列和区间都分块。
对于整块区间，我们发现若区间有包含关系，则小区间一定对答案没贡献，忽略他们后顺序暴力做完取 $\max$ 就是 $\text{O}(n)$ 的了。
具体地，对于每个整块，拿一个双指针 $l,r$ 并记录每个数字在这个区间的次数，每个数字的历史最大，所以用了 $\text{O}(\sqrt{n})$ 做完一个整块，总共有 $\text{O}(\sqrt{n})$ 个块，做完就是 $O(n)$ 的，然后每次做完一个整块，我们暴力 $O(q)$ 枚举所有包含当前块的询问去贡献。这就是一个平衡，我们最后是 $O(n+q\sqrt{n})$ 完成了整块的贡献。
对于散块，我们枚举 $k$，假设有一个新的序列 $f_i$，我们在 $f_i$ 上激活所有 $[a_i=k]$，也就是 $f_i=[a_i=k]$。因为是散块，外面肯定是暴力枚举的 $O(\sqrt{n})$ 枚举数字又有一个 $O(n)$ 了，所以我们要做到 $O(1)$ 查询一个区间内 $[a_i=k]$ 的个数，这里就用到对序列的分块了，分块是可以做到 $O(\sqrt{n})$ 修改 $O(1)$ 查询前缀和的，修改在每次枚举的时候做，所以就是 $O(n\sqrt{n})$ 的了。
卡常前的代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <time.h>
#include <iostream>
#define reg register
#define rep(i,a,b) for(reg int i=a;i<=b;++i)
#define drep(i,a,b) for(reg int i=a;i>=b;--i)
#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define Pqry(x) (x==0?x:h[Srev[x]-1]+f[x])
#define pb emplace_back
#define ins insert
namespace Fread {
const int SIZE=1<<21;char buf[SIZE],*S,*T;
inline char getchar() {if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite {
const int SIZE=1<<21;
char buf[SIZE],*S=buf,*T=buf+SIZE;
inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
inline void putchar(char c){*S++=c;if(S==T)flush();}
struct POPOSSIBLE{~POPOSSIBLE(){flush();}}ztr;
}
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
namespace Fastio{
struct Reader{
template<typename T>
Reader& operator >> (T& x) {
char c=getchar();T f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}x=0;
while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}x*=f;
return *this;
}
Reader(){}
}cin;
struct Writer{
template<typename T>
Writer& operator << (T x) {
if(x==0){putchar('0');return *this;}
if(x<0){putchar('-');x=-x;}
static int sta[45];int top=0;
while(x){sta[++top]=x%10;x/=10;}
while(top){putchar(sta[top]+'0');--top;}
return *this;
}
Writer& operator << (char c) {putchar(c);return *this;}
Writer(){}
}cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
const int N=2e5+10;
inline void chmax(reg int &x,reg int y){if(x<y)x=y;}
int n,m,q;
int a[N];
int t[N],h[N],f[N];
struct OP{
int l,r;
}it[N];
const int intervalB=600,sequentialB=430,ICOST=N/intervalB+10,SCOST=N/sequentialB+10;
int Irev[N],Il[ICOST],Icnt=0;
int Srev[N],Sl[SCOST],Scnt=0;
std::vector<int>F[N],T[N];
int ans[N];
struct QUETY{
int l,r,x;
}Q[N];
int L,R,tmp,now,rmx,tcnt;
signed main(){
cin>>n>>m>>q;
rep(i,1,n)cin>>a[i],F[a[i]].pb(i);
rep(i,1,m)cin>>it[i].l>>it[i].r;
rep(i,1,q)cin>>Q[i].l>>Q[i].r>>Q[i].x,T[Q[i].x].pb(i);
rep(i,1,m){
now=(i-1)/intervalB+1;Icnt=Irev[i]=now;
if(!Il[now])Il[now]=i;
}
Il[Icnt+1]=m+1;
rep(i,1,n){
now=(i-1)/sequentialB+1;Scnt=Srev[i]=now;
if(!Sl[now])Sl[now]=i;
}
Sl[Scnt+1]=n+1;
for(reg int k=1;k<=Icnt;++k){
rep(i,Il[k],Il[k+1]-1)h[i]=i;
std::sort(h+Il[k],h+Il[k+1],[](int &x,int &y){return it[x].l==it[y].l?it[x].r>it[y].r:it[x].l<it[y].l;});
rmx=tcnt=0;
rep(i,Il[k],Il[k+1]-1)if(it[h[i]].r>rmx)rmx=it[h[i]].r,f[++tcnt]=h[i];
rep(i,1,n)h[i]=t[i]=0;
L=1,R=0;
rep(i,1,tcnt){
while(L<it[f[i]].l)t[a[L++]]--;
while(R<it[f[i]].r)t[a[++R]]++,chmax(h[a[R]],t[a[R]]);
}
rep(i,1,q)if(Q[i].l<=Il[k]&&Il[k+1]-1<=Q[i].r)chmax(ans[i],h[Q[i].x]);
}
rep(i,1,n)h[i]=f[i]=0;
rep(k,1,n){
for(auto it:F[k]){
rep(i,it,Sl[Srev[it]+1]-1)f[i]+=1;
rep(i,Srev[it],Scnt)h[i]+=1;
}
for(auto qid:T[k]){
L=Q[qid].l,R=Q[qid].r,tmp=0;
if(Irev[L]+1>=Irev[R]){
rep(i,L,R)chmax(tmp,Pqry(it[i].r)-Pqry(it[i].l-1));
}else{
rep(i,L,Il[Irev[L]+1]-1)chmax(tmp,Pqry(it[i].r)-Pqry(it[i].l-1));
rep(i,Il[Irev[R]],R)chmax(tmp,Pqry(it[i].r)-Pqry(it[i].l-1));
}
chmax(ans[qid],tmp);
}
for(auto it:F[k]){
rep(i,it,Sl[Srev[it]+1]-1)f[i]-=1;
rep(i,Srev[it],Scnt)h[i]-=1;
}
}
rep(i,1,q)cout<<ans[i]<<'\n';
return 0;
}
数据生成器：
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
inline int big_rand(int mod) {
long long rnd = (1LL * rand() << 15) | rand();
return rnd % mod;
}
signed main(int argc, char* argv[]) {
int n = 200000, m = 200000, q = 200000;
unsigned seed = time(0);
if (argc >= 4) {
n = atoi(argv[1]);
m = atoi(argv[2]);
q = atoi(argv[3]);
if (argc >= 5) seed = atoi(argv[4]);
}
srand(seed);
fprintf(stderr, "Random seed: %u\n", seed);
printf("%d %d %d\n", n, m, q);
for (int i = 0; i < n; ++i) {
printf("%d%c", big_rand(n) + 1, (i == n - 1) ? '\n' : ' ');
}
for (int i = 0; i < m; ++i) {
int l = big_rand(n) + 1;
int r = big_rand(n) + 1;
if (l > r) swap(l, r);
printf("%d %d\n", l, r);
}
for (int i = 0; i < q; ++i) {
int L = big_rand(m) + 1;
int R = L + big_rand(m - L + 1);
int k = big_rand(n) + 1;
printf("%d %d %d\n", L, R, k);
}
return 0;
}