最大数maxnumber （HYSBZ 1012）（线段树区间查询和单点修改）（优雅的暴力）

Problem 现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：Q L 功能：查询当前数列中末尾L

个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：A n 功能：将n加

上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取

模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个

数。

Input　第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来

M行，查询操作或者插入操作。

Output 对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

Sample Input Sample Output

5 100 A 96 Q 1 A 97 Q 1 Q 2 96 93 96

题解：简单的线段树模板题，建一颗空树逐个更新最大值就可以了，或者直接储存一个后缀里面最大数，每次更新，加上break，复杂度在不卡数据的时候还可以。

1、线段树

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200000;

struct node

{

    int l, r;

    int w;

};

struct node tree[MAX *4 + 10];

int a[MAX] = {0};

int ans = 0;

void BuildTree(int l, int r, int k)

{

    tree[k].l = l;

    tree[k].r = r;

    if(l == r)

    {

        tree[k].w = a[l];

        return ;

    }

    int m = (tree[k].l + tree[k].r) >> 1;

    BuildTree(l, m,k << 1);

    BuildTree(m + 1, r, k << 1 | 1);

    tree[k].w = max(tree[k << 1].w, tree[k << 1 | 1].w);

}

void SingleModify(int k, int x, int y)

{

    if(tree[k].l == x &&  tree[k].r == x)

    {

        tree[k].w = y;

        return ;

    }

    int m = (tree[k].l + tree[k].r) / 2;

    if(x <= m) SingleModify(k<<1,x,y);

    else SingleModify(k<<1|1,x,y);

    tree[k].w = max(tree[k<<1].w, tree[k<<1|1].w);

}

void IntervalQuery(int k, int x, int y)

{

    if(tree[k].l >= x && tree[k].r <= y)

    {

        ans = max(ans,tree[k].w);

        return ;

    }

    int m = (tree[k].l + tree[k].r) >>1;

    if(x <= m) IntervalQuery(k<<1,x,y);

    if(y > m) IntervalQuery(k <<1 |1,x, y);

}

char op;

int main()

{

    int M, D, t, L, n, x, top;

    while(~scanf("%d %d",&M, &D))

    {

        BuildTree(1,MAX,1);

        t = 0;

        top = 0;

        while(M --)

        {

            getchar();

            scanf("%c %d",&op, &x);

            if(op == 'A')

            {

                n = x;

                n = (n + t) % D;

                SingleModify(1,top + 1,n);

                top ++;

            }

            else

            {

                L = x;

                ans = 0;

                IntervalQuery(1,top - L + 1, top);

                t = ans;

                printf("%d\n",ans);

            }

        }

    }

    return 0;

}

2、优雅的暴力（复杂度在最坏情况下会TLE，不过不卡数据还可以）

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

ll a[N];    // 储存所有数据

ll b[N];    // 存储后缀的最大值，b[i]表示后i个数的最大值

int main()

{

    ll m,mod,n,x,y,i,j,k,f;  // x是查询后保留值

    char op;

    while(~scanf("%lld %lld", &m, &mod))

    {

        i = 1;  j = 1;  k = 0;

        memset(a,0,sizeof(a));

        memset(b,0,sizeof(b));

        x = 0; f = 0;

        for(ll p = 1; p <= m; p ++)

        {

            getchar();

            scanf("%c %lld", &op, &n);

            if(op == 'A')

            {

                if(f == 0)   // 一直是添加的情况，当前没有查询，一旦查询之后就需要Mod

                {

                    y = n % mod;

                    a[i ++] = y;

                    b[j ++] = y;

                    if(a[i - 1] <= a[i - 2]); //如果新添加的这个数比倒数第二个小，不需要更新

                    else

                    {

                        for(k = i - 2; k >= 0; k --)  // 从后面开始更新

                        {

                            if(y > b[k])b[k] = y;

                            else break;

                        }

                    }

                }

                else

                {

                    y = (n + x) % mod;

                    a[i ++] = y;

                    b[j ++] = y;

                    if(a[i - 1] <= a[i - 2]);

                    else

                    {

                        for(k = i - 2; k >= 0; k --)

                        {

                            if(y > b[k])b[k] = y;

                            else break;

                        }

                    }

                }

            }

            else if(op == 'Q')   // 访问情况， 保留x

            {

                f = 1;

                x = b[j - n];

                printf("%lld\n",x);

            }

        }

    }

    return 0;

}

巴特西

最大数maxnumber （HYSBZ 1012）（线段树区间查询和单点修改）（优雅的暴力）

最新文章

热门文章