自动搬运

查看原文

来自洛谷，原作者为

	Pengzt 自己选择的路，跪着也要走完。

搬运于2025-08-24 22:41:35，当前版本为作者最后更新于2023-10-02 23:11:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8701

显然可以直接将维护的值变为区间前 $8$ 大，为实现的简洁，可使用 vector，使用归并合并信息达到 $\mathcal{8n\log n}$。由于偷懒，归并部分我直接写的 sort，加上 vector 的大常数，加 O2 后即可通过。

时间复杂度：$\mathcal{O}(8n\log n)$。

代码：

#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back

const int N=1e5+10;
int n,m;
vector<int> tr[N<<2];
vector<int> operator+(vector<int> a,vector<int> b){
	vector<int> c=a;
	for(int i:b)c.pb(i);
	return c;
}
void pushup(int u){
	tr[u]=tr[u<<1]+tr[u<<1|1];
	sort(tr[u].begin(),tr[u].end(),greater<int>());
	while(tr[u].size()>8)tr[u].pop_back();
}
void update(int u,int l,int r,int k,int val){
	if(l==r){
		tr[u].clear();tr[u].pb(val);
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid)update(u<<1,l,mid,k,val);
	else update(u<<1|1,mid+1,r,k,val);
	pushup(u);
}
vector<int> query(int u,int l,int r,int L,int R){
	if(L<=l&&r<=R)return tr[u];
	int mid=(l+r)>>1;
	vector<int> vec;
	if(L<=mid)vec=vec+query(u<<1,l,mid,L,R);
	if(mid<R)vec=vec+query(u<<1|1,mid+1,r,L,R);
	sort(vec.begin(),vec.end(),greater<int>());
	while(vec.size()>8)vec.pop_back();
	return vec;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		char opt;int x,y;
		cin>>opt>>x>>y;
		if(opt=='C')update(1,1,n,x,y);
		else{
			vector<int> tmp=query(1,1,n,x,y);
			if(tmp.size()==8)cout<<tmp.back()<<"\n";
			else cout<<0<<"\n";
		}
	}
	return 0;
}