首页 > 代码库 > 洛谷P1198 [JSOI2008]最大数

洛谷P1198 [JSOI2008]最大数

P1198 [JSOI2008]最大数

    • 267通过
    • 1.2K提交
  • 题目提供者该用户不存在
  • 标签线段树各省省选
  • 难度提高+/省选-

提交该题 讨论 题解 记录

最新讨论

  • WA80的戳这QwQ
  • BZOJ都过了,洛谷竟然过不了…
  • 为什么过不了
  • = =我想说这题加优读会WA?…
  • 谁说pascal只能80,要换c++…
  • 线段树为什么是80?

题目描述

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

1、 查询操作。

语法:Q L

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

限制:L不超过当前数列的长度。

2、 插入操作。

语法:A n

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

限制:n是整数(可能为负数)并且在长整范围内。

注意:初始时数列是空的,没有一个数。

输入输出格式

输入格式:

 

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

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
5 100A 96Q 1A 97Q 1Q 2
输出样例#1:
969396

说明

[JSOI2008]

分析:这道题有很多种办法解决,首先可以发现数列中的数是递增的,每次添加进去的数都比之前的大,那么根据这个原理,模拟一下就能做出来.

这道题可以用来练线段树,为什么想到要用线段树呢?注意区间二字!在区间中查找最大值并且完成单点修改(插入),这不就是线段树的最基本的操作吗?因为线段树可以全部赋值为-inf,所以插入操作可以理解为单点修改,套用线段树的模板即可解决.

变量开成了全局变量,查了一个晚上的错......

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define le l,mid,o * 2#define re mid + 1,r,o * 2 + 1using namespace std;const int maxn = 200001;int m, d,maxo[maxn << 2],len,t;void build(int l,int r,int o){    if (l == r)    {        maxo[o] = -2147283647;        return;    }    int mid = (l + r) >> 1;    build(le);    build(re);}void charu(int l, int r, int o, int i, int j){    if (l == r) {         maxo[o] = j;        return;     }    int mid = (l + r) >> 1;    if (i <= mid)charu(le, i, j);    else charu(re, i, j);    maxo[o] = max(maxo[o * 2], maxo[o * 2 + 1]);}int query(int l, int r, int o, int x, int y){    if (x <= l && r <= y)        return maxo[o];    int mid = (l + r) >> 1;    int temp = -2147483647;    if (x <= mid)        temp = max(temp,query(le, x, y));    if (y > mid)        temp = max(temp, query(re, x, y));    return temp;}int main(){    scanf("%d%d", &m, &d);    build(1, maxn, 1);    for (int b = 1;b <= m;++b)    {        char c;int i;        cin >> c;scanf("%d", &i);        if (c == A) { len++;charu(1, maxn, 1, len, (i + t) % d); }        else { t = query(1, maxn, 1, len - i + 1, len);printf("%d\n", t); }    }    return 0;}

 

如果你还不会线段树,那么可以参考一下下面这段文字(之前写的可能不是很好,望体谅,可能也有一些不正确的,只能当作参考):

线段树,这个万能的树。

线段,线段,说白了就是一个区间,线段树主要的操作就是对区间进行修改查询,效率非常高,线段树的用途非常广,单点更新、区间更新、最值询问、区间询问,至于它具体能干哪些事取决于树里所储存的信息量。

 

这是一个线段树的图,这个图只是能够帮我们理解线段树的大体形状,并不能告诉我们更多信息,其实线段树的更多功能都隐藏在每一个节点的信息背后,为了能够更方便的做题,我们给线段树的每一个节点标上序号。我们从上到下,从左到右依次标号,如果根节点的序号为k,那么它的左子树节点的序号则为2k,右子树节点的序号则为2k + 1,每一个序号都对应着唯一一个节点,所以我们可以用一个数组tree来表示这个节点背后所隐藏的信息。这个数组究竟开多大呢?虽然在平常做题中我们不需要考虑的这么仔细,但在一些内存限制非常紧的题目中这些都是要注意的。如果区间范围是[0,N-1],那么tree的大小M=2*N + 1,这个很好验证。

我们先来考虑如何建树,一般来说,只要到了叶子节点直接输入就好了,但是我们怎么样才能够很快的到达叶子节点呢?递归!

int tree[2 * MAX_N + 1];

 

/*建立以k为根节点[L,H]为操作区间的线段树*/

void built_tree(int k, int L, int H)

