Posted on 2011-11-15 09:26
C小加 阅读(3813)
评论(1) 编辑 收藏 引用 所属分类:
解题报告
第二个线段树，超时了两次， 原因是读数据的时候忘了加上EOF，郁闷。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=200003;
const int INF=0x7fffffff-1;
int v[MAXN],sum;
typedef struct
{
int left,right,mid;
int count;
}line;
line l[4*MAXN];
void Creat(int a,int b,int r)
{
if(a==b)
{
l[r].left=l[r].right=a;
l[r].count=v[a];
return;
}
l[r].left=a;
l[r].right=b;
l[r].mid=(a+b)>>1;
Creat(a,l[r].mid,r<<1);
Creat(l[r].mid+1,b,(r<<1)+1);
l[r].count=max(l[r<<1].count,l[(r<<1)+1].count);
}
void Add(int n,int m,int r)
{
if(l[r].left==n&&l[r].right==n)
{
l[r].count=m;
return;
}
if(n>l[r].mid)
{
Add(n,m,(r<<1)+1);
}
else
{
Add(n,m,r<<1);
}
l[r].count=max(l[r<<1].count,l[(r<<1)+1].count);
}
int Query(int a,int b,int r)
{
if(l[r].left==a&&l[r].right==b)
{
return l[r].count;
}
else if(a>l[r].mid)
{
return Query(a,b,2*r+1);
}
else if(b<=l[r].mid)
{
return Query(a,b,2*r);
}
else
{
int x=Query(a,l[r].mid,r<<1);
int y=Query(l[r].mid+1,b,(r<<1)+1);
return max(x,y);
}
}
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
Creat(1,n,1);
char s[2];
for(int i=0;i<m;i++)
{
scanf("%s",s);
int b,c;
scanf("%d %d",&b,&c);
if(s[0]=='Q')
{
printf("%d\n",Query(b,c,1));
}
else
{
Add(b,c,1);
}
}
}
return 0;
}