[JSOI2008]最大数maxnumber

Link:61.187.179.132:8080/JudgeOnline/showproblem
就是说让你维护一个数据结构。
支持两个操作,A 在末尾插入一个数,
Q L,最后L个数中最大的是哪个?
很明显要用单调队列。。用了单调队列后。。
整个数列被分成几段每段的答案都是一样的。。
那么弄一个并查集维护答案。。然后插入一个数可能导致几段的合并,
就正好是并查集的Union,然后每段的根就是这段的答案。。
那么用并查集就可以搞定了。。
这个算法实际上就是离线RMQ的一种应用,我以前发过这样那个算法,见:传送门
Code:

#include<cstdio>
using namespace std;
const int maxn=200000;
int stack[maxn],top=0;
int F[maxn],A[maxn];
int find(int x){if(F[x]==x) return x; return F[x]=find(F[x]);}
void Union(int x,int y){F[y]=x;}
int main()
{
//freopen("in","r",stdin);
int last=0,m,d,x,n=0;char c;
scanf("%d %dn",&m,&d);
while(m–)
{
scanf("%c %dn",&c,&x);
if(c==’Q’)
x=(n-x),printf("%dn",last=A[find(x)]);
else
{
F[n]=n;A[n]=(last+x)%d;
while(top&&A[stack[top-1]]<=A[n])
Union(n,stack[top-1]),top–;
stack[top++]=n++;
}
}
}

本高亮代码使用codeHl生成,查看详情

6 thoughts on “[JSOI2008]最大数maxnumber

Leave a Reply to 中国脑筋 Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>