题解 P2717 【寒假作业】

## 平衡树 看到平均数首先转化一下，变成$a[i]-k$ 然后发现只要区间和是非负数就是合法区间 所以对于$[i,j]$满足$s_j-s_{i-1}>=0$即可 那么再做前缀和，对于$i∈[0,n)$的每个$i$统计$j>i$且$s_j>=s_i$的个数 然后发现区间统计排名，可以平衡树来做 于是就快乐的拿平衡树过了这题 说句闲话：研究作业的最好方法就是 A了这道题 祝你们成功（滑稽 ```cpp #include<bits/stdc++.h> #define maxn (100000+500) #define int long long using namespace std; int R=0,sz[maxn],son[maxn][2],rd[maxn],num[maxn],v[maxn],tot=0,n,k,a[maxn],s[maxn]; void pushup(int p) { sz[p]=sz[son[p][0]]+sz[son[p][1]]+num[p]; } void rotate(int &p,int d) { int k=son[p][d^1]; son[p][d^1]=son[k][d],son[k][d]=p; pushup(p),pushup(k),p=k; } void ins(int &p,int x) { if (!p) p=++tot,sz[p]=num[p]=1,v[p]=x,rd[p]=rand(); else if (v[p]==x) sz[p]++,num[p]++; else { int d=(x>v[p]); ins(son[p][d],x); if (rd[p]<rd[son[p][d]]) rotate(p,d^1); pushup(p); } } int rank(int p,int x) { if (!p) return 0; if (v[p]==x) return sz[son[p][0]]+1; else if (v[p]<x) return sz[son[p][0]]+num[p]+rank(son[p][1],x); else return rank(son[p][0],x); } signed main() { srand(time(0)); scanf("%lld%lld",&n,&k); for (int i=1;i<=n;++i) scanf("%lld",&a[i]),a[i]-=k; for (int i=1;i<=n;++i) s[i]=s[i-1]+a[i]; ins(R,s[n]); int Ans=0; for (int i=n-1;i>=0;--i) { ins(R,s[i]); int rk=rank(R,s[i]); Ans+=(n-i+1)-rk; } printf("%lld\n",Ans); return 0; } ```