P1198 [JSOI2008]最大数

题目描述

现在请求你维护一个数列，要求提供以下两种操作：

1、查询操作。

语法：Q L

功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。

限制：LL不超过当前数列的长度。(L > 0)(L>0)

2、插入操作。

语法：A n

功能：将nn加上tt，其中tt是最近一次查询操作的答案（如果还未执行过查询操作，则t=0t=0)，并将所得结果对一个固定的常数DD取模，将所得答案插入到数列的末尾。

限制：nn是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

输入格式

第一行两个整数，MM和DD，其中MM表示操作的个数(M \le 200,000)(M≤200,000)，DD如上文中所述，满足(0<D<2,000,000,000)(0<D<2,000,000,000)

接下来的MM行，每行一个字符串，描述一个具体的操作。语法如上文所述。

输出格式

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

[JSOI2008]

本题数据已加强

题解：为线段树基础……适合刚学线段树的人写一下开拓一下思路。根据题目我们可以将线段的sum改为该线段中的最大值，这样会简单快速许多，具体见下代码；

#define _CRT_SECURE_NO_DepRECATE

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>

#include <iostream>

#include <cmath>

#include <iomanip>

#include <string>

#include <algorithm>

#include <bitset>

#include <cstdlib>

#include <cctype>

#include <iterator>

#include <vector>

#include <cstring>

#include <cassert>

#include <map>

#include <queue>

#include <set>

#include <stack>

#define ll long long

#define INF 0x3f3f3f3f

#define ld long double

const ld pi = acos(-.0L), eps = 1e-;

int qx[] = { ,,,- }, qy[] = { ,-,, }, qxx[] = { ,- }, qyy[] = { ,- };

using namespace std;

struct node

{

    ll l = , r = , sum = , plz = , mlz = ;

}tree[];

ll  p = INF, maxx;

inline void build(int i, int l, int r, int insert,int num)//树的编号 最左端 最右端 插入的值 插入的下标

{

    tree[i].l = l;

    tree[i].r = r;

    if (l == r)//找到该点即替换为insert

    {

        tree[i].sum = insert;

    }

    else

    {

        if ((l + r) /  >= num)

        {

            build(i << , l, (l + r) / , insert, num);

        }

        else

        {

            build(i <<  | , (l + r) /  + , r, insert, num);

        }

        tree[i].sum = max(tree[i << ].sum, tree[i <<  | ].sum);//每个线段的sum为该线段的最大值

    }

}

inline ll search_max(int i, int l, int r)

{

    if (tree[i].l >= l && tree[i].r <= r)//因sum即代表该线段的最大值，所以找到完全包含的线段就可以直接返回sum

    {

        return tree[i].sum;

    }

    if (tree[i].l > r || tree[i].r < l)

    {

        return ;

    }

    ll ans = -INF;

    if (l <= tree[i << ].r)

    {

        ans = max(ans, search_max(i << , l, r));

    }

    if (r >= tree[i <<  | ].l)

    {

        ans = max(ans, search_max(i <<  | , l, r));

    }

    return ans;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    ll m, d, t = , sum = , b,input;

    char x;

    cin >> m >> d;

    for (int i = ; i < m; i++)

    {

        cin >> x;

        if (x == 'A')

        {

            cin >> input;

            input = (input + t) % d;

            build(, , m, input, sum);//因为最多只能插入m个，所以可以直接以m为r

            sum++;

        }

        else

        {

            cin >> b;

            t = search_max(, sum - b, sum - );

            cout << t << endl;

        }

    }

    return ;

}

秒客网

P1198 [JSOI2008]最大数（线段树基础）