欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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);
}