题解 P1198 【[JSOI2008]最大数】

Mr_Wu · 2018-03-13 18:05:00 · 题解

这是一篇蒟蒻写的线段树题解

线段树做的太艰难了QAQ

其实因为我太菜了其他算法都不会

蒟蒻艰难的AC路程

这题要注意的点很多，因为数据的加强，很多线段树的代码都挂了

• 线段树中的二分操作要位运算可能只有我这个蒟蒻没有这个习惯吧

• 最后一个点卡快读(fread好像没事)，要用cin+取消与scanf同步优化(ios::sync_with_stdio(false);)

• 变量类型int就行了，我也不知道为什么不要问我

首先来研究一下这道题。

开一个变量len表示数列大小，一开始为0

添加的时候len++,然后在len位置单点修改(n+t)%d

查询的时候区间查询len-l+1到len最大值

• Q : 线段树是什么？

• A : ...我没办法了，上网查吧

然后就是蒟蒻写的代码了qaq

Code :

//[JSOI2008]最大数
//2364ms / 4085KB
#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 200005;
int m,MOD,len;
int tree[MAXN * 8];
#define mymax(x,y) (x > y ? x : y)

char mygetchar()
{
    char ch;
    while (true)
    {
        ch = getchar();
        if (ch != ' ' && ch != '\r' && ch != '\n') return ch;
    }
}

int readint()
{
    int ret = mygetchar() - '0';
    char ch;
    while (true)
    {
        ch = getchar();
        if (ch != ' ' && ch != '\r' && ch != '\n') ret = ret * 10 + ch - '0';
        else return ret;
    }
}

void insert(int o,int l,int r,int pos,int k)
{
    if (l >= r) tree[o] = k;
    else
    {
        int mid = (l + r) >> 1;
        if (pos <= mid) insert(o << 1, l, mid, pos, k);
        else insert(o << 1 | 1, mid + 1, r, pos, k);
        tree[o] = mymax(tree[o << 1], tree[o << 1 | 1]);
    }
}

int getmax(int o,int l,int r,int L,int R)
{
    if (l == L && r == R) return tree[o];
    else
    {
        int mid = (l + r) >> 1;
        if (R <= mid) return getmax(o << 1, l, mid, L, R);
        else if (L >= mid + 1) return getmax(o << 1 | 1, mid + 1, r, L, R);
        else return mymax( getmax(o << 1, l, mid, L, mid), getmax(o << 1 | 1, mid + 1, r, mid + 1, R));
    }
}

int main()
{
    ios::sync_with_stdio(false);
    char p1;
    int p2,i;
    int t = 0;
    cin >> m >> MOD;
    for (i = 1;i <= MAXN;i++) tree[i] = -99999999;
    while (m--)
    {
        cin >> p1 >> p2;
        if (p1 == 'A')
        {
            insert(1, 1, MAXN, ++len, (p2 + t) % MOD);
        }
        else
        {
            if (!p2) printf("0\n");
            else 
            {
                t = getmax(1, 1, MAXN, len - p2 + 1, len);
                printf("%d\n",t);
            }
        }
    }
    return 0;
}

QWQ