HDU - 1754 I Hate It(简单线段树 单点更新+区间查询)

HDU - 1754 http://acm.hdu.edu.cn/showproblem.php?pid=1754
思路：单点更新+区间查询

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 200000+10;
int n,m;
struct node
{
int v;
int l,r;
    node(int a,int b = -1,int c = -1)
    {   v = a; l = b; r = c;    }
    node(){}
}segtree[maxn << 2];
int data[maxn];

int bulid_tree(int l,int r,int id)
{
    segtree[id].l = l, segtree[id].r = r;
if(l == r)  {segtree[id].v = data[l]; return data[l];}
int mid = (l+r) >> 1;

int a = bulid_tree(l,mid,id<<1);
int b = bulid_tree(mid+1,r,id<<1|1);
return segtree[id].v = max(a,b);
}

int updata(int i,int v,int id)
{
int l = segtree[id].l, r = segtree[id].r;
if(l == r && r == i)    {segtree[id].v = v; return v;}
if(r < i || l > i) return 0;
int mid = (l+r)>>1;

if(mid < i) updata(i,v,id<<1|1);
else updata(i,v,id<<1);
return segtree[id].v = max(segtree[id<<1].v,segtree[id<<1|1].v);
}

int query(int ql,int qr,int id)
{
int l = segtree[id].l, r = segtree[id].r;
if(l == ql && r == qr) return segtree[id].v;
if(r < ql || l > ql) return 0;
int mid = l+r>>1;
int ans = 0;
if(qr <= mid)
        ans = query(ql,qr,id<<1);
else if(ql > mid)
        ans = query(ql,qr,id<<1|1);
else
        ans = max(query(ql,mid,id<<1),query(mid+1,qr,id<<1|1));
return ans;
}
int main()
{
while(~scanf("%d%d",&n,&m))
    {
for(int i = 1; i <= n ; i++)
            scanf("%d",&data[i]);
        bulid_tree(1,n,1);
//cout<<"yes"<<endl;
for(int i = 0; i < m ; i++)
        {
char s[5];
int a,b;
            scanf("%s%d%d",s,&a,&b);
if(s[0] == 'Q')
                printf("%d\n",query(a,b,1));
else
                updata(a,b,1);
        }
    }
return 0;
}

//树状数组代码，但是这个未能理解，参考了别人的代码

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

const int maxn = 200000+10;
int n,m;
int a[maxn],b[maxn];
int lowbit(int x)
{   return x & -x;  }

void updata(int x)
{
int lx,i;
for(; x <= n; x += lowbit(x))
    {
        b[x] = a[x];
        lx = lowbit(x);
for(i = 1; i < lx; i = (i<<1))
            b[x] = max(b[x],b[x-i]);
    }
}
int query(int x,int y)
{
int ans = 0;
while(x <= y)
    {
        ans = max(a[y--],ans);
for(; y - lowbit(y) >= x; y -= lowbit(y))
            ans = max(ans, b[y]);
    }
return ans;
}

int main()
{

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

for(int i = 0; i < m ; i++)
        {
char s[5]; int x,y;
scanf("%s%d%d",s,&x,&y);
if(s[0] == 'U') a[x] = y,updata(x);
else printf("%d\n",query(x,y));
        }
    }

return 0;
}