P2717 寒假作业

$Hyperlink$

https://www.luogu.org/problem/P2717

$Description$

给定一个长度为$n$的序列$A$，求区间平均值不小于$k$的连续子序列个数

n ≤ 1 0 5 , A i ≤ 1 0 4 , k ≤ 1 0 4 n\leq 10^5,A_i\leq 10^4,k\leq 10^4 n≤105,Ai​≤104,k≤104

$Solution$

设选择的区间是$i\sim j$，这里$i<j$，则

∑ p = i j a p j − i + 1 ≥ k \dfrac {\sum_{p=i}^j a_p}{j-i+1}\geq k j−i+1∑p=ij​ap​​≥k

移项

∑ p = i j a p ≥ k ( j − i + 1 ) \sum_{p=i}^j a_p\geq k(j-i+1) p=i∑j​ap​≥k(j−i+1)

即

∑ p = i j a p ≥ ∑ p = i j k \sum_{p=i}^j a_p\geq \sum_{p=i}^j k p=i∑j​ap​≥p=i∑j​k

移项

∑ p = i j ( a p − k ) ≥ 0 \sum_{p=i}^j(a_p-k)\geq 0 p=i∑j​(ap​−k)≥0

令 a p = a p − k a_p=a_p-k ap​=ap​−k， s i = ∑ j < = i a j s_i=\sum^{j<=i} a_j si​=∑j<=iaj​

于是
$$s[j]-s[i-1]\ge 0$$

于是
$$s[j]\ge s[i-1]$$

于是树状数组求顺序对，复杂度$O(nlogn)$

细节：

1. 由于 a i − k a_i-k ai​−k可能小于0，而树状数组莫得小于0的操作，所以要离散化，这也是后面那个$log$的上限是 1 0 5 10^5 105而不是 1 0 4 10^4 104的原因
2. 注意求顺序对的时候是包括$s[0]$的

$Code$

#include
#include
#include
#define LL long long
#define lb(x) x&-x
using namespace std;int n,k,a[100001],c[100001],s[100001],b[100001];
LL ans; 
inline void add(int x){for(;x<=n;x+=lb(x)) c[x]++;return;}
inline int get(int x){int s=0;for(;x;x-=lb(x)) s+=c[x];return s;}
inline LL read()
{char c;LL f=0,d=1;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{n=read();k=read();for(register int i=1;i<=n;i++) a[i]=read()-k,b[i]=s[i]=s[i-1]+a[i];sort(b,b+1+n);int tot=unique(b,b+1+n)-b-1;for(register int i=0;i<=n;i++) s[i]=lower_bound(b,b+1+tot,s[i])-b+1;add(s[0]);for(register int i=1;i<=n;i++){ans+=get(s[i]);add(s[i]);}printf("%lld",ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！