[JSOI2008]最大数（并查集）

2021-04-25 12:27

阅读：476

标签：strong col get while script names lib ble log

并查集的神奇用法：[JSOI2008]最大数

Description

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

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(0D2,000,000,000)

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

输出格式

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

Solution

首先我们来观察这道题的性质：所有的查询都是从最后开始的

这意味着甚么?

我们只用对每个数维护它到最后一个数之间的数的最大值就可以了

但会不断在末端加入数怎么办？并查集上场了

每加入一个数时，像单调栈一样把从它到它前面第一个比它大的数之前的一个数之间的所有数的最深父亲设为它；

这样，就可以在logn的时间内处理问题

上代码

Code

#include 
#include using namespace std;
const int N=200010;
struct node
{
    long long x;
    int y;
}a[N];
int m,tot,cnt,f[N];
long long d,t,x,num[N];
char ch[3];
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{
    scanf("%lld%lld",&m,&d);
    for(int i=1;i)
    {
        scanf("%s",ch);
        scanf("%lld",&x);
        if(ch[0]==‘A‘)
        {
            x+=t,x%=d;
            num[++tot]=x,f[tot]=tot;
            while(x>a[cnt].x&&cnt)
                f[a[cnt--].y]=tot;
            a[++cnt].x=x,a[cnt].y=tot;
        }
        else
        {
            x=tot-x+1,t=num[find(x)];
            printf("%lld\n",t);
        }
    }
    return 0;
}

[JSOI2008]最大数（并查集）

标签：strong col get while script names lib ble log

原文地址：https://www.cnblogs.com/hsez-cyx/p/12229398.html

上一篇：MVC HTML辅助方法

下一篇：k8s官方案例练习-使用 Redis 部署 PHP 留言板应用程序

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[JSOI2008]最大数（并查集）
文章链接：http://soscw.com/index.php/essay/79387.html

亲，登录后才可以留言！

[JSOI2008]最大数（并查集）

评论

热门文章

推荐文章

最新文章

置顶文章