CDOJ(Lutece)_2362_我，不是说了能力要平均值么

本文代码省略库和namespace声明，其中read()函数是读入数值的函数。

https://acm.uestc.edu.cn/problem/wo-bu-shi-shuo-liao-neng-li-yao-ping-jun-zhi-yao/description

这道题包括了线段树、前缀和、离散化、gcd四个点

前缀和：
考虑先将所有数字减去 k ，然后记录一个前缀和sum[i]，于是区间 [L,R] 的平均值小于等于 k 就等价于 sum[L]>=sum[R]

离散化：
考虑到 n ≤ 2e5 ，然而前缀和的值可能非常大。由于本题只需要比较前缀和的大小关系，不需要定量计算，于是用离散化把前缀和的数值范围大大缩小，这有利于建立线段树。

线段树：
对于一个离散化之后的前缀和数组
首先建立一个空线段树
然后从1到n遍历，对于 sum[i] , 先在线段树中查询 [sum[i],maxsum] 的出现次数（现在查询到的次数一定是出现在sum[i] 之前的前缀和贡献的次数），然后答案加上这个出现次数，再把 sum[i] 的贡献加入线段树即可。

gcd：
从线段树的遍历中拿到了满足题意的情况个数，显然这是一个分子，还需要找到分母。
容易知道，分母=1+2+...+n
然后利用gcd对分子分母进行化简即可。

const int MAXN = 200001;
long long n, k, ansa, ansb, a[MAXN], sum[MAXN], sum2[MAXN], maxsum, tmp, cnt[MAXN<<2];

long long gcd(long long a,long long b) { return b?gcd(b,a%b):a; }

inline void pushup(int rt)
{
    cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];
}

void update(int rt,int l,int r,int loc)
{
    if(l==r&&l==loc) { ++cnt[rt]; return ; }
    int mid=(l+r)>>1;
    if(loc<=mid) update(lson,loc);
    else update(rson,loc);
    pushup(rt);
}

int query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return cnt[rt];
    int mid=(l+r)>>1,res=0;
    if(L<=mid) res=query(lson,L,R);
    if(R>mid) res+=query(rson,L,R);
    return res;
}

int main()
{
    read(n); read(k);
    for (register int i=1;i<=n;++i) ansb+=i;
    for (register int i=1;i<=n;++i)
    {
        read(a[i]);
        a[i]-=k;
        sum[i]=sum[i-1]+a[i];
        sum2[i]=sum[i];
    }
    sort(sum2,sum2+n+1);
    tmp=sum2[0]; maxsum=0;
    for (register int i=1;i<=n;++i)
    {
        if(sum2[i]==tmp) continue;
        sum2[++maxsum]=sum2[i];
        tmp=sum2[i];
    }
    for (register int i=0;i<=n;++i)
    {
        sum[i]=lower_bound(sum2,sum2+maxsum+1,sum[i])-sum2+1;
        //printf("sum[%d] = %d\n",i,sum[i]);
    }
    ++maxsum;
    for (register int i=0;i<=n;++i)
       {
           ansa+=query(1,1,maxsum,sum[i],maxsum);
           update(1,1,maxsum,sum[i]);
       }
    do
    {
        tmp=gcd(ansa,ansb);
        ansa/=tmp;
        ansb/=tmp;
    }while(tmp>1);
    printf("%lld/%lld",ansa,ansb);
    return 0;
}