题目链接
题链
题解
区间众数的个数 区间长度一半 称这个区间有主元素,主元素就是这个众数;
题意:求数组中有多少个区间有主元素;
考虑一个子问题:每一种数作为主元素的贡献;
例如给定数组 ,并考虑 作为主元素的贡献;
我们可以将是数字 的记为 ,不是的记为 ;
于是子问题变成求 中有多少个区间和大于 ,例如区间 的和为 ,所以这个区间可行,而区间 的和为 ,所以这个区间不可行;
我们对 求一个前缀和,记为 ,如果 ,也就是对于 查找 之前有多少个比 小的数字,那么区间 满足要求;
例如对于 , 前比 小的数字有 个,分别是 的时候,也就是区间 满足要求;
于是可以对每一种数字,求出 ,求出 ,枚举 ,查找 前有多少个比 小的数字,用树状数组维护权值,显然这样的复杂度是 的,不可取;
我们记录下每一种数字在数组中的位置,例如数字 ,它的位置有 ,如果能在 的时空复杂度下(可以加个)求出这种数字的贡献,那么枚举每一种数字算贡献整体就是 的了;
是连续的, 可以将 分为 个部分,分别是 ,这四个部分都是等差数列,对于区间内的每个值,在该值前且比该值小的数字只能来自于这部分之前,不能来自于 这部分本身;
设法将每一部分同时处理,如有一部分 ,这部分的答案来自于 之前的部分,对 这部分是一个等差数列 ,那么 部分插入到树状数组中就是区间 加 ;
设 为权值的前缀和,,那么对于 部分内的每一个值 , 的贡献就等于 ,那么对于这一整个部分 ,值为 ,整体贡献就是 ,设 为权值的前缀和的前缀和,也就是 的前缀和 ,那么整体贡献就是 ;
于是将问题转变为了,区间 加 ,和求二阶前缀和;
区间 加一个数,求一阶前缀和就是区间加数,区间求和的洛谷线段树模板题1,当然可以用树状数组实现;
和模板题同样将权值 差分,差分后的数组位 ,于是问题转变为单点修改,求三阶前缀和;
用三个树状数组维护 ,,即可;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| #include <bits/stdc++.h> using namespace std; #define LL long long #define MS 2000009
LL n,m; LL a[MS]; vector<LL > vc[MS]; LL b[MS], tot; LL p[4][MS]; LL ans;
LL lowbit(LL x){ return x&(-x); }
void add(LL pos, LL val){ for(LL x=pos;pos<MS;pos+=lowbit(pos)){ p[1][pos] += x*x*val; p[2][pos] += x*val; p[3][pos] += val; } }
LL query(LL pos){ LL ans = 0; for(LL x=pos;pos;pos-=lowbit(pos)){ ans += p[1][pos]; ans += (-2*x-3)*p[2][pos]; ans += (x*x+3*x+2)*p[3][pos]; } return ans/2; }
void clear(){ for(LL i=1;i<=tot;i++) vc[b[i]].clear(); tot = 0; ans = 0; }
void solve(){ cin >> n >> m; for(LL i=1;i<=n;i++){ cin >> a[i]; if(vc[ a[i] ].empty()){ vc[ a[i] ].push_back(0); b[++tot] = a[i]; } vc[ a[i] ].push_back(i); } LL dis = n+1; for(LL i=1;i<=tot;i++){ LL t = b[i]; vc[t].push_back(n+1); LL l, r = -1, len = vc[t].size(); for(LL j=1;j<len;j++){ l = r+1; r = l-(vc[t][j]-vc[t][j-1]-1); LL L = r+dis, R = l+dis; ans += query(R-1) - (L-2>0? query(L-2):0); add(L, 1); add(R+1, -1); } r = -1; for(LL j=1;j<len;j++){ l = r+1; r = l-(vc[t][j]-vc[t][j-1]-1); LL L = r+dis, R = l+dis; add(L, -1); add(R+1, 1); } } cout << ans << "\n";
clear();
}
int main(){ ios::sync_with_stdio(false); LL ce; ce = 1; while(ce--){ solve(); }
return 0; }
|