「Atcoder」ARC075 E - Meaningful Mean

h fake q安利的题.

Links there:ARC075E

题意:给出一个长为$N$的序列 ,求出所有的连续序列,满足他们的算术平均数小于等于$K$.

范围:$N\leq 200000,1 \leq A_i \leq 10^9,1 \leq K \leq 10^9$

分析:首先可以考虑简化问题,将每一个数先减去$K$,再维护一个前缀和$sum$,那么问题简化成求出所有对$(l,r)$使得$sum(r)-sum(l-1) \geq 0$.那么我们求出所有$sum$中的顺序对,也就是满足$i<j,sum[i]<sum[j]$的个数就行了,我们可以用树状数组来维护这个东西.注意离散化.

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;
#define lowbit(x) (x&-x)

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
const int MAXN = 2e5 + 100;
int n,k,a[MAXN],s[MAXN],ans = 0;
int C[MAXN];
vector<int>v;
inline void add(int x,int d){for(int i=x;i<MAXN;i+=lowbit(i)) C[i]+=d;}
inline int Gsum(int x){int ret = 0;for (int i=x;i>=1;i-=lowbit(i)) ret += C[i]; return ret;}
///------------------head------------------
signed main(signed argc, char *argv[]){
    n=read(); k=read();
    rep(i,1,n) a[i]=read()-k,s[i]=s[i-1]+a[i];
    rep(i,0,n) v.pb(s[i]);
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    rep(i,0,n) s[i]=lower_bound(v.begin(),v.end(),s[i])-v.begin()+1;
    rep(i,0,n){
        ans += Gsum(s[i]);
        add(s[i],1);
    }
    printf("%lld\n",ans);
	return 0;
}

/* Examples: */
/*
7 26
10
20
30
40
30
20
10
*/

/*
13
*/