POJ - 4047 Garden 線段樹 區間更新

題目連結：點選檢視

題意：

給出一個N個數的序列以及一個k（0<k<=n<=200000)，m個操作p,x,y，其中

p=0：将x位置的數替換為y

p=1：将x y位置的數互換

p=2:  查詢x-y位置區間連續k個數的和的最大值

題解：每個位置向前取k個數，作為這個位置的結果，線段樹維護下每個區間的最大值即可，當改變一個位置p 的數時，把他所影響的區間（p,p+k-1）更新一下即可，查詢（x，y）區間時，查詢（x+k-1，y）的最大值即可

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200100;
struct node{
	int l,r;
	int laz;
	int maxx;
}tree[N<<2];
int sum[N],a[N];
int n,m,k;
void pushup(int cur)
{
	tree[cur].maxx=max(tree[cur<<1].maxx,tree[cur<<1|1].maxx);
}
void build(int l,int r,int cur)
{
	tree[cur].l=l;
	tree[cur].r=r;
	tree[cur].laz=0;
	if(l==r)
	{
		if(l<k) tree[cur].maxx=-1e9;
		else tree[cur].maxx=sum[l]-sum[l-k];
		return ;
	}
	int mid=(r+l)>>1;
	build(l,mid,cur<<1);
	build(mid+1,r,cur<<1|1);
	pushup(cur);
}
void pushdown(int cur)
{
	if(tree[cur].laz!=0)
	{
		tree[cur<<1|1].maxx+=tree[cur].laz;
		tree[cur<<1|1].laz+=tree[cur].laz;
		tree[cur<<1].maxx+=tree[cur].laz;
		tree[cur<<1].laz+=tree[cur].laz;
		tree[cur].laz=0; 
	}
}
void update(int pl,int pr,int cur,int val)
{
	if(pl<=tree[cur].l&&tree[cur].r<=pr)
	{
		
		tree[cur].maxx+=val;
		tree[cur].laz+=val;
		return;
	}	
	pushdown(cur);
	if(pl<=tree[cur<<1].r) update(pl,pr,cur<<1,val);
	if(pr>=tree[cur<<1|1].l) update(pl,pr,cur<<1|1,val);
	pushup(cur);
}
int query(int pl,int pr,int cur)
{
	if(pl<=tree[cur].l&&tree[cur].r<=pr)
	{
		return tree[cur].maxx;
	}
	int res=-1e9;
	pushdown(cur);
	if(pl<=tree[cur<<1].r) res=max(res,query(pl,pr,cur<<1));
	if(pr>=tree[cur<<1|1].l) res=max(res,query(pl,pr,cur<<1|1));
	return res;
}
int main()
{
	int T;
	int x,y,ll,rr,xx,yy;
	int op;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum[i]=sum[i-1]+a[i];
		}
		build(1,n,1);
		while(m--)
		{
			scanf("%d%d%d",&op,&x,&y);
			if(op==0)
			{
				ll=max(k,x);
				rr=min(n,x+k-1);
				if(ll<=rr)update(ll,rr,1,y-a[x]);
				a[x]=y;
			}
			else if(op==1)
			{
				if(x>y) swap(x,y);
				ll=max(k,x);
				rr=min(n,x+k-1);
				if(ll<=rr) update(ll,rr,1,a[y]-a[x]);
					
				ll=max(k,y);
				rr=min(n,y+k-1);
				if(ll<=rr) update(ll,rr,1,a[x]-a[y]);
					
				swap(a[x],a[y]);

			}
			else
			{
				printf("%d\n",query(x+k-1,y,1));
			}
		}
	}
	return 0;
}