题目链接
原题解：
我们需要找出两个距离不超过$k-1$的位置，使他们的和尽量大。
被修改过得位置比较少，所以我们可以先求出连个位置都没有被修改过的答案，然后只关心那些涉及到至少一个被修改过的位置的方案。
我们可以对每个位置维护一个multiset，表示可以和当前位置同时选择的被修改过的位置的值的集合。
我们需要知道每个位置本来的值加上multiset的最大值的最大值。
由于修改某个位置是需要在这个位置左右两边的两个区间的multiset中同时插入或删除一个值，我们可以用线段树维护集合，某个区间的节点上的multiset中的元素代表这个区间中每个multiset里都有一个当前元素。
我们还需要维护区间最大值。
由于每次修改最多引起$O(log N)$次multiset操作，复杂度为$O(n+qlog ^2 n)$。
补充：
用STL来帮助做树套树。只用存修改后的值。
代码（100分）：
#include<cstdio> #define M 3700001 #define N 2097152 inline int min(int u,int v){return u<v?u:v;} inline int max(int u,int v){return u<v?v:u;} int a[N],b[M],c[M],d[M],e[N],f[N],g[N],m,n,p,q,t; inline void add(int u,int v,int w){b[++t]=a[u],c[a[u]=t]=v,d[t]=w;} inline void up(int u){g[u]=max(g[u<<1],g[u<<1|1]);} inline void modify(int u,int v){for(g[u|=m]=v;u>>=1;up(u));} inline int query(int u,int v) { int w=0; for(u+=m-1,v+=m+1;u^v^1;u>>=1,v>>=1) { if(~u&1)w=max(w,g[u^1]); if(v&1)w=max(w,g[v^1]); } return w; } inline void add(int u,int v,int x,int y) { for(u+=m-1,v+=m+1;u^v^1;u>>=1,v>>=1) { if(~u&1)add(u^1,x,y); if(v&1)add(v^1,x,y); } } void dfs(int u,int v) { for(int i=a[u];i;i=b[i])v=max(v,d[i]+query(max(1,c[i]-p+1),min(n,c[i]+p-1))),modify(c[i],d[i]); u<m?dfs(u<<1,v),dfs(u<<1|1,v),0:q<(u^m)?0:printf("%d ",v); for(int i=a[u];i;i=b[i])modify(c[i],0); } int i,u,v,w; int main() { for(scanf("%d%d%d",&n,&p,&q),m=1;m<n+2||m<=q;m<<=1); for(i=1;i<=n;i++)scanf("%d",e+i); for(i=1;i<=q;i++)scanf("%d%d",&u,&v),add(f[u],i-1,u,e[u]),e[u]=v,f[u]=i; for(i=1;i<=n;i++)f[i]?add(f[i],q,i,e[i]):add(1,i,e[i]); return dfs(1,0),0; }