Codeforces Round #510 (Div. 2) - D. Petya and Array (树状数组+离散化)
程序员文章站
2022-05-09 15:08:26
...
http://codeforces.com/contest/1042/problem/D
题意:
给你n个数,询问你区间和小于t的个数。
POINT:
即sum[r]-sum[l-1]<t的(r,l)的对数(r>l)。
可以用逆序对的做法。把sum数组离散化之后。
每次sum[i]去找>sum[i]-t的前缀和的个数。
别忘记了sum[0]=0.
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 200000+22;
vector<LL>V;
LL sum[N];
int id(LL x)
{
return int(lower_bound(V.begin(),V.end(),x)-V.begin()+1LL);
}
int num[N<<1];
int sz;
void add(int x){while(x<=sz) static_cast<void>(num[x]++),x+=x&-x;}
int query(int x){int ans=0; while(x>=1) static_cast<void>(ans+=num[x]),x-=x&-x; return ans;}
int main()
{
LL t;int n;
scanf("%d%lld",&n,&t);
V.push_back(0);
for(int i=1;i<=n;i++){
scanf("%lld",&sum[i]);
sum[i]+=sum[i-1];
V.push_back(sum[i]);
V.push_back(sum[i]-t);
}
sort(V.begin(),V.end());
V.erase(unique(V.begin(),V.end()),V.end());
sz=V.size();
LL ans=0;
add(id(0));
for(int i=1;i<=n;i++){
ans+=query(sz)-query(id(sum[i]-t));
add(id(sum[i]));
}
printf("%lld\n",ans);
}
推荐阅读
-
Codeforces Round #510 (Div. 2) D. Petya and Array
-
Codeforces Round #510 (Div. 2) - D. Petya and Array (树状数组+离散化)
-
Codeforces Round #510 (Div. 2) D. Petya and Array(树状数组或线段树)
-
Codeforces Round #510 (Div. 2) D. Petya and Array
-
【Codeforces Round #510 (Div. 2) D.Petya and Array】 树状数组
-
Codeforces Round 510 D. Petya and Array (树状数组)
-
【权值线段树】Codeforces Round #510 (Div. 2) D. Petya and Array
-
Codeforces Round #510 (Div. 2) D. Petya and Array
-
CF Round #510 (Div. 2) D - Petya and Array (树状数组)
-
Codeforces Round #510 (Div. 2) D. Petya and Array (codeforces 1042 D)