题解：P6717 [CCO 2018] Boring Lectures

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=1e6+5;
int n,k,q;
int a[Maxn];
struct tree{
	int t[Maxn<<2];
	void change(int x,int l,int r,int d,int p){
		if(l==r)return void(t[x]=p);
		int mid=l+r>>1;
		if(mid>=d)change(x<<1,l,mid,d,p);
		else change(x<<1|1,mid+1,r,d,p);
		t[x]=max(t[x<<1],t[x<<1|1]);
	}
	int query(int x,int l,int r,int L,int R){
		if(L<=l&&r<=R)return t[x];
		int mid=l+r>>1,res=0;
		if(mid>=L)res=query(x<<1,l,mid,L,R);
		if(mid<R)res=max(res,query(x<<1|1,mid+1,r,L,R));
		return res;
	}
}A;
struct node{
	int id,val;
};
vector<node>t[Maxn<<2];
void change(int x,int l,int r,int L,int R,node g){
	if(L>R)return;
	if(L<=l&&r<=R)return void(t[x].push_back(g));
	int mid=l+r>>1;
	if(mid>=L)change(x<<1,l,mid,L,R,g);
	if(mid<R)change(x<<1|1,mid+1,r,L,R,g);
}
int last[Maxn];
stack<node>stk;
void dfs(int x,int l,int r,int ans){
	int siz=stk.size();
	for(node i:t[x]){
		int id=i.id;
		int val=A.query(1,1,n,id,id);
		A.change(1,1,n,id,0);
		ans=max(ans,A.query(1,1,n,max(1,id-k+1),min(n,id+k-1))+i.val);
		A.change(1,1,n,id,i.val);
		stk.push({id,val});
	}
	if(l==r){
		printf("%d\n",ans);
	}
	else{
		int mid=l+r>>1;
		dfs(x<<1,l,mid,ans);
		dfs(x<<1|1,mid+1,r,ans);
	}
	while(stk.size()>siz){
		A.change(1,1,n,stk.top().id,stk.top().val);
		stk.pop();
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();k=read();q=read()+1;
	for(int i=1;i<=n;i++)a[i]=read(),last[i]=1;
	for(int i=2;i<=q;i++){
		int id=read(),val=read();
		change(1,1,q,last[id],i-1,(node){id,a[id]});
		a[id]=val;last[id]=i;
	}
	for(int i=1;i<=n;i++)change(1,1,q,last[i],q,(node){i,a[i]});
	dfs(1,1,q,0);
	return 0;
}