HDU 1754 I Hate It (线段树,模板)

Description

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。

这让很多学生很反感。

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。

 

Input

本题目包含多组测试,请处理到文件结束。

在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。

学生ID编号分别从1编到N。

第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。

接下来有M行。每一行有一个字符 C (只取'Q'或'U') ,和两个正整数A,B。

当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。

当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。

 

Output

对于每一次询问操作,在一行里面输出最高成绩。

 

Sample Input

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

 

Sample Output

5
6
5
9

 

思路

线段树模板题,附 [点/区间] 修改模板如下。

 

AC 代码

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);
#define default_setv -1

using namespace std;
typedef long long LL;
const int maxn = 2e5+10;

int sumv[maxn<<2];  //四倍空间
int minv[maxn<<2];
int maxv[maxn<<2];
int addv[maxn<<2];
int setv[maxn<<2];  //初始值:-1
int a[maxn];

void maintain(int o,int L,int R)
{
    int lc = o<<1,rc=o<<1|1;
    sumv[o] = minv[o] = maxv[o] = 0;
    if(setv[o] != default_setv)
    {
        sumv[o] = setv[o] * (R-L+1);
        minv[o] = maxv[o] = setv[o];
    }
    else if(R>L)
    {
        sumv[o] = sumv[lc] + sumv[rc];
        minv[o] = min(minv[lc],minv[rc]);
        maxv[o] = max(maxv[lc],maxv[rc]);
    }
    minv[o] += addv[o];
    maxv[o] += addv[o];
    sumv[o] += addv[o] * (R-L+1);
}

void pushdown(int o)
{
    int lc = o<<1,rc = o<<1|1;
    if(setv[o] != default_setv)
    {
        setv[lc] = setv[rc] = setv[o];
        addv[lc] = addv[rc] = 0;
        setv[o] = default_setv;
    }
    if(addv[o] != 0)
    {
        addv[lc] += addv[o];
        addv[rc] += addv[o];
        addv[o] = 0;
    }
}

/*
 * o: 当前节点(1),修改区间:[y1,y2] ,添加值:v_add,总区间:[L,R] (这里的L,R必须是2的幂次)
 */
void update_add(int o,int L,int R,int y1,int y2,int v_add)
{
    int lc = o<<1,rc = o<<1|1;
    if(y1<=L&&y2>=R)
        addv[o] += v_add;
    else
    {
        pushdown(o);
        int M = L + (R-L)/2;
        if(y1<=M)
            update_add(lc,L,M,y1,y2,v_add);
        else
            maintain(lc,L,M);
        if(y2>M)
            update_add(rc,M+1,R,y1,y2,v_add);
        else
            maintain(rc,M+1,R);
    }
    maintain(o,L,R);
}

/*
 * o: 当前节点(1),修改区间:[y1,y2] ,修改值:v_set,总区间:[L,R] (这里的L,R必须是2的幂次)
 */
void update_set(int o, int L, int R,int y1,int y2,int v_set)
{
    int lc = o<<1, rc = o<<1|1;
    if(y1 <= L && y2 >= R)
    {
        setv[o] = v_set;
        addv[o] = 0;
    }
    else
    {
        pushdown(o);
        int M = L + (R-L)/2;
        if(y1 <= M)
            update_set(lc, L, M,y1,y2,v_set);
        else
            maintain(lc, L, M);
        if(y2 > M)
            update_set(rc, M+1, R,y1,y2,v_set);
        else
            maintain(rc, M+1, R);
    }
    maintain(o, L, R);
}

/*
 * o: 当前节点(1),查询区间:[y1,y2] ,初始累加(0),总区间:[L,R] (这里的L,R必须是2的幂次)
 */
int _min, _max, _sum;
void query(int o, int L, int R, int y1,int y2, int add)
{
    if(setv[o] != default_setv)
    {
        _sum += (add+setv[o]+addv[o]) * (min(R, y2)-max(L, y1)+1);
        _min = min(_min, setv[o]+addv[o]+add);
        _max = max(_max, setv[o]+addv[o]+add);
    }
    else if(y1 <= L && y2 >= R)
    {
        _sum += sumv[o] + add * (R-L+1);
        _min = min(_min, minv[o]+add);
        _max = max(_max, maxv[o]+add);
    }
    else
    {
        int M = L + (R-L)/2;
        if(y1 <= M)
            query(o*2, L, M, y1, y2,add+addv[o]);
        if(y2 > M)
            query(o*2+1, M+1, R, y1, y2, add + addv[o]);
    }
}

/*
 * o: 当前节点(1),总区间:[L,R] (这里的L,R必须是2的幂次)
 * 所有 setv 初始化为 -1,所有叶子节点 addv 为当前值
 */
void build(int o,int L,int R)
{
    if(L==R)
    {
        setv[o] = default_setv;
        addv[o] = sumv[o] = maxv[o] = minv[o] = a[L];
    }
    else
    {
        int M = L + (R-L)/2;
        int lc = o<<1,rc = o<<1|1;
        build(lc,L,M);
        build(rc,M+1,R);

        addv[o] = 0;
        setv[o] = default_setv;
        sumv[o] = sumv[lc] + sumv[rc];
        maxv[o] = max(maxv[lc],maxv[rc]);
        minv[o] = min(minv[lc],minv[rc]);
    }
}

/*
 * 测试函数,R 代表叶子节点个数
 */
void test(int R,int n)
{
    cout<<"----------"<<endl;
    auto init = [&]()
    {
        _sum = 0;
        _min = INT_MAX;
        _max = INT_MIN;
    };
    for(int i=1; i<=n; i++)
    {
        init();
        query(1,1,R,i,i,0);
        cout<<i<<" --> "<<_sum<<"\t "<<_min<<"\t "<<_max<<endl;
    }
    init();
    query(1,1,R,1,R,0);
    cout<<"total: "<<_sum<<endl;
    cout<<"----------"<<endl;
}

int main()
{
    IO;
    int n,m;
    while(cin>>n>>m)
    {
        int R = 1;
        while(R<n)R<<=1;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        build(1,1,R);
        while(m--)
        {
            char c;
            int l,r;
            cin>>c>>l>>r;
            if(c=='Q')
            {
                _max = 0;
                query(1,1,R,l,r,0);
                cout<<_max<<endl;
            }
            else
                update_set(1,1,R,l,l,r);
        }
    }
    return 0;
}