題目描述：
有一條河，沿河的一側(cè)生活著一個(gè)部落。這個(gè)一字型的部落有n個(gè)據(jù)點(diǎn)，從左至右依次編號(hào)1~n。
部落的人們有時(shí)會(huì)在某個(gè)據(jù)點(diǎn)建立建筑，每個(gè)建筑都有各自的價(jià)值。一開始，每個(gè)據(jù)點(diǎn)的都沒(méi)有建筑，價(jià)值都是0。如果在已有建筑的據(jù)點(diǎn)建立新的建筑，那么新的建筑會(huì)代替舊的建筑（舊的建筑就此消失）。
有兩種操作C和Q：
1、C x y，表示在據(jù)點(diǎn)x建立一個(gè)價(jià)值為y的建筑。
2、Q x y，詢問(wèn)在據(jù)點(diǎn)x~y之間（包括x，y）的建筑中，價(jià)值第八大的建筑的價(jià)值是多少。

輸入描述：
第一行，兩個(gè)正整數(shù)n和k，表示據(jù)點(diǎn)的數(shù)量和操作的數(shù)量。
接下的k行，每行一個(gè)操作。

輸出描述：
對(duì)于所有的Q操作，輸出相應(yīng)的第八大建筑的價(jià)值。

輸入樣例：
10 14
C 1 5
C 2 4
C 3 7
C 4 6
C 5 5
C 6 1
C 7 8
Q 1 10
C 8 3
C 9 6
C 10 3
Q 1 9
C 6 10
Q 1 10

輸出樣例：
0
3
4
思路：唉，當(dāng)時(shí)要是能想到這一點(diǎn)，也不會(huì)只拿個(gè)國(guó)二了。
很明顯，區(qū)間操作，線段樹是很容易想到的。但是這次線段樹的每一個(gè)節(jié)點(diǎn)不是維護(hù)一個(gè)數(shù)了，而是8個(gè)數(shù)。因?yàn)?很小，所以還是可以承擔(dān)的。每次pushup的時(shí)候，將最大的八個(gè)數(shù)更新給父節(jié)點(diǎn)。查詢的時(shí)候返回一個(gè)數(shù)組就可以了。代碼沒(méi)有測(cè)試，不知道有沒(méi)有問(wèn)題，當(dāng)個(gè)參考吧。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; struct node{int l;int r;int a[9];int len; }p[maxx<<2]; int n,m,x,y;inline void pushup(int cur) {int *c1=new int[9];int *c2=new int[9];int len1=p[cur<<1].len;int len2=p[cur<<1|1].len;sort(p[cur<<1].a,p[cur<<1].a+len1);sort(p[cur<<1|1].a,p[cur<<1|1].a+len2);c1=p[cur<<1].a;c2=p[cur<<1|1].a;int len=0;len1--,len2--;while(len<8&&(len1>=0&&len2>=0)){if(c1[len1]>c2[len2]) p[cur].a[len++]=c1[len1],len1--;else p[cur].a[len++]=c2[len2],len2--;}if(len1==-1) while(len<8&&len2>=0) p[cur].a[len++]=c2[len2--];else while(len<8&&len1>=0) p[cur].a[len++]=c1[len1--];while(len<8) p[cur].a[len++]=0;p[cur].len=len; } inline void build(int l,int r,int cur) {p[cur].l=l;p[cur].r=r;p[cur].len=0;memset(p[cur].a,0,sizeof(p[cur].a));if(l==r) return ;int mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1); } inline void update(int pos,int v,int cur) {int L=p[cur].l;int R=p[cur].r;if(L==R) {p[cur].a[0]=v;p[cur].len=1;return ;}int mid=L+R>>1;if(pos<=mid) update(pos,v,cur<<1);else update(pos,v,cur<<1|1);pushup(cur); } inline int *query(int l,int r,int cur) {int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r) return p[cur].a;int mid=L+R>>1;if(r<=mid) return query(l,r,cur<<1);else if(l>mid) return query(l,r,cur<<1|1);else{int *c1=new int[9];c1=query(l,mid,cur<<1);int *c2=new int[9];c2=query(mid+1,r,cur<<1|1);sort(c1,c1+8);sort(c2,c2+8);int *c=new int[9];int len=0,len1=7,len2=7;while(len<8&&(len1>=0&&len2>=0)){if(c1[len1]>c2[len2]) c[len++]=c1[len1],len1--;else c[len++]=c2[len2],len2--;}if(len1==-1) while(len<8&&len2>=0) c[len++]=c2[len2--];else while(len<8&&len1>=0) c[len++]=c1[len1--];return c;} } int main() {scanf("%d%d",&n,&m);build(1,n,1);char s[2];while(m--){scanf("%s%d%d",s,&x,&y);if(s[0]=='C') update(x,y,1);else {int *c=new int[9];c=query(x,y,1);sort(c,c+8);printf("%d\n",c[0]);}}return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的2019蓝桥杯国赛B组第九题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。