P1198 [JSOI2008]最大数（单调栈，并查集）

传送门

单调栈的做法显然，主要是这道题为什么可以用并查集来代替二分查找

在将一个数插入单调队列时，我们可以将被删除的数的父亲标记为插入的数，在查找时只需要找到查找的数的根，根上的数值即为答案。

证明？不会证qwq

复杂度$O(n)$

code：

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