{

    if (L == H){

        scanf("%d", &tree[k]);

        return;

    }

    built_tree(k << 1, L, (L + H) << 1);

    built_tree(k << 1 | 1, (L + H) << 1 | 1, H);

}

如果L==H,证明当前区间的长度为1,也就是此节点为叶节点,可以直接赋值。

再来考虑一个经典问题:求一个区间内的最小元素值。

这道题可以用暴力来做,不过复杂度太高,在一些题目中可能会TLE,我们可以看到区间二字,那么这道题80%要用线段树来做(当然也不是绝对,只是效率高),我们不断比较当前查询区间和目标区间,如果当前查询区间在目标区间内,那么当前深度所表示的节点便可以参与最小值计算,如果不在区间内,则返回无穷大,否则则分别对当前树的左右子树进行相同运算(可能术语话太强了).

int read_tree(int k, int L, int H, int beg, int end)

{

    if (beg > H || end < L) return -INT_MAX;

    if (beg <= L && end >= H) return tree[k];

    return min(read_tree(2 * k, L, (L + H) / 2, beg, end),

        read_tree(2 * k + 1, (L + H) / 2 + 1, H, beg, end));

}

有查询,就一定伴随着修改的存在,如果是普通的数组,修改很容易,只需要对所需要操作的下标所对应的数据修改即可,但是这是高效率数据结构,修改就意味着要对许多量进行改变,在线段树中,我们对一个节点进行修改只需要对其及其所有的祖先进行修改即可,其他量不变。

/*在根节点为k,[L,H]为操作区间的线段树里对id处的值更新为key*/

int update_tree(int k, int L, int H, int id, int key)

{

    if (L == H){

        tree[k] = key;

        return;

    }

    if (id < (L + H) / 2)

        update(k * 2, L, (L + H) / 2, id, key);

    else

        update(K * 2 + 1, (L + H) / 2 + 1, H, id, key);

    tree[k] = MAX(tree[k * 2], tree[2 * k + 1]);

}

这样便完成了修改操作.

然后是比较复杂的区间修改,设计一个数据结构,使它支持两种操作

  1. Add(L,R,v)将AL,AL+1…AR的值全部+V
  2. Query(L,R)计算子序列AL,AL+1…AR的元素和,最小值,最大值。

这里要维护三个查询值,该怎么维护呢?

首先这里的Add操作是区间修改,并不是单点修改,最糟糕的情况下可能整棵线段树的结点值都要被修改。我们知道线段树任意区间都能分解成不超过2h个不相交区间的并,利用这个结论我们可以将每一个Add操作分解成不超过2h个的Add操作,记录在线段树的结点中。每次执行完Add操作都要重新计算每个结点的附加信息,递归访问到的结点全部都要重新计算,并且是在递归返回后计算!

下面给出计算的代码:

void weihu(int o,int L,int R)

{

    int lc = o * 2, rc = o * 2 + 1;

    sumv[o] = minv[o] = maxv[o] = 0;

    if (R > L) {

        sumv[o] = sumv[lc] + sumv[rc];

        minv[o] = min(minv[lc], minv[rc]);

        maxv[o] = max(maxv[lc], maxv[rc]);

    }

    minv[o] += addv[o];

    maxv[o] += addv[o];

    sumv[o] += addv[o] * (R - L + 1);

}

对于下面的代码来说,修改/查询的范围均为[y1,y2].

这里的sumv数组要说一下,为什么要用左右子结点相加得出呢?首先父亲结点就包含了左右结点,其次这样维护的时候就不需要修改全部的sumv数组的元素了。当然这里指的是特殊情况,一般是那种极端数据的。

下面是Add操作的代码:

void Add(int o, int L, int R)

{

    int lc = o * 2, rc = o * 2 + 1;

    if (y1 <= L && y2 >= R)

        addv[o] += v;

    else {

        int M = (L + R) >> 1;

        if (y1 <= M)

            Add(lc, L, M);

        if (y2 > M)

            Add(rc, M + 1, R);

    }

    weihu(o, L, R);

}

其中addv数组是累加边界的add值,因为一棵线段树的子节点可能不知被修改一次,所以有必要设立这个数组。

然后是查询操作,话说用线段树步步都得谨慎,感觉这句话没错啊,每次进行操作都要考虑到结点对结点之间有没有影响,我们查询一般都是从上往下递归查询,既然一个结点的父结点执行了add操作,而这个节点也被父节点包括在内,所以这个节点的值肯定被改变了,于是我们只能设3个全局变量来维护。

