2013
12-21

# I Hate It

5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

5
6
5
9

HintHuge input,the C function scanf() will work better than cin 

#include <stdio.h>

int max(int d,int b)//这里如果用inline会加速好多啊
{
return d>b?d:b;
}

#define  MAXN  2000000
int a[MAXN+5];

struct node
{
int left;
int right;
int sum;
} b[MAXN*2];

void build(int left , int right , int i)//为left，right ，sum赋值
{
int mid;
b[i].left=left;
b[i].right=right;
if(left==right)
{
b[i].sum=a[left];
return ;
}

mid=(left+right)/2;
build(left,mid,2*i);
build(mid+1,right,2*i+1);
b[i].sum=max(b[2*i].sum , b[2*i+1].sum);

}

void  Update(int id,int value,int i)
{
if(b[i].left==b[i].right)
{
b[i].sum=value;
return ;
}

int mid =(b[i].left+b[i].right)/2;
if(mid>=id) Update(id,value,2*i);
if(id>mid) Update(id ,value,2*i+1);
b[i].sum=max(b[i*2].sum , b[2*i+1].sum);//注意更新的时候不仅更新子节点，还要更新父节点

}

int Query(int left, int right,int i)
{
int mid;
if(b[i].left==left && b[i].right ==right) return b[i].sum;
mid=(b[i].left+b[i].right)/2;
if(right<=mid) return Query(left,right,2*i);
if (left>mid ) return Query(left,right,2*i+1);
if(left<=mid && mid<right)
return max(Query(left,mid,2*i) , Query(mid+1,right,2*i+1));
}

int main()
{
int n,m;
char c;
int id,value;
int i;
while(scanf("%d%d",&n,&m)!=EOF)
{
//scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
build(1,n,1);
for(i=0;i<m;i++)
{
scanf("%c",&c);
scanf("%d%d",&id,&value);
if(c=='U') Update(id,value,1);
if(c=='Q') printf("%d\n",Query(id,value,1));
}
}
return 0;
}

char c 中，在最下面贴最新的代码

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN=2000000;

int n,m,a[MAXN+5];

struct tree
{
int l,r;

int v;

}trees[MAXN*2];

int max(int k,int l)
{
return k>l?k:l;
}

void buildtree(int rs,int l,int r)
{
//printf("%d %d %d\n",rs,l,r);
trees[rs].l=l;
trees[rs].r=r;
if(r==l)
{
trees[rs].v=a[l];
return ;
}

int mid=(l+r)/2;

buildtree(rs*2,l,mid);
buildtree(rs*2+1,mid+1,r);

trees[rs].v=max(trees[rs*2].v,trees[rs*2+1].v);
}

void update(int rs,int k,int l)
{
//printf("%d %d %d %d %d\n",rs,k,l,trees[rs].l,trees[rs].r);

if(trees[rs].l==k&&trees[rs].r==k)
{
trees[rs].v=l;
return ;
}

int mid=(trees[rs].l+trees[rs].r)/2;

if(k<=mid)update(rs*2,k,l);
if(k>mid)update(rs*2+1,k,l);

trees[rs].v=max(trees[rs*2].v,trees[rs*2+1].v);
}

int querry(int rs,int l,int r)
{
//printf("%d %d %d\n",rs,l,r);
if(trees[rs].l==l&&trees[rs].r==r)
return trees[rs].v;

int mid=(trees[rs].l+trees[rs].r)/2;

if(r<=mid)return querry(rs*2,l,r);
if(l>mid)return querry(rs*2+1,l,r);
if(l<=mid&&r>mid)
return max(querry(rs*2,l,mid),querry(rs*2+1,mid+1,r));

return 0;
}

int main()
{
int i,ac,bc;

char c;

while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);

buildtree(1,1,n);

for(i=1;i<=m;i++)
{
getchar();

scanf("%c%d%d",&c,&ac,&bc);

if(c=='Q')
printf("%d\n",querry(1,ac,bc));
else
update(1,ac,bc);
}
}

return 0;
}

1. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