[TIOJ 1827] Yet another simple task ^____^

作法：

如果考慮二分答案的話，那麼就會需要查詢某個區間內小於等於某個值的數有幾個，而這是持久化線段樹的經典應用。另外對於這個問題也可以用劃分樹解決，code 是陳博彰寫的，也順便附在下面。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
struct node
{
    node *l,*r ;
    int val ;
    node(int v)
    {
        val=v ;
        l=r=NULL ;
    }
};
 
node *build(int L,int R)
{
    if(L==R) return ( new node(0) ) ;
    int mid=(L+R)/2 ;
    node *u=new node(0) ;
    u->l = build(L,mid) ;
    u->r = build(mid+1,R) ;
    return u ;
}
 
node *modify(int L,int R,node *u,int pos)
{
    if(L==R) return ( new node( u->val+1 ) ) ;
    int mid=(L+R)/2 ;
    node *v=new node(0) ;
    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 l,int r,int L,int R,node *u1,node *u2)
{
    if(l==L && r==R) return (u2->val - u1->val) ;
    int mid=(L+R)/2 ;
    if(r<=mid) return query(l,r,L,mid,u1->l,u2->l) ;
    else if(l>mid) return query(l,r,mid+1,R,u1->r,u2->r) ;
    else return query(l,mid,L,mid,u1->l,u2->l) +
                query(mid+1,r,mid+1,R,u1->r,u2->r) ;
}
 
node *root[maxn] ;
main()
{
    int n,Q ; scanf("%d%d",&n,&Q) ;
    root[0]=build(1,n) ;
    for(int i=1;i<=n;i++)
    {
        int x ; scanf("%d",&x) ;
        root[i]=modify(1,n,root[i-1],x) ;
    }
    while(Q--)
    {
        int p,k ; scanf("%d%d",&p,&k) ; p++ ;
        int l=0 , r=n ;
        while(r-l>1)
        {
            int mid=(l+r)/2 , lo=max(1,p-mid) , hi=min(n,p+mid) ;
            if( query(1,mid,1,n,root[lo-1],root[hi]) >= k) r=mid ;
            else l=mid ;
        }
        printf("%d\n",r) ;
    }
}

用劃分樹的 code :

#include <cstdio>
#include <algorithm>
using namespace std;
 
int data[2][128 * 1024];
int left[17][128 * 1024];
 
/**
 *  Precondition:  data[17 % 2] is b
 *  Postcondition: left is properly filled
 *                 data[0] is b sorted (though unused)
 *                 data[1][i] = upper_bound(data[0], data[0] + 128 * 1024, i)
 */
void preprocess() {
    for(int d = 16, g = 2; d >= 0; d--, g <<= 1) {
        for(int l = 0; l < 128 * 1024; l += g) {
            int r = l + g, m = (l + r) / 2;
            merge(data[(d + 1) % 2] + l, data[(d + 1) % 2] + m,
                  data[(d + 1) % 2] + m, data[(d + 1) % 2] + r, 
 
                  data[d % 2] + l);
            for(int i = l, j = l; i < r; i++) {
                while(data[(d + 1) % 2][j] <= data[d % 2][i] && j < m)
                    j++;
                left[d][i] = j - l;
            }
        }
    }
    for(int i = 0, j = 0; i < 128 * 1024; i++) {
        while(data[0][j] <= i && j < 128 * 1024)
            j++;
        data[1][i] = j;
    }
}
 
int query(int hint, int l, int r, int d = 0, int nl = 0, int nr = 128 * 1024) {
    if(l <= nl && nr <= r) {
        return hint;
    } else if(!(r <= nl || nr <= l)) {
        if(hint == 0)
            return 0;
        int lhint = left[d][nl + hint - 1];
        int rhint = hint - lhint;
        return query(lhint, l, r, d + 1, nl, (nl + nr) / 2) +
               query(rhint, l, r, d + 1, (nl + nr) / 2, nr);
    } else {
        return 0;
    }
}
 
bool ok(int n, int p, int k, int s) {
    return query(data[1][s], max(p - s, 0), min(p + s + 1, n)) >= k;
}
 
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
        scanf("%d", data[17 % 2] + i);
    fill(data[17 % 2] + n, data[17 % 2] + 128 * 1024, 1048576);
    preprocess();
    for(int i = 0; i < m; i++) {
        int p, k;
        scanf("%d %d", &p, &k);
        int l = 0, r = n;
        while(l < r) {
            int s = (l + r) / 2;
            ok(n, p, k, s) ? (r = s) : (l = s + 1);
        }
        printf("%d\n", r);
    }
}