[TIOJ] 1827 Yet another simple task ^____^

題目連結：https://tioj.ck.tp.edu.tw/problems/1827
　　人生第一次寫了持久化資料結構>< ! 不過是參考了cbd的code才順利寫出來的。
　　b[i]的範圍在1e5以內所以不用離散話，二分搜答案，建持久化線段樹。

#include<bits/stdc++.h>
using namespace std;
const int N = 100000+10;
struct node{
    int val;
    node *l,*r;
    node(int v)
    {
        val = v;
        l = r = NULL;
    }
}*root[N];
node* build(int L,int R)
{
    if(L == R) return ( new node(0) );
    int mid = (L+R)>>1;
    node *v = new node(0);
    v->l = build(L,mid);
    v->r = build(mid+1,R);
    return v;
} 
node* modify(int L,int R,node* u,int pos)
{
    if(L == R) return ( new node(u->val+1) );
    node* v = new node(0);
    int mid = (L+R)>>1;
    if(pos<=mid)
    {
        v->r = u->r;
        v->l = modify(L,mid,u->l,pos);
    }
    else
    {
        v->l = u->l;
        v->r = modify(mid+1,R,u->r,pos);
    }
    v->val = v->l->val+v->r->val;
    return v;
}
int query(int ql,int qr,int L,int R,node* u1,node* u2)
{
    if(ql == L && qr == R) return (u2->val - u1->val);
    if(R < ql || qr < L) return 0;
    int mid = (L+R)>>1;
    if(qr <= mid) return query(ql,qr,L,mid,u1->l,u2->l);
    else if(mid < ql) return query(ql,qr,mid+1,R,u1->r,u2->r);
    else return query(ql,mid,L,mid,u1->l,u2->l)+query(mid+1,qr,mid+1,R,u1->r,u2->r);
}
signed main()
{
    int n,m;
    cin >> n >> m;
    root[0] = build(1,n);
    for(int i = 1; i <= n; i++) 
    {
        int x; cin >> x;
        root[i] = modify(1,n,root[i-1],x);
    }
    while(m--)
    {
        int p,k; cin >> p >> k; p++;
        int l = 0, r = n;
        while(r-l>1)
        {
            int mid = (l+r)>>1, lo = max(1,p-mid), ro = min(n,p+mid);
            if(query(1,mid,1,n,root[lo-1],root[ro]) >= k) r = mid;
            else l = mid;
        }
        cout << r << '\n';
    }
}