ZOJ 2112 Dynamic Rankings（带修改的区间第K大，分块+二分搜索+二分答案）

Dynamic Rankings

Time Limit: 10 Seconds Memory Limit: 32768 KB

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.

Your task is to write a program for this computer, which

- Reads N numbers from the input (1 <= N <= 50,000)

- Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change some a[i] to t.

Input

The first line of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a single test case.

The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format

Q i j k or
C i t

It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.

There're NO breakline between two continuous test cases.

Output

For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],..., a[j])

There're NO breakline between two continuous test cases.

Sample Input

2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output

3
6
3
6

题目链接：ZOJ 2112

突然发现用分块做很简单，每一个块维护区间内的有序序列，暴力修改+重构，查询的时候二分下答案，设当前的二分值为mid，如果区间内小于等于mid的数>=k则说明答案小于等于mid，否则答案大于mid。

代码：

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 50010;

const int M = 10010;

const int BC = 233;

struct Block

{

    int l, r;

};

Block B[M];

int arr[N], belong[N], unit, bcnt, b[N];

int n, m;

void reset(int x)

{

    for (int i = B[x].l; i <= B[x].r; ++i)

        b[i] = arr[i];

    sort(b + B[x].l, b + B[x].r + 1);

}

void init()

{

    unit = sqrt(n);

    bcnt = n / unit;

    if (n % unit)

        ++bcnt;

    int i;

    for (i = 1; i <= bcnt; ++i)

    {

        B[i].l = (i - 1) * unit + 1;

        B[i].r = i * unit;

    }

    B[bcnt].r = n;

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

        belong[i] = (i - 1) / unit + 1;

    for (i = 1; i <= bcnt; ++i)

        reset(i);

}

void update(int x, int t)

{

    int bx = belong[x];

    arr[x] = t;

    reset(bx);

}

int bs(int x, int key)

{

    int l = B[x].l, r = B[x].r;

    int ans = -1;

    while (l <= r)

    {

        int mid = MID(l, r);

        if (b[mid] <= key)

        {

            ans = mid;

            l = mid + 1;

        }

        else

            r = mid - 1;

    }

    return ~ans ? ans - B[x].l + 1 : 0;

}

int query(int l, int r, int k)

{

    int L = 0, R = 1e9;

    int ans = 1;

    int bl = belong[l], br = belong[r], i;

    while (L <= R)

    {

        int tk = 0;

        int mid = MID(L, R);

        for (i = l; i <= B[bl].r; ++i)

            if (arr[i] <= mid)

                ++tk;

        for (i = B[br].l; i <= r; ++i)

            if (arr[i] <= mid)

                ++tk;

        for (i = bl + 1; i < br; ++i)

            tk += bs(i, mid);

        if (tk >= k)

        {

            ans = mid;

            R = mid - 1;

        }

        else

            L = mid + 1;

    }

    return ans;

}

int main(void)

{

    int tcase, i;

    char ops[3];

    int l, r, k, x, t;

    scanf("%d", &tcase);

    while (tcase--)

    {

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

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

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

        init();

        for (i = 1; i <= m; ++i)

        {

            scanf("%s", ops);

            if (ops[0] == 'Q')

            {

                scanf("%d%d%d", &l, &r, &k);

                printf("%d\n", query(l, r, k));

            }

            else

            {

                scanf("%d%d", &x, &t);

                update(x, t);

            }

        }

    }

    return 0;

}

巴特西

ZOJ 2112 Dynamic Rankings（带修改的区间第K大，分块+二分搜索+二分答案）

最新文章

热门文章