【Codeforces 1042D】Petya and Array

题意

【题解】

把a[i]处理成前缀和
离散化.
枚举i从1..n假设a[i]是区间和的a[r]
显然我们需要找到a[r]-a[l]

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 2e5;

int n;

ll t;

ll a[N+10];

ll b[N*2+10];

map<ll,int> dic,dic1;

int lowbit(int x){

    return x&(-x);

}

ll get_sum(int x){

    ll ans = 0;

    while (x>0){

        ans = ans + b[x];

        x = x-lowbit(x);

    }

    return ans;

}

void add(int x){

    while (x<=2*N+2){

        b[x]= b[x]+1;

        x = x + lowbit(x);

    }

}

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> t;

    dic[0] = 1;

    dic[0+t] = 1;

    for (int i = 1;i <= n;i++) {

        cin >> a[i];

        a[i]+=a[i-1];

        dic[a[i]] = 1;

        dic[a[i]+t] = 1;

    }

    int cnt = 0;

    for (auto temp:dic){

        cnt++;

        dic1[temp.first] = cnt;

    }

    add(dic1[0+t]);

    //cout<<dic1[0+t]<<endl;

    ll fans = 0;

    for (int i = 1;i <= n;i++){

        ll temp1 = get_sum(cnt)-get_sum(dic1[a[i]]);

        fans = fans + temp1;

        add(dic1[a[i]+t]);

    }

    cout<<fans<<endl;

    return 0;

}

巴特西

【Codeforces 1042D】Petya and Array

最新文章

热门文章