解题报告 HDU1754 I HATE IT

题目内容

hdu1754

题意

维护一些学生成绩,支持单点修改和区间求最值操作

解题思路

嗯,造一棵线段树即可

#include <bits/stdc++.h>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)
#define f(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=200000+5;

int a[maxn],f[maxn<<2];

void build(int i,int j,int k)//造树
{
    if(i==j) f[k]=a[i];
    else
    {
        build(i,M,L);
        build(M+1,j,R);
        f[k]=max(f[L],f[R]);
    }
    return;
}

void modify(int u,int d,int i,int j,int k)//单点编辑操作
{
    if(i==j) f[k]=d;
    else
    {
        if(u<=M) modify(u,d,i,M,L);
        if(u>M) modify(u,d,M+1,j,R);
        f[k]=max(f[L],f[R]);//每次操作完记得回溯
    }
    return;
}

int query(int u,int v,int i,int j,int k)//区间查询操作
{
    if(u==i&&v==j) return f[k];
    else
    {
        if(v<=M) return query(u,v,i,M,L);
        if(u>M) return query(u,v,M+1,j,R);
    }
    return max(query(u,M,i,M,L),query(M+1,v,M+1,j,R));
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        f(i,1,n) scanf("%d",&a[i]);
        build(1,n,1);
        getchar();//嗯,读入回车符把我坑死了
        f(i,1,m)
        {
            char c;int a,b;
            scanf("%c %d %d\n",&c,&a,&b);//记得读入回车符
            if(c=='U') modify(a,b,1,n,1);
            if(c=='Q') printf("%d\n",query(a,b,1,n,1));
        }
    }
    return 0;
}

反思

tmd这个回车符把我弄得要死不活的
要么使用cin(怎么可能),要么使用getchar()直接读入回车符,要么使用scanf的格式化功能直接把回车符干掉。

然后每组数据读入完之后记得memset即可

发表评论

电子邮件地址不会被公开。 必填项已用*标注