CSP模拟 小 trick 总结 （持续施工中）
虽然这篇博客来的有点晚，但还是写了，欢迎dalao补充（
1、分块、莫队有关：
(1):一个真正的回滚莫队（感谢 Qyun 的讲解）
$\ \ \ \ \ \ \ \ $学习回滚莫队的时候，我们经常会在回滚时使用memcpy来恢复以前的版本，但众所周知--memset和memcpy常数巨大，破坏了莫队 $ O(n \sqrt n) $ 的时间复杂度，导致TLE。
$\ \ \ \ \ \ \ \ $但对于一些可以进行del操作，只是不好改变答案的回滚（比如求一个区间的众数），直接记下来回滚版本的ans，然后进行del操作，因为块长为 $ \sqrt n $ ，所以每次最多进行 $ \sqrt n $ 次操作，总时间复杂度$ O(n \sqrt n) $
----例题：洛谷 P3709
MAN
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define ps push_back
#define mk make_pair
#define rint register int
#define G cout<<"-------------------"<<endl
inline ll read(){
char c=getchar();ll x=0,f=1;
while(!isdigit(c))(c=='-'?f=-1:0),c=getchar();
while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int N=2e5+3,inf=0x7fffffff;
const ll linf=0x3f7f7f7f7f7f7f7f,mod=1e9+7;
int n,a[N],cnt[N],b[N],ans,anss[N],m,zh[N],cntp,len,st[N],ed[N];
struct jj{
int l,r,id;
inline bool operator <(const jj&x)const{
if(zh[l]==zh[x.l])return r<x.r;
return zh[l]<zh[x.l];
}
}q[N];
int main(){
// #ifndef ONLINE_JUDGE
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
// #endif
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
n=read(),m=read();
len=pow(n,0.5),cntp=n/len;
for(int i=1;i<=cntp;++i){
st[i]=ed[i-1]+1,ed[i]=ed[i-1]+len,ed[cntp]=n;
for(int j=st[i];j<=ed[i];++j)
zh[j]=i;
}
for(int i=1;i<=n;++i)
b[i]=a[i]=read();
sort(b+1,b+1+n);
int n1=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;++i)
a[i]=lower_bound(b+1,b+1+n1,a[i])-b;
for(int i=1,l,r;i<=m;++i){
l=read(),r=read();q[i]={l,r,i};
}
sort(q+1,q+1+m);
int l1=0,r1=0;int la=0;
for(int i=1,l,r;i<=m;++i){
// cout<<i<<endl;/
l=q[i].l,r=q[i].r;
if(zh[l]==zh[r]){
fill(cnt+1,cnt+1+n1,0);ans=0;
for(int j=l;j<=r;++j)
ans=max(ans,++cnt[a[j]]);
anss[q[i].id]=ans;
continue;
}
if(zh[l]!=zh[q[i-1].l]||zh[q[i-1].l]==zh[q[i-1].r]){
fill(cnt+1,cnt+1+n1,0);
l1=ed[zh[l]],r1=l1-1;ans=la=0;
}
while(r1<r)ans=max(ans,++cnt[a[++r1]]);
// memcpy(zan,cnt,4*(n1+1));
la=ans;
while(l1>l)ans=max(ans,++cnt[a[--l1]]);
anss[q[i].id]=ans;
ans=la;while(l1<ed[zh[l]])--cnt[a[l1++]];
}
for(int i=1;i<=m;++i)
cout<<-anss[i]<<'\n';
}