蓝桥杯2019国B-第八大奇迹

题目传送：[P8701 蓝桥杯 2019 国 B] 第八大奇迹 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

第一：静态区间查询第八大第一个想法肯定是主席树，但是太麻烦了，这里略过不提。

第二：可以看到是固定只查询第八大，可以考虑线段树维护前八大即可。pushup用归并排序

代码：

using namespace std;
#include<iostream>

const int maxn=1e5+10;

struct node{
	int v[8]={0};
}t[maxn<<2];//每个节点记录这个区间的前八大 

inline void pushup(node & x,node & l,node & r)//用归并排序思想合并 
{
	int p1=0,p2=0,p=0;
	
	while(p<8&&p1<8&&p2<8)
		if(l.v[p1]>r.v[p2])x.v[p++]=l.v[p1++];
		else x.v[p++]=r.v[p2++];	
}

inline void modify(int x,int l,int r,int &dist ,int &v)
{
	if(l==r)
	{
		t[x].v[0]=v;
		return;
	}
	
	int mid=l+r>>1;
	
	if(mid>=dist)modify(x<<1,l,mid,dist,v);
	else modify(x<<1|1,mid+1,r,dist,v);
	
	pushup(t[x],t[x<<1],t[x<<1|1]);
}

inline node query(int x,int l,int r,int &L,int &R)
{
	if(l>=L&&r<=R)return t[x];
	
	int mid=l+r>>1;
	node t1,t2,ans;
	
	if(mid>=L)t1=query(x<<1,l,mid,L,R);
	if(mid<R)t2=query(x<<1|1,mid+1,r,L,R);
	
	pushup(ans,t1,t2);
	
	return ans;
}

int l,n,x,y;
char op;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>l>>n;
	
	while(n--)
	{
		cin>>op>>x>>y;
		
		if(op=='C')modify(1,1,l,x,y);
		else cout<<query(1,1,l,x,y).v[7]<<'\n';
	}
	return 0;
}