有n個(gè)格子，從左到右放成一排，編號(hào)為1-n。

共有m次操作，有3種操作類型：

1.修改一個(gè)格子的權(quán)值，

2.求連續(xù)一段格子權(quán)值和，

3.求連續(xù)一段格子的最大值。

對(duì)于每個(gè)2、3操作輸出你所求出的結(jié)果。

第一行2個(gè)整數(shù)n，m。

接下來一行n個(gè)整數(shù)表示n個(gè)格子的初始權(quán)值。

接下來m行，每行3個(gè)整數(shù)p,x,y，p表示操作類型，p=1時(shí)表示修改格子x的權(quán)值為y，p=2時(shí)表示求區(qū)間[x,y]內(nèi)格子權(quán)值和，p=3時(shí)表示求區(qū)間[x,y]內(nèi)格子最大的權(quán)值。

有若干行，行數(shù)等于p=2或3的操作總數(shù)。

每行1個(gè)整數(shù)，對(duì)應(yīng)了每個(gè)p=2或3操作的結(jié)果。

對(duì)于20%的數(shù)據(jù)n <= 100，m <= 200。

對(duì)于50%的數(shù)據(jù)n <= 5000，m <= 5000。

對(duì)于100%的數(shù)據(jù)1 <= n <= 100000，m <= 100000，0 <= 格子權(quán)值 <= 10000。

思路:線段樹模板！就是最大值這個(gè)地方我有點(diǎn)搞混了；；；

#include<bits/stdc++.h>#define N 100010using namespace std;int t[4*N],tt[4*N],a[N];int s,maxn;void build(int l,int r,int d){	if(l==r)	{		t[d]=a[l];		tt[d]=a[l];		return ;	}	int mid=(l+r)/2;	build(l,mid,2*d);	build(mid+1,r,2*d+1);	t[d]=t[2*d]+t[2*d+1];	tt[d]=max(tt[2*d],tt[2*d+1]);	return ;}void update(int pos,int l,int r,int d,int num)//單點(diǎn)更新{	if(l==r)	{		t[d]=num;		tt[d]=num;		return ;	}	int mid=(l+r)/2;	if(pos<=mid)		update(pos,l,mid,2*d,num);	else		update(pos,mid+1,r,2*d+1,num);	t[d]=t[2*d]+t[2*d+1];	tt[d]=max(tt[2*d],tt[2*d+1]);	return ;}int query(int l,int r,int L,int R,int d)//和查詢{	if(l==L&&r==R)	{	 	return t[d];	}	int mid=(L+R)/2;	if(r<=mid)	{		return query(l,r,L,mid,2*d);	}	else if(l>mid)	{		return query(l,r,mid+1,R,2*d+1);	}	else	return  query(l,mid,L,mid,2*d)+query(mid+1,r,mid+1,R,2*d+1);//左右都需要查詢的時(shí)候傳入的 參數(shù)都是mid 和mid+1}int queryma(int l,int r,int L,int R,int d)//查詢最大值{	if(l<=L&&R<=r)		return tt[d];	int mid=(L+R)/2;	int ret=0;	if(l<=mid)//有區(qū)間在左面,就查詢左區(qū)間的最大值	ret=max(ret,queryma(l,r,L,mid,2*d));	if(r>mid)	ret=max(ret,queryma(l,r,mid+1,R,2*d+1));//有區(qū)間在右面就查詢右區(qū)間的最大值	return ret;	}int main(){	int p,x,y,n,m,s;	scanf("%d %d",&n,&m);	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);	build(1,n,1);	for(int i=0;i<m;i++)	{		scanf("%d %d %d",&p,&x,&y);		if(p==1)		{			update(x,1,n,1,y);		}		else  if(p==2)		{			 s=query(x,y,1,n,1);			 PRintf("%d/n",s);		}		else		{	maxn=queryma(x,y,1,n,1);			 printf("%d/n",maxn);		}	}}