CF510 D - Petya and Array

問題

長さnの数列aが与えられる
aの連続する部分列のうち、総和がt未満になるものの個数を求めよ

1 <= n <= 2*10^5
|a[i]| <= 10^9
|t| <= 2*10^14

解法

とりあえず累積和sを取る
a[i]が全部正なら累積和が単調増加になるから二分探索で解けるけど、今回は負の数もあるから無理
BITが使えれば各iでs[j] < s[i]+t ∴ s[j] <= s[i]+t-1となるようなj(>i)の個数を足し合わせていけば解ける
でもaの値が大きいからそのままは無理
ただ使う値の種類は累積和の各要素とそれらにt-1を足したものだけで、それらはたかだかn*2個しかないから、圧縮すればいける

実装

使う値をsetに入れて、手前から0,1,2,...と番号を付ける感じでmapで変換表を作ってる
自分的には楽だから座標圧縮系は毎回こうやってんだけど別にvectorに入れてuniqueしてもいい

部分列の左端と右端が同じやつは別に数えてる

#define int long long

template<class T, int ME> class BIT {
	public:
	T bit[1<<ME],val[1<<ME];
	T sum(int e) {T s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	T add(int e,T v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	T set(int e,T v) { add(e,v-val[e]);}
	int lb(T v) {
		T tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<v) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};

int n, t, a[200200], s[200200], ans, m;
set<int> x;
map<int,int> y;
BIT<int,20> b;

signed main() {
	cin >> n >> t;
	rep(i,n) {
		cin >> a[i];
		s[i] = (i==0 ? 0 : s[i-1]) + a[i];
		x.insert(s[i]), x.insert(s[i]+t-1);
	}
	each(i,x) y[i] = m++;
	rep(i,n) b.add(y[s[i]],1), ans += (s[i]<t);
	rep(i,n) {
		b.add(y[s[i]],-1);
		ans += b.sum(y[s[i]+t-1]);
	}
	cout << ans << endl;
}