（这是一个线性的做法）
显然对于合法的区间，众数是唯一的，因此不妨枚举众数，将众数标记为1、其余数标记为-1，此时问题即求有多少个区间和大于0
考虑暴力的做法：从左到右枚举右端点，记当前前缀和为$tot$，即查询之前有多少个前缀和小于$tot$
具体的，记$f_{i}$为（当前）有多少个前缀和为$i$，即查询$\sum_{i=\min }^{tot-1}f_{i}$，并将$f_{tot}$加1
（其中$\min$为历史前缀最小值，初始为$f_{0}=1$且$\forall i\ne 0,f_{i}=0$）
由于$tot$的变化是连续的，不难线性维护$\sum_{i=\min}^{tot-1}f_{i}$，时间复杂度为$o(n^{2})$
进一步的，注意到1的个数和是$o(n)$的，-1的段数和也是$o(n)$的，因此将连续的一段-1一起处理
具体的，考虑处理一段-1，假设这段-1之前的前缀和为$tot$，这段-1的长度为$l$，即查询$\sum_{i=tot-l}^{tot-1}\sum_{j=\min}^{i-1}f_{j}$，并将$\forall tot-l\le i<tot,f_{i}$加1
对于修改，可以通过差分维护，并记差分数组为$\Delta f_{i}$（定义$f_{i}=\sum_{j=\min}^{i}\Delta f_{j}$）
对于查询，不妨暴力枚举$tot$，同样利用$tot$变化的连续性，线性维护$\sum_{j=\min}^{tot}\Delta f_{j}$和$\sum_{j=\min}^{tot-1}f_{j}$，那么不难得到查询的结果（$tot$暴力枚举即代替了$i$），但时间复杂度仍为$o(n^{2})$
考虑$\min$，显然当$tot\le \min$时之后的部分必然都为0，不妨直接变为最终的$tot-l$（注意更新$\min$）
考虑此时的复杂度，注意到每一次$mn$减少，都会减少对应$tot$的枚举，而最终$mn$至多为所有元素和，因此$tot$的枚举级别是1的个数，也即$o(n)$的
对于单个1直接暴力"枚举"$tot$即可，显然是$o(n)$的
最终，总复杂度为$o(n)$，可以通过
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 1000005
4 #define ll long long
5 stack<int>st;
6 vector<int>v[N];
7 int t,n,m,x,now,mn,cnt,s,f[N<<1];
8 ll ans;
9 void update(int l,int r){
10 f[l]++,f[r+1]--;
11 st.push(l),st.push(r+1);
12 cnt++;
13 }
14 void dec(int x){
15 for(int i=0;i<x;i++){
16 if (now==mn){
17 now=mn=now-(x-i);
18 cnt=s=0;
19 return;
20 }
21 cnt-=f[now--],s-=cnt,ans+=s;
22 }
23 }
24 int main(){
25 scanf("%d",&t);
26 while (t--){
27 scanf("%d",&n);
28 m=1e6,ans=0;
29 for(int i=0;i<=m;i++)v[i].clear();
30 for(int i=1;i<=n;i++){
31 scanf("%d",&x);
32 v[x].push_back(i);
33 }
34 for(int i=0;i<=m;i++){
35 int lst=0;
36 now=mn=n,cnt=s=0;
37 update(now,now);
38 //cnt=\sum_{i=mn}^{tot}f_{i},s=\sum_{i=mn}^{tot-1}\sum_{j=mn}^{i}f_{j}
39 for(int j=0;j<v[i].size();j++){
40 if (lst+1<v[i][j]){
41 dec(v[i][j]-lst-1);
42 update(now,now+(v[i][j]-lst-1)-1);
43 }
44 s+=cnt,cnt+=f[++now],ans+=s;
45 update(now,now);
46 lst=v[i][j];
47 }
48 if (lst<n)dec(n-lst);
49 while (!st.empty()){
50 f[st.top()]=0;
51 st.pop();
52 }
53 }
54 printf("%lld\n",ans);
55 }
56 return 0;
57 }
View Code