题解：CF2056D Unique Median

首先，对于所有长度为奇数的子串，一定是好的子串，我们可以直接预处理出来。

对于长度为偶数的子串，我们可以观察到

a

的数据范围只有

10

，一个暴力的思想就是直接枚举子串的中位数

i

，然后统计子串个数。

我们假设一个子串小于

i

的数的个数为

a

，等于

i

的数的个数为

b

大于

i

的数的个数为

c

，那么一个好的子串需要满足：

\frac{(a+b+c)}{2} \le a+b

a<\frac{(a+b+c)}{2}

我们将式子拆开，发现

a

，

b

，

c

并不好处理，也很难统计，所以我们可以换个思路，应用容斥思想，统计以

i

为其中一个中位数但不是好子串的个数。

假设，有

a

个数小于等于

i

，

b

个数大于

i

，对于我们要统计的两个条件：

以 $i$ 为其中一个中位数： $i$ 要在子串中出现过，且 $\frac{(a+b)}{2} \le a$
这个子串不是好子串，也就是排序后第 $(a+b)/2+1$ 为不等于 $i$ 。 $a<\frac{(a+b)}{2}+1$

这个式子列出来，我们就可以发现，其实我们要统计的子串就是小于等于

i

的数出现恰好

\frac{(a+b)}{2}

次且

i

出现过的子串。

我们可以借助前缀和和桶统计答案。

最后，ACcode：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200010
#define N 100000
// By flyfreemrn
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void write(ll x){
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
ll T,n,a[MAXN],t[MAXN],ans;
ll work(ll p){
//	memset(t,0,sizeof(t)); 不能直接清空桶，会TLE
	ll now=N,res=0;//赋初始值N，防止now<0时越界
	queue<ll> q,_q;//q暂存桶数据，_q负责清空桶
	q.push(N);
	for(int i=1;i<=n;i++){
		if(a[i]<=p)now++;
		else now--;//前缀和统计当前位置小于等于i的数和大于i的数的数量关系
		if(a[i]==p){
			while(!q.empty()){//发现和p相同的数，这时队列中的数据可以添加到桶中在之后被查询
				ll fnt=q.front();
				_q.push(fnt);
				q.pop();
				t[fnt]++;
			}
		}
		res+=t[now];
	 	q.push(now);//因为我们要保证子串存在p，所以要暂存数据
	}
	while(!_q.empty()){//清空桶
		ll fnt=_q.front();
		_q.pop();
		t[fnt]=0;
	}
	return res;
}
int main(){
	T=read();
	while(T--){
		n=read();
		ans=0;
		for(int i=1;i<=n;i++)a[i]=read(),ans+=i;//处理所有子串
		for(int i=1;i<=10;i++){
			ans-=work(i);//容斥
//			cout<<i<<" "<<work(i)<<endl;
		}
		cout<<ans<<endl;
	}
	return 0;
}

题解：CF2056D Unique Median

文章操作

相关推荐

评论

题解：CF2056D Unique Median