题意：
给长度为n的序列及k(0<k<=n<=200000),m个操作p,x,y。其中(1）p==0:将x位置处的数变为y;(2)p==1：将x,y位置处的数互换。（3）p==2查询x-y位置之间连续k个数的和的最大值。
分析：
求连续区间的和最大，可以把区间看成一个点，这样这n-k+1个区间的最大和可以看做n-k+1个点的最大值，当更新原序列中位置x的值就相当于更新区间中x-k+1到x区间的值，然后用线段树做成段更新。成段更新要用到lazy标记，我的理解是：当更新或query的时候如果当前区间满足要求（T[k].l==s&&T[k].r==t）直接标记lazy并返回。否则将当前的lazy赋给它的子区间（父区间满足的性质子区间也满足，这是线段树中比较重要的思想），然后继续往下更新或query.注意更新后子区间的性质有变化，要向上更新父区间（这样才能保证父区间满足的性质子区间也满足）。
代码：
<pre name="code" class="cpp">//poj 4047
//sep9
#include <iostream>
using namespace std;
const int maxN=200012;
struct Node
{int l,r,maxx,lazy;
}T[maxN*4];
int n,m,k;
int v[maxN],b[maxN];
int build(int l,int r,int k)
{int mid=(l+r)>>1;T[k].l=l;T[k].r=r;T[k].lazy=0;if(l==r){T[k].maxx=b[l];return T[k].maxx;}int x=build(l,mid,2*k);int y=build(mid+1,r,2*k+1);T[k].maxx=max(x,y);return T[k].maxx;
}
int query(int s,int t,int k)
{if(T[k].l==s&&T[k].r==t)return T[k].maxx+T[k].lazy;T[2*k].lazy+=T[k].lazy;T[2*k+1].lazy+=T[k].lazy;T[k].maxx+=T[k].lazy;T[k].lazy=0;if(t<=T[2*k].r)return query(s,t,2*k);else if(s>T[2*k].r)return query(s,t,2*k+1);else{int x=query(s,T[2*k].r,2*k);int y=query(T[2*k+1].l,t,2*k+1);return max(x,y);}
}void update(int s,int t,int k,int c)
{if(T[k].l==s&&T[k].r==t){T[k].lazy+=c;return ;}T[2*k].lazy+=T[k].lazy;T[2*k+1].lazy+=T[k].lazy;T[k].maxx+=T[k].lazy;T[k].lazy=0;if(t<=T[2*k].r)update(s,t,2*k,c);else if(s>T[2*k].r)update(s,t,2*k+1,c);else{update(s,T[2*k].r,2*k,c);update(T[2*k+1].l,t,2*k+1,c);} T[k].maxx=max(T[2*k].maxx+T[2*k].lazy,T[2*k+1].maxx+T[2*k+1].lazy);
}int main()
{int cases;scanf("%d",&cases);while(cases--){scanf("%d%d%d",&n,&m,&k);memset(b,0,sizeof(b));for(int i=1;i<=n;++i)scanf("%d",&v[i]);for(int i=1;i<=k;++i)b[1]+=v[i];for(int i=2;i<=n-k+1;++i)b[i]=b[i-1]-v[i-1]+v[i+k-1]; build(1,n-k+1,1);while(m--){int q,x,y;scanf("%d%d%d",&q,&x,&y);if(q==0){update(max(1,x-k+1),min(n-k+1,x),1,y-v[x]);v[x]=y;}else if(q==1){update(max(1,x-k+1),min(n-k+1,x),1,v[y]-v[x]);update(max(1,y-k+1),min(n-k+1,y),1,v[x]-v[y]);swap(v[x],v[y]);}elseprintf("%d\n",query(x,y-k+1,1)); }}return 0;
}