W哭了,找了三个小时错误,还是W第六个和第七个样例,求佬佬帮忙康康
查看原帖
W哭了,找了三个小时错误,还是W第六个和第七个样例,求佬佬帮忙康康
506883
NojmLi楼主2021/4/7 23:06
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF=1e10+10;
typedef struct Node{
    int lson,rson;
    ll sum;
}node;
ll b[100010];
node a[100000000];
int root,ct;
int L=-INF,R=INF;
void pushup(int u){
    a[u].sum=a[a[u].lson].sum+a[a[u].rson].sum;
}

void update(int &u,ll l,ll r,ll x){
    if(!u) u=++ct;
    if(l==r){
        a[u].sum+=1;
        return;
    }
    ll mid=l+r>>1;
    if(x<=mid) update(a[u].lson,l,mid,x);
    if(x>mid) update(a[u].rson,mid+1,r,x);
    pushup(u);
}
ll query(int u,ll l,ll r,ll x,ll y){
    if(!u) return 0;
    if(x<=l&&y>=r) return a[u].sum;
    ll mid=l+r >>1;
    ll res=0;
    if(x<=mid) res+=query(a[u].lson,l,mid,x,y);
    if(y>mid) res+=query(a[u].rson,mid+1,r,x,y);
    return res;
}
int main(){
    ll low,high;
    int n;
    scanf("%d%lld%lld",&n,&low,&high);
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
        b[i]+= b[i-1];//前i项之和
    }
    root=++ct;

    update(root,L,R,0);
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=query(root,L,R,b[i]-high,b[i]-low);
        update(root,L,R,b[i]);
    }
    printf("%lld\n",ans);
    return 0;
}


2021/4/7 23:06
加载中...