hdu4417

题意

给定一个数列，每次查询一个区间，和一个值h，问区间内有多少个数小于等于h。

分析

二分数的个数，划分树求解判断是否满足条件，划分树求解的是第k小的数，那么前面k个数肯定不大于这个数了，比较这个数和h即可。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int INF = 1e9;

const int MAXN = 1e5 + 5;

const int LOG_N = 30;

// tree[dep][i] 第dep层第i个位置的数值

int tree[LOG_N][MAXN];

int sorted[MAXN];

// toleft[p][i] 第p层前i个数中有多少个整数分入下一层

int toleft[LOG_N][MAXN];

void build(int l, int r, int dep)

{

    if(l == r) return;

    int mid = (l + r) / 2;

    int same = mid - l + 1; // 和中点数相同的数的个数

    for(int i = l; i <= r; i++)

        if(tree[dep][i] < sorted[mid]) same--;

    int lpos = l, rpos = mid + 1;

    for(int i = l; i <= r; i++)

    {

        if(tree[dep][i] < sorted[mid])

            tree[dep + 1][lpos++] = tree[dep][i];

        else if(tree[dep][i] == sorted[mid] && same)

        {

            tree[dep + 1][lpos++] = tree[dep][i];

            same--;

        }

        else tree[dep + 1][rpos++] = tree[dep][i];

        toleft[dep][i] = toleft[dep][l - 1] + lpos - l;

    }

    build(l, mid, dep + 1);

    build(mid + 1, r, dep + 1);

}

// [L,R]里查询子区间[l,r]第k小的数

int query(int L, int R, int l, int r, int dep, int k)

{

    if(l == r) return tree[dep][l];

    int mid = (L + R) / 2;

    // 有多少个查询区间内的节点会进入下一层的左子树

    int cnt = toleft[dep][r] - toleft[dep][l - 1];

    if(cnt >= k)

    {

        int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1];

        int newr = newl + cnt - 1;

        return query(L, mid, newl, newr, dep + 1, k);

    }

    else

    {

        int newr = r + toleft[dep][R] - toleft[dep][r];

        int newl = newr - (r - l - cnt);

        return query(mid + 1, R, newl, newr, dep + 1, k - cnt);

    }

}

int n, m;

int solve(int s, int t, int h)

{

    int l = 1, r = (t - s) + 1, mid;

    int ans = 0;

    while(l <= r)

    {

        mid = (l + r) / 2;

        if(query(1, n, s, t, 0, mid) <= h)

        {

            ans = mid;

            l = mid + 1;

        }

        else r = mid - 1;

    }

    return ans;

}

int main()

{

    int T;

    scanf("%d", &T);

    for(int kase = 1; kase <= T; kase++)

    {

        scanf("%d%d", &n, &m);

        for(int i = 1; i <= n; i++)

        {

            scanf("%d", &sorted[i]);

            tree[0][i] = sorted[i];

        }

        sort(sorted + 1, sorted + n + 1);

        build(1, n, 0);

        printf("Case %d:\n", kase);

        while(m--)

        {

            int s, t, h;

            scanf("%d%d%d", &s, &t, &h);

            s++; t++;

            printf("%d\n", solve(s, t, h));

        }

    }

    return 0;

}