并查集的神奇用法：[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<D<2,000,000,000)(0<D<2,000,000,000)

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

输格外式

对付每一个盘问操纵，你应该凭据挨次依次输出功效，每个功效占一行。

Solution

首先我们来不雅察看这道题的性质：所有的盘问都是从最后开始的

这意味着甚么?

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

但会不停在末端插手数怎么办？并查集上场了

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

这样，就可以在logn的时间内措置惩罚惩罚问题

上代码

Code 

#include <cstdio> #include <cstdlib> 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<=m;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]最大数（并查集）