luoguP1198 [JSOI2008]最大数

\(\Theta(nlog_2n)\)算法一眼线段树,在此不再赘述.

那么如何写\(\Theta(n\alpha(n))?\)算法呢?

我们可以搞一个单调栈.

每次加入一个数,就讲栈中val值比他大的数删去,并将它对应的位置上的数的父亲指向当前位置,用并查集维护一下即可.

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define il inline
#define rg register
#define gi read<int>
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int O = 2e5 + 10, inf = (1 << 31) - 1;
template<class TT>
il TT read() {
    TT o = 0,fl = 1; char ch = getchar();
    while (!isdigit(ch) && ch != '-') ch = getchar();
    if (ch == '-') fl = -1, ch = getchar();
    while (isdigit(ch)) o = o * 10 + ch - '0', ch = getchar();
    return fl * o;
}
char ch[2];
ll x;
int t, m, n, mod, fa[O], a[O];
stack<pii >s;
il int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main() {
    m = gi(), mod = gi();
    while (m--) {
        scanf("%s %lld", ch, &x);
        if (ch[0] == 'A') {
            (x += t) %= mod;
            fa[++n] = n;
            a[n] = x;
            while (!s.empty() && x > s.top().first) fa[s.top().second] = n, s.pop();
            s.push(pii(x, n));
        }
        else printf("%d\n", t = (x ? a[find(n - x + 1)] : 0));
    }
    return 0;
}

luoguP1198 [JSOI2008]最大数

原文：https://www.cnblogs.com/lylyl/p/11688681.html