Codeforces Round #510 (Div. 2) D. Petya and Array

题目链接：http://codeforces.com/contest/1042/problem/D

题意：求区间和＜k的个数；

思路：

很多人用线段树或者树状数组做的这道题，但是还有一个很有意思的做法（红黑树）

某一个区间的和，我们可以通过 Sn-Sm 来表示，那么题目的意思就可以变成，Sn - Sm < k 的个数；

假设有 S1 , S2，S3，S4，S5，(S5 = a1+a2+a3+a4+a5)，那么3到5的区间和就是 S5-S2；

由Sn-Sm < k 可得，Sn < k+Sm，要想求出以n结尾的所有符合题目意思的个数，就要找出 k+Sm大于Sn的所有Sm的个数，如果换成 公式 -Sm < k-Sn，那么，就要找出所有小于 k-Sn的个数，显然后者要比前者好求一些；因为要求的数在key = k-Sn的前面，我们可以用扫描法，从第一个开始逐步向前遍历，每遍历一次就从先前遍历过的数中找出我们要找的数对应的下标，就是我们要的值；那要如何快速的找出我们要找的Sm的下标呢？最容易想的方法就是二分，每遍历一个数就往容器内放一个数，然后sort然后lower_bound，虽然估计的时间复杂度大概是n*2logn，但是还是会超时；这时候用红黑树去找小于k的个数能快很多，这里介绍的是一个 pb_ds的函数库，现成的红黑树，只需要用insert加入数字，用order_of_key查找小于k的个数，能快就能得出答案；不过要注意的是，很多平台的oj并不适用这个函数库，这里只是觉得有意思才记录下来的，有空的时候，最好还是学学如果手写红黑树；下面给出代码：（因为红黑树不能存入相同的元素，所以用一个pair来存放元素，first是放-Sm的值，second是放一个index来区分相同的元素）

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<long long,int>,null_type,less< pair<long long,int> >,rb_tree_tag,tree_order_statistics_node_update> rbtree;

long long s[200005];

int main (void)
{
	int n,tmp;
	long long t;
	cin >> n >> t;
	s[0] = 0;
	rbtree it;
	it.insert(make_pair(0,0)); //因为红黑树是从0开始计数的，所以这里要先插入一个元素0；
	for (int i = 1; i <= n; ++i) {
		cin >> tmp;
		s[i] = s[i-1]+tmp;
	}
	long long ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans+=it.order_of_key(pair<long long,int> (t-s[i],0));
		it.insert(pair<long long,int> (-s[i],i));
	}
	cout << ans << endl;
	return 0;
 }