例题传送门：P4062 [Code+#1] Yazid 的新生舞会
简要题意：给定一串序列\(A_1,A_2,...,A_n\)，求有多少个子区间\([l,r]\)满足子区间内众数的个数大于\(\frac{r-l+1}{2}\)
思考若数\(w\)是众数的方案数：新建一个序列\(B\)，令\(B_i=[A_i=w]\)，考虑前缀和\(S_i=\sum\limits_{k=1}^iB_i=S_{i-1}+B_i\)，则对于子区间\([l+1,r]\)，若\(S_r-S_l>\frac{r-l}{2}\)，则数\(w\)是子区间\([l+1,r]\)的众数，转换一下该不等式为：\(2S_r-r>2S_l-l\)，则可以线性求\(2S_i-i\)，可以用树状数组寻找小于\(2S_r-r\)的数，则求数\(w\)是众数的方案数时间复杂度为\(O(n \log n)\)。
因为\(0 \le A_i \le n-1\)，所以用该方法时间复杂度为\(O(n^2 \log n)\)
这样还不够，还要优化。
如上图，我们发现：\(2S_i-i\)是由一个个等差数列组成的，而等差数列的个数为原序列中\(1\)的个数\(+1\)，也就是\(A_i=w\)的个数\(+1\)，所以一共有的等差数列的个数不超过\(2n\)个，我们可以考虑从这里入手优化:只要我们快速求出一个等差数列对答案的贡献就好了
还有一个可以思考的点：\(P_i\in [-n,n]\)
因为负数不太好计算，所以我们令所有\(P_i\)加上\(n+1\)，即\(P_i\in [1,2n+1]\)
考虑差分计数（即\(p_1+p_2+...p_i\)表示\(P_i\)的出现次数，下同），记\(\sum\limits_{k=1}^ip_k\)为\(P_i\)的出现次数，对于等差数列\(le,le+1,...,ri-1,ri\)，令\(p_{le}++,p_{ri+1}--\)
考虑差分计数，记\(\sum\limits_{k=1}^itr_k\)为\(P_1\sim P_i\)出现次数和，则可以推出\(tr_i=\sum\limits_{j=1}^ip_j\)
考虑差分计数，记\(\sum\limits_{k=1}^ia_k\)为\(P_1,P_1\sim P_2,P_1\sim P_3...P_1\sim P_i\)的出现次数的和，则可以推出\(a_i=\sum\limits_{j=1}^itr_j\)
考虑求\(P_1\sim P_{le},P_1\sim P_{le+1}...P_1\sim P_{ri-1},P_1\sim P_{ri}\)出现次数的和，即求\(\sum\limits_{i=1}^{ri}a_i-\sum\limits_{i=1}^{le-1}a_i\)
理论上说只要我们会求快速求\(\sum\limits_{i=1}^xa_i\)就可以了
转换一下原式，把\(p_k\)提到前面来：
把多项式按照拆开来，整理一下为：
只要我们用树状数组记录\(p_k,p_k\times k,p_k\times k^2\)，就可以在\(O(\log n)\)时间复杂度内求出\(\sum\limits_{i=1}^xa_i\)
插入时也是\(O(\log n)\)的时间复杂度（树状数组单点修改\(p_{le},p_{ri+1}\)）
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=5e5+50;
ll n,type,a,le,ri,last,ans,en;
vector<ll> e[N];
ll tr[N*2],tr1[N*2],tr2[N*2];
ll lb(ll x)
{
return x & -x;
}
void add(ll wz,ll x)
{
ll now=wz;
while(wz<=en)
{
tr[wz]=tr[wz]+x;
tr1[wz]=tr1[wz]+x*now;
tr2[wz]=tr2[wz]+x*now*now;
wz+=lb(wz);
}
}
ll query(ll wz)
{
ll re=0,now=wz;
while(wz>0)
{
re=re+now*now*tr[wz]+3*now*tr[wz]+2*tr[wz];
re=re+tr2[wz];
re=re-3*tr1[wz]-2*now*tr1[wz];
wz-=lb(wz);
}
return re/2;
}
int main()
{
scanf("%lld %lld",&n,&type);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&a);
e[a].push_back(i);
}
en=2*n+1;
for(ll i=0;i<n;i++)
{
e[i].push_back(n+1);
ri=n+1;//[-n,n]->[1,2n+1]
last=1;
for(ll j=0;j<e[i].size();j++)
{
le=ri-(e[i][j]-last);
ans=ans+query(ri-1)-query(le-2);
add(le,1);
add(ri+1,-1);
ri=le+1;
last=e[i][j]+1;
}
ri=n+1;
last=1;
for(ll j=0;j<e[i].size();j++)
{
le=ri-(e[i][j]-last);
add(le,-1);
add(ri+1,1);
ri=le+1;
last=e[i][j]+1;
}
}
printf("%lld\n",ans);
return 0;
}
总结一下：
1，只需要\(n\)个树状数组就可以求出\(n\)阶前缀和
2，遇到这种很有规律的计数题，不一定要直接计数，可以考虑差分计数，最后再用\(n\)阶前缀和快速求出即可