洛谷P1198 [JSOI2008]最大数（线段树/单调栈）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：

https://www.luogu.org/problemnew/show/P1198

题目描述

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

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：复制

单调栈解法。因为题目求的是末尾L个数的最大值，利用两个栈分别存储最大值和最大值的位置。然后二分查找。注意二分查找时上界是总得个数减去区间长度，而不是栈的空间减去区间长度，因为不符合栈的数值已经出栈了。

单调栈解法参考自：https://www.luogu.org/blog/user38348/solution-p1198

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

long long Stack[2][200010];

long long cnt=0,top=0;

void add(long long val){

    cnt++;

    while(Stack[0][top]<val&&(top>0)) top--;

    Stack[0][++top]=val;

    Stack[1][top]=cnt;

}

long long quiry(long long L){

    int l=1,r=top;

    int ind=cnt-L+1;

//    int ind=top-L+1;

    while(l<r){

        int mid=(l+r)>>1;

        if(Stack[1][mid]<ind) l=mid+1;

        else r=mid;

    }

    return Stack[0][l];

}

int main(int argc, char** argv) {

    int M;long long D;

    scanf("%d %lld",&M,&D);

    long long t=0;

    while(M--){

        char c;

        long long d;

        cin>>c>>d;

        if(c=='A'){

            add((t+d)%D);

        }

        else if(c=='Q'){

            t=quiry(d);

            printf("%lld\n",t);

        }

    }

    return 0;

}

线段树解法，维护区间的最大值。

#include <iostream>

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=200010*4;

ll Max[maxn];

void add(int p,int l,int r,int x,ll c){

    if(l==r){

        Max[p]=c;return;

    }

    int mid=(l+r)>>1;

    if(x<=mid) add(p<<1,l,mid,x,c);

    else add(p<<1|1,mid+1,r,x,c);

    Max[p]=max(Max[p<<1],Max[p<<1|1]);

}

int quiry(int p,int l,int r,int a,int b){

    if(a>r||b<l) return -1e8;

    if(a<=l&&r<=b){

        return Max[p];

    }

    int mid=(l+r)>>1;

    return max(quiry(p<<1,l,mid,a,b),quiry(p<<1|1,mid+1,r,a,b));

}

int main(int argc, char** argv) {

    int M,D;

    scanf("%d %d",&M,&D);

    fill(Max,Max+maxn,-1e8);

    ll t=0;

    int x=0;

    while(M--){

        char c;int d;

        cin>>c>>d;

        if(c=='A'){

            x++;

            ll num=(t+d)%D;

            add(1,1,200010,x,num);

        }else if(c=='Q'){

            t=quiry(1,1,200010,x-d+1,x);

            printf("%lld\n",t);

        }

    }

    return 0;

}