[TIOJ] 1827. Yet another simple task ^____^

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

---

不難發現本題可以對答案二分搜，因為S有單調性，那驗證的時候就是要驗證一個區域是不是有至少k個數小於S，我原本想說用個BIT套treap之類的，但估完複雜度後發現會TLE，實在苦思不知該如何做，直到有人雷了我說誰區間和在用BIT的，我才發現可以用維護前綴和的精神做這題，也就是說每個前綴變成存一棵treap，但是如果每一個前綴都重新插一遍所有東東到treap裡面會發現預處理變成$O(n^2 log(n))$，明顯會TLE，所以不妨用持久化的概念，也就是讓一部分是共用的，有修改到的部分再複製出來就好了，因為複製時最多只會動到一條跟到葉的路徑也就是最多$log(n)$個節點，因此複雜度還是$log(n)$，只是記憶體有點龐大而已。

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

struct treap{
	treap *l, *r;
	int pri,val,size;
	treap(){l=r=nullptr;size=0;}
	treap(int x){l=r=nullptr;pri=rand();val=x;size=1;}
};
inline int gSize(treap* x){return x?x->size:0;}
inline void pull(treap* x){x->size=gSize(x->l)+1+gSize(x->r);}

int arr[N+5], n;
treap* root[N+5];
bool isOK(int,int,int);
void split(treap*,int,treap*&,treap*&);
treap* merge(treap*, treap*);
int query(treap*,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	srand(time(NULL));
	int m;cin>>n>>m;
	for(int i=0;i<n;i++)cin>>arr[i];
	root[0]=new treap(arr[0]);
	for(int i=1;i<n;i++){
		auto a=new treap, b=new treap;
		split(root[i-1], arr[i], a, b);
		root[i] = merge(merge(a,new treap(arr[i])), b);
	}
	while(m--){
		int p,k;cin>>p>>k;
		int l=-1,r=n;
		while(r-l>1){
			int mid=(r+l)>>1;
			if(isOK(mid, p, k))r=mid;
			else l=mid;
		}
		cout<<r<<'\n';
	}
	return 0;
}

bool isOK(int s,int p,int k){
	int l=p-s-1, r=min(p+s, n-1);
	int sm = (l<0)?query(root[r], s):query(root[r], s)-query(root[l], s);
	return sm>=k;
}

void split(treap* ori, int k, treap*& a, treap*& b){
	if(!ori)a=b=nullptr;
	else if(ori->val <= k){
		auto cow = new treap;
		*cow=*ori;
		a=cow;
		split(ori->r, k, a->r, b);
		pull(a);
	}else{
		auto cow = new treap;
		*cow=*ori;
		b=cow;
		split(ori->l, k, a, b->l);
		pull(b);
	}
}

treap* merge(treap* a, treap* b){
	if(!a || !b)return a?a:b;
	if(a->pri > b->pri){
		a->r=merge(a->r, b);
		pull(a);
		return a;
	}else{
		b->l=merge(a, b->l);
		pull(b);
		return b;
	}
}

int query(treap* rr, int k){
	if(!rr)return 0;
	if(rr->val<=k)return gSize(rr->l)+1+query(rr->r, k);
	else return query(rr->l, k);
}