[hdu7020]Array

(这是一个线性的做法)

显然对于合法的区间,众数是唯一的,因此不妨枚举众数,将众数标记为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)$,可以通过

[hdu7020]Array
 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

 

上一篇:关于最短路


下一篇:NOIP 模拟30