题解 P1198 【[JSOI2008]最大数】

· · 题解

这是一个比较麻烦的线段树写法，先读入指令，add[],que[]分别表示A和Q的指令；并且考虑到指令的先后顺序，记录编号，定义cmd结构，用于记录。

为什么不边读边处理呢？

其实这道题是可以边读边处理的，但是这样用线段树的话，就必须把根节点定义为1..,MAXN的范围了，有点。。。

所以考虑到这里，就用这种麻烦一点的算法了。这样能够先得到最后的数的个数。

介绍三个核心函数（直接从我Luogu2068的题解里复制修改的，两题有点像，可以参考）

up(int p)

用于更新p节点的值。因为这是二叉树，p节点的子节点为2p,2p+1.

max_arr[]用于存储tree.

更新操作：max_arr[p]=max(max_arr[2p],max_arr[2p+1]);

update(int p, int l, int r, int x, int v)

用于更新第x个数，使第x个数+v

因为更新第x个数后，存储第x个数值节点的父节点（上司）都会受到影响，于是传递节点p，节点p的值为：max_arr[p]=max(a[l],a[l+1],..,a[r]);

l,r是p的“范围”

若l=r表示已经找到存储a[x]的节点，+v.

然后再二分，更新节点。

query(int p, int l, int r, int x, int y);

p,l,r的定义见2.

这个函数用于获得[x,y]区间的和。

分析可知：如果[l,r]包含于[x,y]，那么可以直接将s[p]的值加入最后的答案中。

（max_arr[p]=max(a[l], ... ,a[r]; max(a[x], ... , a[y])=max(max(a[x], ... ,a[l-1]). max_arr[p], max(a[r+!], ... , a[y])）

所以在这种情况下，可以直接返回。

if (x<=l && y<=r) then return max_arr[p];

如果[l,r]不是[x,y]的子集，那么取m=(l+r) div 2;

分两边讨论。

如果x<=m,则讨论左边；

如果m<y,讨论右边。

注意：

这两种情况是并列的，不存在else的情况。

所以这一段的伪代码就是：

m=(l+r)/2;
int ret=-INF;
if x<=m ret=max(query左边,ret)
if m<y ret=max(query右边,ret)
return ret;

具体实现见下。

所以上面就是主要介绍了。

最后：主程序

读入

addcnt, quecnt是两个数组的指针，储存指令

处理

按照实现储存的数值判断指令先后，调用update,query即可。

//Luogu 1198 _ RMQ-Method Solve
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=200000;
const int INF=10000000;

struct cmd{
    int x, num;
}add[MAXN+1], que[MAXN+1];

int max_arr[4*MAXN+1];
int Q, mod, previous=0;
int n=0, addcnt=0, quecnt=0;

void up(int p)
{
    max_arr[p]=max(max_arr[2*p], max_arr[2*p+1]);
    return;
}

void update(int p, int l, int r, int x, int v)
{
    if (l==r) {
        max_arr[p]=v;
        return;
    }

    int m=(l+r)/2;
    if (x<=m) update(2*p, l, m, x, v);
    else update(2*p+1, m+1, r, x, v);
    up(p);
    return;
}

int query(int p, int l, int r, int x, int y)
{
    if (x<=l && r<=y) {
        return max_arr[p];
    }

    int m=(l+r)/2;
    int ret=-INF;
    if (x<=m) ret=max(ret, query(2*p, l, m, x, y));
    if (m<y) ret=max(ret, query(2*p+1, m+1, r, x, y));
    return ret;
}

int main()
{
    cin >> Q >> mod;
    for (int i=1; i<=Q; i++) {
        char c[3];
        scanf("%s", c);
        if (c[0]=='A') {
            addcnt++;
            scanf("%d", &add[addcnt].x);
            n++;
            add[addcnt].num=i;
        }
        else {
            quecnt++;
            scanf("%d", &que[quecnt].x);
            que[quecnt].num=i;
        }
    }

    fill(max_arr, max_arr+4*n, -INF);
    addcnt=1;
    quecnt=1;
    for (int i=1; i<=Q; i++) {
        if (add[addcnt].num==i) {
            update(1, 1, n, addcnt, (add[addcnt].x+previous)%mod);
            addcnt++;
        }
        else if (que[quecnt].num==i) {
            previous=query(1, 1, n, addcnt-que[quecnt].x, addcnt-1);
            printf("%d\n", previous);
            quecnt++;
        }
    }

    return 0;
}