P1531 I Hate It

题目大意:

n个学生，告知你每位学生的成绩，m次查询，
每一行有一个字符 C (只取’Q’或’U’) ，和两个正整数A，B。当C为’Q’的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。当C为’U’的时候，表示这是一条更新操作，如果当前A学生的成绩低于B，则把ID为A的学生的成绩更改为B，否则不改动。

思路:

很明显的区间查询，单点修改，维护区间最大值即可
线段树模板题

AC Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+9;
struct node{
    int score;
}a[N];
struct segtree{
    int v, tag;
}tr[N<<2];
inline int read()
{
    int ans=0;
    char last=' ',ch=getchar();
    while(ch<'0'||ch>'9') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}
inline int lc(int p)   {return p<<1;}
inline int rc(int p)   {return p<<1|1;}
inline void build(int k, int l, int r){
    if(l==r)    {tr[k].v=a[l].score; return ;}
    int mid=(l+r)>>1;
    build(lc(k), l, mid);
    build(rc(k), mid+1, r);
    tr[k].v=max(tr[lc(k)].v,tr[rc(k)].v);
}
inline void f(int p, int k){
    tr[p].v=max(tr[p].v, k);
    tr[p].tag=max(tr[p].tag, k);
}
inline void push_down(int p){
    f(lc(p), tr[p].tag);
    f(rc(p), tr[p].tag);
    tr[p].tag=0;
}
inline void push_up(int p)  {tr[p].v=max(tr[lc(p)].v, tr[rc(p)].v);}
inline void updata(int p, int l, int r, int x, int y, int k){
    if(x>r || y<l)  return ;
    if(l<=x && y<=r){
        tr[p].v=max(tr[p].v, k);
        tr[p].tag=max(tr[p].tag,k);
        return ;
    }  
    int mid=(x+y)>>1;
    if(tr[p].tag) push_down(p);
    updata(lc(p), l, r, x, mid, k);
    updata(rc(p), l, r, mid+1, y, k);
    push_up(p);
}
inline int query(int p, int l, int r, int x, int y){
    if(x>r || y<l)  return 0;
    if(l<=x && y<=r) return tr[p].v;
    int mid=(x+y)>>1;
    if(tr[p].tag) push_down(p);
    return max(query(lc(p), l, r, x, mid), query(rc(p), l, r, mid+1, y));
}
int main(){
    int n=read();
    int m=read();
    for(int i=1; i<=n; i++){
        a[i].score=read();
    }
    build(1,1,N);
    char op;
    int x, y;
    for(int i=1; i<=m; i++){
        cin>>op>>x>>y;
        if(op=='Q') cout<<query(1,x,y,1,N)<<endl;
        if(op=='U'){
            int s1=query(1,x,x,1,N);
            if(s1<y)   updata(1,x,x,1,N,y);
        }
    }
    return 0;
}

I Hate It

题目大意:

跟洛谷的题差不多，只不过修改是直接修改，而不是比之前的值大才修改
注意多组输入！
注意多组输入！
注意多组输入！

AC Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+9;
struct node{
    int score;
}a[N];
struct segtree{
    int v, tag;
}tr[N<<2];
inline int read()
{
    int ans=0;
    char last=' ',ch=getchar();
    while(ch<'0'||ch>'9') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}
inline int lc(int p)   {return p<<1;}
inline int rc(int p)   {return p<<1|1;}
inline void push_up(int p)  {tr[p].v=max(tr[lc(p)].v, tr[rc(p)].v);}
inline void build(int k, int l, int r){
    if(l==r)    {tr[k].v=a[l].score; return ;}
    int mid=(l+r)>>1;
    build(lc(k), l, mid);
    build(rc(k), mid+1, r);
    push_up(k);
}

inline void updata(int p, int l, int r, int x, int y, int k){
    if(x>r || y<l)  return ;
    if(l<=x && y<=r){
        tr[p].v=k;
        return ;
    }  
    int mid=(x+y)>>1;
    updata(lc(p), l, r, x, mid, k);
    updata(rc(p), l, r, mid+1, y, k);
    push_up(p);
}
inline int query(int p, int l, int r, int x, int y){
    if(x>r || y<l)  return 0;
    if(l<=x && y<=r) return tr[p].v;
    int mid=(x+y)>>1;
    return max(query(lc(p), l, r, x, mid), query(rc(p), l, r, mid+1, y));
}
int main(){
    int n, m;
    while(~scanf("%d%d", &n, &m)){
        for(int i=1; i<=n; i++) a[i].score=read();
        build(1,1,n);
        char op;
        int x, y;
        for(int i=1; i<=m; i++){
            cin>>op>>x>>y;
            if(op=='Q') cout<<query(1,x,y,1,n)<<endl;
            if(op=='U') updata(1,x,x,1,n,y);
        }
    }
    return 0;
}