「CodePlus 2017 11 月赛」Yazid 的新生舞会

Posted on Edited on In

「CodePlus 2017 11 月赛」Yazid 的新生舞会

最基本的分析这里只保留： \(cnt>\frac{len}{2}\Rightarrow 2cnt>len\)

对于每一个合法的区间，合法的众数显然只有一个

考虑对于每一个众数计算答案，把 \(x\) 出现的位置拿出来成一个序列 \(A_i\)

如果选择的区间恰好包含 \(A_i,A_{i+1},\cdots ,A_j\) ，那么合法的情况就是 \(2(j-i+1)>R-L+1,L\in[A_{i-1}+1,A_i],R\in[A_{j},A_{j},A_{j+1}-1]\)

参数分离得到 \(2j-R>2i-L\)

如果对于每一个 \(L\) 更新答案，那么更新的是一段区间，不妨设其为 \(UL,UR\)

对于每个 \(R\) 查询则是一段前缀 和 的区间

我们知道树状数组维护区间修改区间查询需要做一次差分，而这次是区间前缀和

也就是说是再高一维。。

不妨在 \(UL\) 上加, \(UR\) 上减，那么在 \(p\) 处的更新对于在 \(k\) 处的查询的贡献是

\(\cfrac{(k-p+1)(k-p+2)}{2}=\cfrac{k^2+p^2-2pk+3k-3p+2}{2}\)

那么直接处理这个式子即可，需要维护 \(updval,p\cdot updval,p^2\cdot updval\)

查询时加入 \(k\) 的贡献

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
int rd(){
	int s=0; char c;
	while(c=getchar(),c<48);
	do s=s*10+c-'0';
	while(c=getchar(),c>47);
	return s;
}
enum{N=1000010};
int n;
vector <int> A[N];
ll ans,s1[N],s2[N],s3[N];
void Add(int p,ll x) {
	p--; ll a=x,b=x*p,c=x*p*p;
	for(p+=n+1;p<=n*2;p+=p&-p) s1[p]+=a,s2[p]+=b,s3[p]+=c;
}
void Add(int l,int r,int x) { Add(l,x),Add(r+1,-x); }
ll Que(int p) {
	ll r1=0,r2=0,r3=0,tp=p;
	for(p+=n;p;p-=p&-p) r1+=s1[p],r2+=s2[p],r3+=s3[p];
	return ((tp*tp+tp)*r1-(2*tp+1)*r2+r3)/2;
}
ll Que(int l,int r) { return Que(r)-Que(l-1); }
int main(){ 
	freopen("party.in","r",stdin),n=rd(),rd();
	rep(i,1,n) A[rd()].push_back(i);
	rep(k,0,n-1) if(A[k].size()) {
		rep(i,0,A[k].size()-1) {
			int p=A[k][i],l=i?A[k][i-1]:0,r=i<(int)A[k].size()-1?A[k][i+1]:n+1;
			Add(2*i-p+1,2*i-l,1);
			ans+=Que(2*(i+1)-r,2*(i+1)-p-1);
		}
		rep(i,0,A[k].size()-1) {
			int p=A[k][i],l=i?A[k][i-1]:0;
			Add(2*i-p+1,2*i-l,-1);
		}
	}
	fprintf(fopen("party.out","w"),"%lld\n",ans);
}