BZOJ 1012: [JSOI2008]最大数maxnumber【线段树单点更新求最值，单调队列，多解】

2022-10-27 11:11:45

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 10374 Solved: 4535
[Submit][Status][Discuss]

Description

　　现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：Q L 功能：查询当前数列中末尾L
个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：A n 功能：将n加
上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取
模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个
数。

Input

　　第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来
M行，查询操作或者插入操作。

Output

　　对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

Sample Input

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

Sample Output

96
93
96

HINT

　　数据如下http://pan.baidu.com/s/1i4JxCH3

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1012

分析：线段树，，，，，我可能又是智障了，调了俩个小时，一个update写错一个细节，WA了三发，然后一直Re，mmp，开80W数组都不够？开了个270W的数组才过，这题目有毒！这题其实也很简单，先建一棵树，结点都为空，然后记录下插入的数的个数为cnt，逐个插入，每次询问cnt-l+1到cnt的最大值即可！

下面给出AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=;

 #define inf 0x7fffffff

 inline int read()

 {

     int x=,f=;

     char ch=getchar();

     while(ch<''||ch>'')

     {

         if(ch=='-')

             f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='')

     {

         x=x*+ch-'';

         ch=getchar();

     }

     return x*f;

 }

 inline void write(int x)

 {

     if(x<)

     {

         putchar('-');

         x=-x;

     }

     if(x>)

         write(x/);

     putchar(x%+'');

 }

 struct Tree

 {

     int L,R,maxn;

 }tree[N<<];

 inline void buildtree(int l,int r,int pos)

 {

     tree[pos].L=l;

     tree[pos].R=r;

     tree[pos].maxn=-inf;

     if(l==r)

         return;

     int mid=(l+r)/;

     buildtree(l,mid,pos*);

     buildtree(mid+,r,pos*+);

 }

 inline int Query(int l,int r,int pos)

 {

     if(tree[pos].L==l&&tree[pos].R==r)

         return tree[pos].maxn;

     int mid=(tree[pos].L+tree[pos].R)/;

     if(r<=mid)

         return Query(l,r,pos*);

     else if(l>mid)

         return Query(l,r,pos*+);

     else return max(Query(l,mid,pos*),Query(mid+,r,pos*+));

 }

 inline void update(int l,int r,int pos)

 {

     if(tree[pos].L==tree[pos].R)

     {

         tree[pos].maxn=r;

         return;

     }

     int mid=(tree[pos].L+tree[pos].R)/;

     if(l<=mid)

         update(l,r,pos*);

     else update(l,r,pos*+);

     tree[pos].maxn=max(tree[pos*].maxn,tree[pos*+].maxn);

 }

 int m,mod,last,cnt;

 int main()

 {

     m=read();

     mod=read();

     buildtree(,m,);

     for(int i=;i<=m;i++)

     {

         char ch[];

         scanf("%s",ch);

         int x;

         if(ch[]=='A')

         {

             cnt++;

             x=read();

             x=(x+last)%mod;

             update(cnt,x,);

         }

         else

         {

             x=read();

             last=Query(cnt-x+,cnt,);

             printf("%d\n",last);

         }

     }

     return ;

 }

似乎可以用单调队列写？

贴个AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int m,d,a[maxn<<],t,maxx[maxn<<],l,p;

 char q[];

 int main()

 {

     scanf("%d%d",&m,&d);

     while(m--)

     {

         scanf("%s%d",q,&p);

         if(q[]=='A')

         {

             a[++t]=(l+p)%d;

             for(int i=t;i;i--)

             {

                 if(maxx[i]<a[t])

                     maxx[i]=a[t];

                 else break;

             }

         }

         else printf("%d\n",l=maxx[t-p+]);

     }

     return ;

 }

码农公寓