P2717

Aryper · 2021-10-12 18:45:37 · 个人记录

寒假作业

序列所有数同时减去 k，再求前缀和。平均值大于等于 k 就是此时的连续序列和非负。然后在前缀和上做 CDQ 分治。

同样是由小到大排序。

注意区间的左端点为 0。

时间复杂度 O(n\log n)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,k,ans;

ll a[N+5],c[N+5],tmp[N+5];

void solve(ll l,ll r) {
    if(l==r) return;
    ll mid=(l+r)>>1;
    solve(l,mid);solve(mid+1,r);
    ll i=l,j=mid+1,cnt=l;
    while(i<=mid&&j<=r) {
        if(c[j]-c[i]>=0) tmp[cnt++]=c[i++];
        else {ans+=i-l;tmp[cnt++]=c[j++];}
    }
    while(i<=mid) tmp[cnt++]=c[i++];
    while(j<=r) {ans+=i-l;tmp[cnt++]=c[j++];}
    for(ll i=l;i<=r;i++) c[i]=tmp[i];
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();k=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read()-k;c[i]=c[i-1]+a[i];
    //  printf("c[%lld]=%lld\n",i,c[i]);
    }

    solve(0,n);

    write(ans);

    return 0;
}