正題

題目鏈接:https://www.luogu.com.cn/problem/P2717

---

題目大意

$n$個數(shù)，求有多少個連續(xù)子序列的平均值大于等于$k$。

---

解題思路

因為長度會十分干擾，所以我們將所有數(shù)減去$k$。問題就變?yōu)榱饲笥卸嗌龠B續(xù)子序列的和非負(fù)。用前綴和+逆序?qū)η缶秃昧恕?/p>

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define lowbit(x) (x&-x) using namespace std; const ll N=1e5+10; ll n,k,a[N],b[N],t[N],ans; void change(ll x,ll num) {while(x<=n)t[x]+=num,x+=lowbit(x);return; } ll ask(ll x) {ll ans=0;while(x)ans+=t[x],x-=lowbit(x);return ans; } int main() {scanf("%lld%lld",&n,&k);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1]-k,b[i]=a[i];b[n+1]=0;sort(b+1,b+2+n);ll m=unique(b+1,b+2+n)-b-1;change(lower_bound(b+1,b+1+m,0)-b,1);for(ll i=1;i<=n;i++){a[i]=lower_bound(b+1,b+1+m,a[i])-b;ans+=ask(a[i]);change(a[i],1);}printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的P2717-寒假作业【逆序对,树状数组】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。