Codeforces Round #510 (Div. 2) D. Petya and Array（树状数组或线段树）

地址：http://codeforces.com/contest/1042/problem/D

很多题都是不会直接就可以应用一个算法，都会转变一下就变成了熟悉的问题；
这道题当把数组变成前缀和sum数组则需要找满足sum[j] - sum[i - 1] < t;如果数据量小的话，直接在对应的前缀和值上进行树状数组即可；但是这题数据比较大，所以先将前缀和值离散化排序一下，sum[j] - t < sum[i - 1];用二分在离散化后的数据中找到该在哪个位置上加一，在该位置以下的sum值都比该位置的小，在该位置以上的sum值比该位置的 大，计数即可
注意：在sum值找，总会缺少一种情况是[1,j],sum值里只能找到[i,j]区间；所以先提前处理一下[1,i]小于t的个数或者添加一个sum值为0的虚节点

树状数组做法：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 2 * 1e5 + 5;

#define lowbit(x) x&-x

LL a[N];
LL b[N];
LL sum[N];
LL n,t;

void add(int i,int val)
{
    while(i <= n)
    {
        b[i] += val;
        i += lowbit(i);
    }
}

LL query(int i)
{
    LL ans = 0;
    while(i)
    {
        ans += b[i];
        i -= lowbit(i);
    }
    return ans;
}

int main()
{
    while(~scanf("%lld %lld",&n,&t))
    {
        memset(sum,0,sizeof(sum));
        memset(b,0,sizeof(b));
        LL ans = 0;
        for(int i = 1;i <= n;++i)
        {
            scanf("%lld",&a[i]);
            sum[i] = sum[i - 1] + a[i];
            a[i] = sum[i];
            if(sum[i] < t) ans++;
        }
        sort(a + 1,a + n + 1);
        for(int i = 1;i <= n;++i)
        {
            int x = lower_bound(a + 1,a + n + 1,sum[i]) - a;
            int y = lower_bound(a + 1,a + n + 1,sum[i] - t + 1) - a - 1;
            ans += (i - 1 - query(y));
            //cout << x << " " << y << " " << ans << endl;
            add(x,1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

线段树做法：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 2 * 1e5 + 5;

LL tree[N << 2];
LL a[N];
LL sum[N];

void updateone(int root,int l,int r,int index,LL val)
{
    if(l == r){
        if(l == index){
            tree[root] += val;
        }
        return ;
    }
    int mid = (l + r) / 2;
    if(index <= mid){
        updateone(root * 2 + 1,l,mid,index,val);
    }else{
        updateone(root * 2 + 2,mid + 1,r,index,val);
    }
    tree[root] += val;
}

LL query(int root,int l,int r,int ql,int qr)
{
    if(qr < l || ql > r){
        return 0;
    }
    if(ql <= l && qr >= r){
        return tree[root];
    }
    int mid = (l + r) / 2;
    LL sum = 0;
    if(ql <= mid){
        sum += query(root * 2 + 1,l,mid,ql,qr);
    }
    if(qr > mid){
        sum += query(root * 2 + 2,mid + 1,r,ql,qr);
    }
    return sum;
}

int main()
{
    LL n,t;
    while(~scanf("%lld %lld",&n,&t))
    {
        memset(tree,0,sizeof(tree));
        memset(a,0,sizeof(a));
        memset(sum,0,sizeof(sum));
        LL ans = 0;
        for(int i = 1;i <= n;++i)
        {
            scanf("%lld",&a[i]);
            a[i] += a[i - 1];
            sum[i] = a[i];
        }
        //加了一个虚节点来求sum[i] - 0的情况
        sort(a,a + n + 1);
        for(int i = 1;i <= n;++i)
        {
            int x = lower_bound(a,a + n + 1,sum[i - 1]) - a + 1;
            updateone(1,1,n + 1,x,1LL);
            //原本需要-a-1，但是由于上面都是将整体id加了个1，所以这里不用了
            int y = lower_bound(a,a + n + 1,sum[i] - t + 1) - a + 1;
            ans += query(1,1,n + 1,y,n + 1);
            //cout << query(1,1,n + 1,y,n + 1) << endl;
           // cout << x << " " << y << endl;
        }
        printf("%lld\n",ans);
    }
    return 0;
}