Talk is Cheap, Show Me the Code!

0%

可修改区间第K值

Posted on In

给定一个长度为n的序列A，有m个询问，每次询问下标在[L,R]范围内的数字，从小到大排序之后，第K小的元素值，同时需要支持修改某个元素。

输入描述:

第一行两个整数n和m。
第二行n个整数，表示Ai。
接下来m行，属于下面两种情况之一：
1 L R K：表示下标在[L,R]范围内的第K小的数。
2 x y：把A[x]赋值成y。

输出描述:

对于每个询问，输出相应的结果。

示例1
输入

5 3
10 5 3 4 8
1 1 2 1
2 4 7
1 1 4 3

输出

5
7

说明

n,m<=30000

kexiukaik.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define M 305
using namespace std;
int A[M*M],sz[M],K;
struct node {
    int id,num;
    void set(int _id,int _num) {
        id=_id,num=_num;
    }
} C[M][M];
bool cmp(node a,node b) {
    return a.num<b.num;
}
int Find(int id,int R,int x) {
    int L=0,res=-1;
    while(L<=R) {
        int mid=(L+R)>>1;
        if(C[id][mid].num<=x) {
            res=mid;
            L=mid+1;
        } else R=mid-1;
    }
    return res;
}
int find_less(int x,int a,int b) {//不完整块暴力扫描，完整块二分查找
    int id_a=a/K,id_b=b/K;
    int res=0,i;
    if(id_a==id_b) {
        for(i=a; i<=b; i++)
            res+=A[i]<=x;
    } else {
        for(i=a; i<id_a*K+sz[id_a]; i++)
            res+=A[i]<=x;
        for(i=id_a+1; i<id_b; i++)
            res+=Find(i,sz[i]-1,x)+1;
        for(i=id_b*K; i<=b; i++)
            res+=A[i]<=x;
    }
    return res;
}
int query(int a,int b,int k) {//二分查找
    int L=0,R=1000000000;
    int res=0;
    while(L<=R) {
        int mid=(L+R)>>1;
        if(find_less(mid,a,b)>=k) {
            res=mid;
            R=mid-1;
        } else L=mid+1;
    }
    return res;
}
void update(int a,int x) {//更新
    int i,id_a=a/K;
    A[a]=x;
    for(i=0; i<sz[id_a]; i++)//找到位置，修改值
        if(C[id_a][i].id==a) {
            C[id_a][i].num=x;
            break;
        }
    sort(C[id_a],C[id_a]+sz[id_a],cmp);//重新排序，可用插入排序优化
}
int main() {
    int cas,n,m,i,j,k,a,b;
    scanf("%d",&cas);
    while(cas--) {
        scanf("%d %d",&n,&m);
        K=int(sqrt(n));
        memset(sz,0,sizeof(sz));
        for(i=0; i<n; i++) {
            scanf("%d",&A[i]);
            C[i/K][i%K].set(i,A[i]);
            sz[i/K]++;
        }
        for(i=0; i<=(n-1)/K; i++) {
            sort(C[i],C[i]+sz[i],cmp);
        }
        char op[2];
        while(m--&&scanf("%s",op)) {
            if(op[0]=='Q') {
                scanf("%d %d %d",&a,&b,&k);
                printf("%d\n",query(--a,--b,k));
            } else {
                scanf("%d %d",&a,&b);
                update(--a,b);
            }
        }
    }
    return 0;
}