CSUST 2013 丢手绢 （线段树）

链接： 丢手绢

题意：
n个数编号为 1 - n 围成一个环，给出 q 次操作，点修改，和查询 相距不超过k的两个数字之和的最大值和最小值。
思路：
注意数据范围 k 最大是 5 ，我们可以 o （ n ）的求出每个长度为 k 的区间里的 最大值次大值，最小值次小值，也就可以得到答案，但是还有修改，因为每次修改，最多改变 k 个区间的最值，所以我们还是可以直接修改这个小区间的最值 ，但这还不是我们要求的，我们可以把每个点的权值定义为 以当前位置为左边界长度为 k的区间的两数字之和的最大值，然后用线段树维护这个最大值，就可以得到答案了，每次修改相当于 k 次单点修改。

代码：

#include <iostream>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
int val[maxn],n,q,k;
struct node{int mx,mmx,mn,mmn;
}e[maxn];
int ans1[maxn],ans2[maxn];
void pushup(int rt){ans1[rt] = max (ans1[rt<<1],ans1[rt<<1|1]);ans2[rt] = min (ans2[rt<<1],ans2[rt<<1|1]);
}
void update1(int i,int c1,int c2,int l,int r,int rt){   if(l == r) {ans1[rt] = c1;ans2[rt] = c2;return;}ll m=(l + r) >> 1;if(i <= m) update1(i,c1,c2,l,m,rt<<1);else update1(i,c1,c2,m+1,r,rt<<1|1);pushup(rt);
}
void update (int pos, int x){val[pos] = x;for(int s = 0; s <= k; s ++){int i = (pos - s + n) % n;e[i].mx=0,e[i].mmx=0,e[i].mn=1e9+7,e[i].mmn=1e9+7;for(int j = i; j <= i + k; j ++){if(val[j % n] >= e[i].mx){e[i].mmx=e[i].mx;e[i].mx=val[j % n];}else if(val[ j % n] > e[i].mmx){e[i].mmx=val[j % n];}if(val[j % n] <= e[i].mn){e[i].mmn=e[i].mn;e[i].mn=val[j % n];}else if(val[ j % n] < e[i].mmn){e[i].mmn=val[j % n];}}update1(i+1,e[i].mx+e[i].mmx,e[i].mn+e[i].mmn,1,n,1);}
}
int main(){scanf("%d",&n);for(int i = 0; i < n; i ++)  scanf("%lld", &val[i]);scanf("%d%d",&q,&k);for(int i = 0; i < n; i++)   update(i,val[i]);while(q--){int op,p,x;scanf("%d",&op);if(op == 1){scanf("%d%d",&p,&x);update(p-1,x);}if(op==2){printf ("%d %d\n",ans1[1],ans2[1]);} }
}