首页 > 代码库 > AtCoder Regular Contest 075 E - Meaningful Mean 树状数组求顺序对， 前缀和

AtCoder Regular Contest 075 E - Meaningful Mean 树状数组求顺序对， 前缀和

2024-09-30 11:14:38   213人阅读

题目链接:

http://arc075.contest.atcoder.jp/tasks/arc075_c

题意：

给你一个序列和一个数k，求有多少对l，r，使得a[l]+a[l+1]+...+a[r]的算术平均数大于等于k

  • 1≤N≤2×10^5
  • 1≤K≤10^9
  • 1≤ai≤10^9

思路：

首先对于所有数减去k，这样就不用除(r-l+1), 然后我们发现所求的就是有多少对l,r，使得sum[r]-sum[l-1] >= 0, sum是减去k之后的序列的前缀和

用树状数组对sum求有多少个顺序对，多加一个0这个数，代表从sum[r]-sum[0]对答案的贡献。

由于sum[i]可能很大，所以需要离散化。。

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
12     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 2e5+10;
17 
18 ll n,k,x,s[maxn],tree[maxn*4];
19 vector<ll> v;
20 
21 void add(ll x){
22     while(x < maxn){
23         tree[x] += 1;
24         x += x&-x;
25     }
26 }
27 
28 ll sum(ll x){
29     ll res = 0;
30     while(x > 0){
31         res += tree[x];
32         x -= x&-x;
33     }
34     return res;
35 }
36 
37 int main(){
38     cin >> n >> k;
39     for(int i=1; i<=n; i++){
40         x = read();
41         x -= k;
42         s[i] = s[i-1]+x;
43     }
44     for(int i=0; i<=n; i++) 
45         v.push_back(s[i]);
46     sort(v.begin(),v.end());
47     v.resize(unique(v.begin(),v.end())-v.begin());
48     for(int i=0; i<=n; i++) s[i] = lower_bound(v.begin(),v.end(),s[i])-v.begin()+1;
49 
50     ll ans = 0;
51     for(int i=0; i<=n; i++){
52         ans += sum(s[i]);
53         add(s[i]);
54     }
55     cout << ans << endl;
56 
57 
58     return 0;
59 }

 

 

AtCoder Regular Contest 075 E - Meaningful Mean 树状数组求顺序对， 前缀和


联系
我们