【AtCoder Regular Contest 075 E】Meaningful Mean | Mrsrz's blog

平衡树。

题目大意：

给定一个数列，再给定整数 $k$，问有多少区间的平均数大于等于 $k$。

题解：

我们先对所有数减去 $k$，那么相当于问有多少区间的和大于等于 $0$。

我们令右端点从小到大，每次向右移动时，对每个左端点对应的区间都加上了同一个数。然后插入这个端点本身，查询有多少个数大于等于 $0$。

可以直接使用平衡树实现。

全局加可以直接打标记，然后只剩下查询 rank 的操作，所以可以使用 pbds 的 tree。

时间复杂度 $O(n\log n)$。

Code：

#include<iostream>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<long long,int>,null_type,less<pair<long long,int>>,rb_tree_tag,tree_order_statistics_node_update>rbt;
rbt s;
int n,a,k,tot;long long tag,ans;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>a,a-=k;
        tag+=a;
        s.insert(make_pair(a-tag,++tot));
        ans+=i-s.order_of_key(make_pair(-tag,0));
    }
    cout<<ans;
    return 0;
}