【Ynoi2008】rsmemq
根号分治。
题目大意：
给定一个长度为 $n$ 的序列 $a$。
$m$ 组询问，每次给出 $l,r$，问有多少 $l’,r’$ 满足 $l\leq l’\leq r’\leq r$ 且 $r’-l’+1$ 是偶数，且 $\frac {l’+r’}2$ 是 $a_{l’},a_{l’+1},a_{l’+2},\ldots,a_{r’}$ 的众数。
题解：
$5\times 10^5$ 已成为常见的根号复杂度范围.jpg
本题可以分为两个部分，下面分别对其分析。
第一部分（预处理）
我们对每个不同的数值进行考虑。考虑当前的数为 $v$，它的出现次数为 $c$。
由于 $v$ 能产生贡献的区间的中点位置必须是 $v$，因此我们考虑枚举两个端点到中点的距离 $L$。$v$ 在区间的出现次数显然随着 $L$ 的增大而单调不降，且出现次数为 $0\sim c$。
我们再对 $v$ 的每个不同的出现次数进行考虑。对于 $v$ 出现了 $i$ 次，它对应的 $L$ 是连续的，设为区间 $[l,r]$。我们可以找到一个 $m\in[l-1,r]$ 满足当 $L\in[l,m]$ 时，$v$ 是区间的众数，而当 $L\in[m+1,r]$ 时，$v$ 不是区间的众数。证明很简单，这里略去。
因此我们可以使用二分来找到这个 $m$ 的值，从而能得出所有能产生贡献的 $L$ 的范围。由于总共有 $c$ 个不同的出现次数（$0$ 次不可能成为众数，故略去），因此可以得到 $c$ 个互不相交的范围。
由于二分的时候还需要求区间众数，因此对于一个 $v$，求它的 $L$ 的范围需要 $O(c\sqrt n\log n)$ 或 $O(c\sqrt{n\log n})$ 的时间复杂度。而所有的 $v$ 的 $c_v$ 的和为 $n$，因此这部分的总时间复杂度为 $O(n\sqrt n\log n)$ 或 $O(n\sqrt{n\log n})$。这个复杂度还不能接受。
考虑优化上述过程。
容易发现，$c_v\gt \sqrt n$ 的不同的 $v$ 最多有 $\sqrt n$ 个，这部分我们可以暴力枚举 $L$ 并进行判断，时间复杂度 $O(n\sqrt n)$（记得把连续的 $L$ 并成一个区间，否则空间复杂度将为 $O(n\sqrt n)$）。
而对于 $c_v\leq \sqrt n$ 的所有 $v$，我们不妨考虑枚举众数的出现次数。
假设当前众数的出现次数为 $(k-1)$，我们可以在 $O(n)$ 内求出 $p_{1..n}$，其中 $p_i$ 表示最小的满足 $[i,j]$ 的区间众数出现次数为 $k$ 的 $j$。
以下是求数组 $p$ 的方法：
可以证明 $a_{p_i}$ 是区间 $[i,p_i]$ 的唯一众数，否则 $[i,p_i-1]$ 的众数的出现次数也为 $k$。
同理，若 $a_i\neq a_{p_i}$，则 $[i+1,p_i]$ 的众数的出现次数也为 $k$。
我们对一个 $[i,p_i]$ 的左端点不断按此法向右移动，得到的 $[j,p_i]$ 会满足 $a_j=a_{p_i}$，即 $p_i$ 是位置 $j$ 之后第 $(k-1)$ 个 $a_j$。
考虑令 $q_i$ 表示 $i$ 之后第 $(k-1)$ 个 $a_i$ 的出现位置，那么对于一个 $i$，就有 $p_i=\min_{j>i} q_j$。
也就是说 $p_i$ 是 $q_i$ 的后缀 $\min$ 数组。
用 vector 按顺序存每个数值的出现位置，然后再对每个位置记一下它在 vector 里的下标，就可以 $O(1)$ 得到单个 $q_i$。
那么这部分的时间复杂度为 $O(n)$。
枚举可能的数值 $v$，并取出 $l,r$ 满足当且仅当 $L\in[l,r]$ 时，$v$ 的出现次数恰好为 $k$。
我们在上面提到了二分这个 $m$，在二分的时候，我们需要判断的其实是，是否存在一个区间 $[s,t]\in[v-m,v+m]$ 满足 $[s,t]$ 的区间众数大于等于 $k$。而我们只需要对所有的 $i\in[v-m,v+m]$ 检查：满足 $[i,j]$ 的众数出现次数恰好为 $k$ 的最小的 $j$ 是否大于 $v+m$，这个 $j$ 就是上面我们求出的 $p_i$。而由于 $p_i$ 具有单调性，因此我们只需要检查 $p_{v-m}$ 是否大于 $v+m$ 即可。因此单次检验是 $O(1)$ 的，一次二分的复杂度就是 $O(\log n)$。
由于所有的 $v$ 的 $c_v$ 总和为 $n$，因此这里的二分的次数不会超过 $n$ 次，时间复杂度为 $O(n\log n)$。
而我们需要对每个 $k\leq \sqrt n$ 计算对应的 $p$ 数组，因此这部分的时间复杂度是 $O(n\sqrt n)$。
第二部分（回答询问）。
我们接下来需要解决的问题如下：
给定不超过 $n$ 个三元组 $(v,x,y)$ 满足 $x\leq y$。对每个三元组，枚举 $i\in[x,y]$，并令 $A_{v-i,v+i}$ 增加 $1$。
$m$ 次询问，每次给定 $l,r$，求 $\sum\limits_{i=l}^r\sum\limits_{j=l}^r A_{i,j}$ 的值。
这个问题有多种做法，这里介绍一种较方便且容易理解的做法（感谢 memset0 提供了该做法的思路）。
上面这个二维的问题是比较容易想到的转化后的题意，不过我们还是直接讨论一个三元组 $(v,x,y)$ 对 $l,r$ 的贡献。
令 $a$ 为 $[v-y,v-x]\cap[l,r]$ 的长度，$b$ 为 $[v+x,v+y]\cap[l,r]$ 的长度，则贡献为 $\min(a,b)$。
令 $mid=\lfloor\frac{l+r}2\rfloor$，可以发现，当 $mid\leq v$ 时，总有 $a\geq b$，当 $mid\gt v$ 时，总有 $a\lt b$。
那么我们对 $mid\leq v$ 和 $mid\gt v$ 两种情况分开统计贡献即可。每种情况都是一个简单的二维数点问题，使用离线树状数组解决即可，时间复杂度 $O((n+m)\log n)$，空间复杂度 $O(n+m)$。
综上，算法的时间复杂度为 $O(n\sqrt n+m\log n)$，空间复杂度为 $O(n+m)$，可以通过本题。
Code：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,siz=450;
typedef long long LL;
int __MEMORY__[N],*__ITERATOR__=__MEMORY__;
class Vector{
int*__BEGIN__,*__END__,*__IT__;
public:
inline void INIT(int*a,int*b){__BEGIN__=__IT__=a,__END__=b;}
inline int*begin(){return __BEGIN__;}
inline int*end(){return __END__;}
inline int size(){return __IT__-__BEGIN__;}
inline int&operator[](const int&x){return __BEGIN__[x];}
inline void push_back(const int&x){*__IT__++=x;}
inline int&back(){return*__IT__;}
}pos[N];
int n,m,a[N],tot[N],rnk[N],q;
struct dat{
int m,l,r,I;
inline bool operator<(const dat&rhs)const{return m!=rhs.m?m<rhs.m:I<rhs.I;}
}D[2*N];
inline void add(int i,int l,int r,int tp=0){if(l<=r)D[++q]=(dat){i,l,r,tp};}
LL ans[N];
struct bit{
int B[N];LL C[N];
inline void add(int i,int x){for(int k=i;i<=n;i+=i&-i)B[i]+=x,C[i]+=(LL)k*x;}
inline LL ask(int i){LL x=0;for(int k=i;i;i&=i-1)x+=B[i]*(k+1LL)-C[i];return x;}
}b,c;
vector<dat>vec[siz+5];
void solve_leq_sqrt(){
for(int s=1;s<=siz;++s)if(vec[s].size()){
static int _r[N];
for(int i=1;i<=n;++i)if(rnk[i]+s<pos[a[i]].size())_r[i]=pos[a[i]][rnk[i]+s];else _r[i]=n+1;
for(int i=n-1;i;--i)_r[i]=min(_r[i],_r[i+1]);
for(dat it:vec[s]){
int l=it.l,r=it.r,m=it.m,res=l-1;
while(l<=r){
const int mid=(l+r)/2;
if(_r[m-mid]>m+mid)l=(res=mid)+1;else r=mid-1;
}
if(it.l<=res)add(m,it.l,res);
}
}
}
void solve(){
sort(D+1,D+q+1);
for(int i=1;i<=q;++i)if(D[i].I)ans[D[i].I]+=b.ask(D[i].r)-b.ask(D[i].l-1);
else b.add(D[i].m-D[i].r,1),b.add(D[i].m-D[i].l+1,-1);
for(int i=q;i;--i)if(D[i].I)ans[D[i].I]+=c.ask(D[i].r)-c.ask(D[i].l-1);
else c.add(D[i].m+D[i].l,1),c.add(D[i].m+D[i].r+1,-1);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i],rnk[i]=+tot[a[i]]++;
#define it __ITERATOR__
for(int i=1;i<=n;++i)pos[i].INIT(it,it+tot[i]),it+=tot[i];
#undef it
for(int i=1;i<=n;++i)pos[a[i]].push_back(i);
for(int i=1;i<=n;++i)if(tot[i]>siz){
static int cnt[N];
memset(cnt,0,sizeof(int)*(n+1)),cnt[a[i]]=1;
if(a[i]==i)add(i,0,0);
int mx=1,pre=1;
for(int len=1;;++len){
int l=i-len,r=i+len;
if(l<1||r>n){add(i,pre,len-1);break;}
++cnt[a[l]],++cnt[a[r]];
mx=max({mx,cnt[a[l]],cnt[a[r]]});
if(cnt[i]!=mx)add(i,pre,len-1),pre=len+1;
}
}else if(tot[i]){
Vector&v=pos[i];
static int sta[N];int top=0,lm=min(n+1-i,i);
for(int j=0,ed=v.size();j<ed;++j){
int x=abs(i-v[j]);
if(x<lm)sta[++top]=x;
}
sort(sta+1,sta+top+1),sta[++top]=lm;
for(int j=1;j<top;++j){
int l=sta[j],r=sta[j+1]-1;
if(l<=r)vec[j].emplace_back((dat){i,l,r});
}
}
solve_leq_sqrt();
for(int i=1,l,r;i<=m;++i)cin>>l>>r,add((l+r)/2,l,r,i);
solve();
for(int i=1;i<=m;++i)cout<<ans[i]<<'\n';
return 0;
}