ARC075 E.Meaningful Mean（树状数组）-白红宇

ARC075 E.Meaningful Mean（树状数组）

阅读量：6698 次

发布时间：2019-06-25

本文共 1036 字，大约阅读时间需要 3 分钟。

题目大意：给定n和k，问an中有多少子区间的平均值大于等于k

很巧妙的一个式子，就是如果一个区间[l, r]满足条件

那么则有

sum[r] - sum[l-1] >= (r-l+1)*k

整理一下就是sum[r] - r*k >= sum[l-1] - (l-1)*k

然后先离散一下，用树状数组就可以了

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;typedef long long LL;const int maxn = 2e5 + 100;int n, k;LL a[maxn], c[maxn*4];map
          
            M;vector
           
             V;void Modify(int x, int s){ for(; x <= n; x += x&(-x)) c[x] += s;}LL Query(int y){ if(y <= 0) return 0; LL ans = 0; for(int x = y; x; x -= x&(-x)) ans += c[x]; return ans;}int main(){ int x; scanf("%d %d", &n, &k); for(int i = 1; i <= n; i++) scanf("%d", &x), a[i] = x; LL sum = 0; for(int i = 1; i <= n; i++) { sum += a[i]; sum -= k; V.push_back(sum); } sort(V.begin(), V.end()); for(int i = 0; i < V.size(); i++) M[V[i]] = i+1; sum = 0; LL ans = 0; for(int i = 1; i <= n; i++){ sum += a[i]; sum -= k; ans += Query(M[sum]); if(sum >= 0) ans++; Modify(M[sum], 1); } cout<
            
             <