[TIOJ] 1208. 第K大連續和

題目連結:http://tioj.infor.org/problems/1208

---

不太確定該如何下手時，就先二分搜一陣吧，而且他還特別保證所有項的絕對值都不超過10,000，所以感覺二分搜有機會，那二分搜答案要怎麼驗證呢?其實對於一個數我們有能力可以知道有幾個連續和比他大，因為如果要看x是第幾大，則就是對於每個前綴和$a_i$我們都要找有多少個$a_j$使得$a_i - a_j > x$(其中$i>j$)，移項發現變成找有多少個$a_j+x < a_i$，那不就是一個平衡數常帶有的功能嗎?所以就先找看看對於這個前綴和$a_i$有多少個$a_j+x$比他小，算完後再把$a_i+x$丟到平衡樹內，如此就可以知道他是第幾大的了，複雜度$O(n log n log C)$其中C是值域

#include <bits/stdc++.h>
using namespace std;
#define N 20000

class Treap{
	private:
		struct __node{
			__node* l;
			__node* r;
			int __pri,__size,__val;
			__node(){l=NULL;r=NULL;__pri=rand();__size=0;}
			__node(int x){l=NULL;r=NULL;__pri=rand();__size=1;__val=x;}
			~__node(){if(l)delete l;if(r)delete r;l=NULL;r=NULL;}
		};
		__node* __root;
		inline int __gSize(__node* __x){return (__x==NULL)?0:(__x->__size);}
		__node* __merge(__node* __x,__node* __y){
			if(__x==NULL||__y==NULL)return __x?__x:__y;
			else if(__x->__pri > __y->__pri){
				__x->r = __merge(__x->r,__y);
				__x->__size = __gSize(__x->l)+__gSize(__x->r)+1;
				return __x;
			}else{
				__y->l = __merge(__x,__y->l);
				__y->__size = __gSize(__y->l)+__gSize(__y->r)+1;
				return __y;
			}
		}
		void __split(__node* rr, int x, __node*& l, __node*& r){
			if(rr==NULL)r=l=NULL;
			else if(rr->__val <= x){
				l=rr;
				__split(rr->r, x, l->r, r);
				l->__size = __gSize(l->r)+__gSize(l->l)+1;
			}else{
				r=rr;
				__split(rr->l, x, l, r->l);
				r->__size = __gSize(r->r)+__gSize(r->l)+1;
			}
		}
		int __oOk(__node* rr, int x){
			if(rr==NULL)return 0;
			if((rr->__val) < x)return __gSize(rr->l)+__oOk(rr->r, x)+1;
			else return __oOk(rr->l, x);
		}
	public:
		Treap(){__root=NULL;}
		~Treap(){delete __root;__root=NULL;}
		void insert(int x){
			__node *a, *b;
			__split(__root, x, a, b);
			__root = __merge(__merge(a, new __node(x)), b);
			__root->__size = __gSize(__root->l)+__gSize(__root->r)+1;
		}
		int order_of_key(int x){return __oOk(__root,x);}
};

int arr[N+5], n, k;
inline bool isOK(int);

int main(){
	srand(time(NULL));
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k;
	arr[0]=0;
	while(n!=0||k!=0){
		int l=-1,r=1;
		for(int i=1;i<=n;i++){
			int x;cin>>x;
			arr[i]=arr[i-1]+x;
			if(x<0)l+=x;
			else r+=x;
		}
		while(r-l>1){
			int mid=(l+r)/2;
			if(isOK(mid))r=mid;
			else l=mid;
		}
		cout<<r<<'\n';
		cin>>n>>k;
	}
	return 0;
}

inline bool isOK(int x){
	Treap ss;
	int sm=0;
	for(int i=0;i<=n;i++){
		sm+=ss.order_of_key(arr[i]);
		ss.insert(arr[i]+x);
	}
	return sm<k;
}