int _min, _max, _sum;

void query(int o, int L, int R, int add)

{

    if (y1 <= L && y2 >= R) {

        _sum += sumv[o] + add * (R - L + 1); \

            _min = min(_min, minv[o] + add);

        _max = max(_max, maxv[o] + add);

    }

    else {

        int M = (L + R) >> 1;

        if (y1 <= M)

            query(o * 2, L, M, add + addv[o]);

        if (y2 > M)

            query(o * 2 + 1, M + 1, R, add + addv[o]);

    }

}

看到很多人都弄混了,好吧,其实我也有点晕了。可能会有人问了,为什么我们的weihu函数已经维护了现在还要维护呢?因为weihu函数是从下到上的,也就是从左右子节点维护的,是相对于子节点所发生的变化,而这里的全局变量是因为父节点进行了Add操作,子节点包含在内,所以要另开变量维护。如果还是搞不明白,可以看到weihu函数最后只是修改了当前节点的值,并没有维护到它的子节点,所以要另开变量维护。

接下来是更加复杂的:

Set(L,R,v)把AL,AL+1...AR的值全部修改为v.

Query(L,R)计算子序列AL,AL+1...AR的三个值(同上题).

可以看到这里变动的是Set操作,我们说这道题比之前复杂,为什么呢?因为之前的Add操作不管操作次序如何,都可以达到最后的结果,前提是算法是对的,代码没写错。然而Set操作则不同,好比刷油漆,最后刷的就是最终颜色。怎么办呢?打标记!这里的打标记则相当于对于被改变的特殊情况而做的变动,是为了最后的求出三个值而打的,那么怎么做呢?如果当前区间完全被包含在我们需要修改/查询的区间内,则直接修改标记为v,否则则标记下传。

void pushdown(int o)

{

    int lc = o * 2, rc = o * 2 + 1;

    if (setv[o] >= 0)

    {

        setv[lc] = setv[rc] = setv[o];

        setv[o] = -1;

    }

}

这里的setv数组即为标记,注意到这个数组被初始化为-1,这里不要搞错了,那么问题来了:为什么我们要清除父节点的标记呢?

接下来,Set操作代码:

void Set(int o, int L, int R)

{

    int lc = o * 2, rc = o * 2 + 1;

    if (y1 <= L && y2 >= R)

    {

        setv[o] = v;

    }

    else {

        pushdown(o);

        int M = (L + R) >> 1;

        if (y1 <= M)

            Set(lc, L, M);

        else

            maintain(lc, L, M);

        if (y2 > M)

            Set(rc, M + 1, R);

        else

            maintain(rc, M + 1, R);

    }

    maintain(o, L, R);

}

注意到3次maintain,最后一次很好理解,因为我们之前讲过,每一次递归完后都必须要维护一次,那么前两次又是为何呢?因为标记一旦下传,则该子树的附加信息需要改变,当前区间内的子树在递归完后自然会进行维护,不过另一个区间内的子树则没有被维护,因此需要加上两次maintain函数的调用。

接下来是query操作的代码:

void query(int o, int L, int R)

{

    if (setv[o] >= 0) {

        _sum += setv[o] * (min(R, y2) - max(L, y1) + 1);

        _min = min(_min, setv[o]);

        _max = max(_max, setv[o]);

    }

    else if (y1 <= L && y2 >= R)

    {

        _sum += sumv[o];

        _min = min(_min, minv[o]);

        _max = max(_max, maxv[o]);

    }

    else {

        int M = (L + R) >> 1;

        if (y1 <= M)

            query(o * 2, L, M);

        if (y2 > M)

            query(o * 2 + 1, M + 1, R);

    }

}

对于有标记的区间,我们要优先处理,首先知道当前区间都被修改为setv[o],既然所有值都是一样的,自然就是对其进行操作,然后再考虑被所要查询的区间所完全包围。回到之前的问题上来,为什么我们要清除父节点的标记呢?我们将标记下传一般都是传到被所要查询的区间所完全包围的区间,因为子节点的区间内的值就包含了大区间的值,换句话说,所求的结果就是几个小区间的并,而这几个小区间则是分解到不能再分解为止,自然,我们将父节点的标记消除因为子节点才是影响到结果的根本,我们求的值最终也在子节点进行,所以要消除.

 

                                                        

洛谷P1198 [JSOI2008]最大数