题目描述



题目分析

其实就是动态查询区间 [a, b] 中第八大的数,使用线段树,线段树中套一个 vector 保存前八大的数。

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
#include<cstdio>
#include<vector>
using namespace std;
const int N=400001;

struct Tree {
int l,r;
vector<int> v;
} tree[N];

// 将l和r归并到v中
void pushUp(vector<int> &v,const vector<int> &l,const vector<int> &r) {
int i,j,k;
i=j=k=0;
while(k<8) {
if(l[i]>r[j]) {
v[k++]=l[i++];
}
else {
v[k++]=r[j++];
}
}
}

void build(int u,int l,int r) {
tree[u].l=l;
tree[u].r=r;
tree[u].v.resize(8);
if(l==r) {
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
//因为一开始都是0,所以不用pushup
}

void modify(int u,int p,int x) {
if(tree[u].l==tree[u].r) {
tree[u].v[0]=x;
return;
}
int mid=(tree[u].l+tree[u].r)>>1;
if(p<=mid) {
modify(u<<1,p,x);
}
else {
modify(u<<1|1,p,x);
}
pushUp(tree[u].v,tree[u<<1].v,tree[u<<1|1].v);
}

vector<int> query(int u,int l,int r) {
if(tree[u].l>=l && tree[u].r<=r) {
return tree[u].v;
}
int mid=(tree[u].l+tree[u].r)>>1;
if(r<=mid) {
return query(u<<1,l,r);
}
if(l>mid) {
return query(u<<1|1,l,r);
}
vector<int> ans(8,0);
pushUp(ans,query(u<<1,l,r),query(u<<1|1,l,r));
return ans;
}

int main()
{
int L,N;
scanf("%d %d",&L,&N);
build(1,1,L);
char op;
int a,b;
while(N--) {
scanf("\n%c %d %d",&op,&a,&b);
if(op=='C') {
modify(1,a,b);
}
else {
printf("%d\n",query(1,a,b)[7]);
}
}

return 0;
}