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

题目链接: 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

思路： 【AtCoder|AtCoder Regular Contest 075 E - Meaningful Mean 树状数组求顺序对，前缀和】首先对于所有数减去k，这样就不用除(r-l+1), 然后我们发现所求的就是有多少对l,r，使得sum[r]-sum[l-1] >= 0, sum是减去k之后的序列的前缀和
用树状数组对sum求有多少个顺序对，多加一个0这个数，代表从sum[r]-sum[0]对答案的贡献。
由于sum[i]可能很大，所以需要离散化。。
代码：

1 #include 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(){ 10ll x=0,f=1; char ch=getchar(); 11while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar(); } 12while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar(); } 13return x*f; 14 } 15 // 16 const int maxn = 2e5+10; 17 18 ll n,k,x,s[maxn],tree[maxn*4]; 19 vector v; 20 21 void add(ll x){ 22while(x < maxn){ 23tree[x] += 1; 24x += x&-x; 25} 26 } 27 28 ll sum(ll x){ 29ll res = 0; 30while(x > 0){ 31res += tree[x]; 32x -= x&-x; 33} 34return res; 35 } 36 37 int main(){ 38cin >> n >> k; 39for(int i=1; i<=n; i++){ 40x = read(); 41x -= k; 42s[i] = s[i-1]+x; 43} 44for(int i=0; i<=n; i++) 45v.push_back(s[i]); 46sort(v.begin(),v.end()); 47v.resize(unique(v.begin(),v.end())-v.begin()); 48for(int i=0; i<=n; i++) s[i] = lower_bound(v.begin(),v.end(),s[i])-v.begin()+1; 49 50ll ans = 0; 51for(int i=0; i<=n; i++){ 52ans += sum(s[i]); 53add(s[i]); 54} 55cout << ans << endl; 56 57 58return 0; 59 }

转载于:https://www.cnblogs.com/yxg123123/p/6938882.html