线段树模板题

题面描述

给定一个包含n个数的序列，初值全为0，现对这个序列有两种操作：

操作1：把 给定 第k1 个数改为k2;

操作2：查询 从第k1个数到第k2个数得最大值。（k1<=k2<=n）

所有的数都 <=100000

输入格式

第一行给定一个整数n，表示有n个操作。

以下接着n行，每行三个整数，表示一个操作。

第一个树表示操作序号，第二个数为k1，第三个数为k2

输出格式

若干行，查询一次，输出一次。

样例

线段树模板题，单点修改，区间查询，维护一下最大值，直接套模板

#include <bits/stdc++.h>
using namespace std ;
const int io=100200;
struct hf
{
	int l,r;
	int dat;
}a[io*4];
int qw[io];
void b(int p,int l,int r)
{
	a[p].l=l,a[p].r=r;
	if(l==r)
	{
		a[p].dat=qw[l];return ;
	}
	int mid=(l+r)/2;
	b(p*2,l,mid);
	b(p*2+1,mid+1,r);
	a[p].dat=max(a[p*2].dat,a[p*2+1].dat);
}
int ask(int p,int l,int r)
{
	if(l<=a[p].l&&r>=a[p].r)
	return a[p].dat;
	int mid=(a[p].l+a[p].r)/2;
	int v=-(1<<30);
	if(l<=mid)
	v=max(v,ask(p*2,l,r));
	if(r>mid)
	v=max(v,ask(p*2+1,l,r));
	return v;
}
void ch(int p,int x,int v)
{
	if(a[p].l==a[p].r)
	{
		a[p].dat=v;
		return;
	}
	int mid=(a[p].l+a[p].r)/2;
	if(x<=mid)
	ch(p*2,x,v);
	else
	ch(p*2+1,x,v);
	a[p].dat=max(a[p*2].dat,a[p*2+1].dat);
}
int main()
 {
 	freopen("a.in","r",stdin);
 	freopen("a.out","w",stdout);
	 int n,m;
	 cin>>n;
	  b(1,1,n);//建树 
	 while(n--)
	 {
	 	int x,y,z;
	 	cin>>x>>y>>z;
	 	if(x==1)
	 	{
	 		ch(1,y,z);//把数组中[3]的值改为999 
	 	}
	 	if(x==2)
	 	{
	 		cout<<ask(1,y,z)<<endl;//查询2到5的最大值 
	 	}
	}
	return 0;
}