HDU-1754 I Hate It （树状数组模板题——单点更新，区间查询最大值）

ac代码(注意字符读入前需要注意回车的影响)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<bitset>

#include<cassert>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<deque>

#include<iomanip>

#include<list>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define mp make_pair

#define pi acos(-1)

#define pii pair<int, int>

#define pll pair<long long , long long>

#define ll long long

#define ld long double

#define MEMS(x) memset(x, -1, sizeof(x))

#define MEM(x) memset(x, 0, sizeof(x))

const int inf = 0x3f3f3f3f;

const int maxn = 200005;

using namespace std;

int N, M;

int s, c[maxn], d[maxn];

char order;

int lowbit(int x)

{

    return x & (-x);

}

void update(int x)

{

    while(x <= N)

    {

        d[x] = c[x];

        int lx = lowbit(x);

        for(int i = 1; i < lx; i <<= 1)

            d[x] = max(d[x], d[x - i]);

        x += lowbit(x);

    }

}

int getmax(int l, int r)

{

    int ans = 0;

    while(r >= l)

    {

        ans = max(ans, c[r]);

        --r;

        while(r - lowbit(r) >= l)

        {

            ans = max(ans, d[r]);

            r -= lowbit(r);

        }

    }

    return ans;

}

int main()

{

//    freopen("input.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

    while(scanf("%d %d", &N, &M) != EOF)

    {

        memset(d, 0, sizeof(d));

        for(int i = 1; i <= N; i++)

        {

            scanf("%d", &c[i]);

            update(i);

        }

        int a, b;

        while(M--)

        {

            getchar();

            scanf("%c %d %d", &order, &a, &b);

            if(order == 'U')

            {

                c[a] = b;

                update(a);

            }

            else if(order == 'Q')

                printf("%d\n", getmax(a, b));

        }

    }

}

巴特西

HDU-1754 I Hate It （树状数组模板题——单点更新，区间查询最大值）

最新文章

热门文章