P1198 [JSOI2008]最大数

题目描述

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

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行，每行一个字符串，描述一个具体的操作。语法如上文所述。

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

输入输出样例

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

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],既然所有值都是一样的，自然就是对其进行操作，然后再考虑被所要查询的区间所完全包围。回到之前的问题上来，为什么我们要清除父节点的标记呢？我们将标记下传一般都是传到被所要查询的区间所完全包围的区间，因为子节点的区间内的值就包含了大区间的值，换句话说，所求的结果就是几个小区间的并，而这几个小区间则是分解到不能再分解为止，自然，我们将父节点的标记消除因为子节点才是影响到结果的根本，我们求的值最终也在子节点进行，所以要消除.