P2174 小Z的神奇数列 堆 逆元

Genius_Z · 2019-04-24 14:27:46 · 题解

这里讲一下堆的在线做法。

维护四个堆，两个大根堆两个小根堆，分别记为q,delq（大根堆），p,delp（小根堆）。

每次删除操作就把要删除的那个数丢进delq和delp里，当q与delq的堆顶相同时，就一直pop，直到堆顶不同，小根堆同理。

这样前三个操作就没了

第4个操作就是一个快速幂。

主要是操作5。

由于毒瘤出题人给的模数不是质数，求逆元必须用exgcd，所以维护一个变量mulit记录当前的模意义下的乘积，每次删除乘以逆元，遇到操作5直接输出，这题就没了。

Code：

#include <algorithm>
#include <tuple>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define inl inline
#define re register int
#define fa(x) t[x].fa
#define ls(x) t[x].child[0]
#define rs(x) t[x].child[1]
#define ll long long
const int inf = 0x3f3f3f3f;
#define lowbit(x) ((x) & (-x))
using namespace std;
template <class Read>
inl Read read() {
    Read x = 0;
    register bool w = 0;
    register char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-') w = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return w ? -x : x;
}
inl int spread() {
    register char c = getchar();
    while (c != 'D'&&c != 'B'&&c != 'S'&&c != 'M'&&c != 'T') {
        c = getchar();
    }
    if (c == 'D')return 0;
    else if (c == 'B')return 1;
    else if (c == 'S')return 2;
    else if (c == 'M')return 3;
    else return 4;
}
const int mod = 317847191;
inl int qpow(int x, int y) {
    long long ans = 1, base = x;
    while (y) {
        if (y & 1)ans = ans * base % mod;
        base = base * base % mod;
        y >>= 1;
    }
    return ans;
}
inl int exgcd(int a, int b, int &x, int &y) {
    if (!b) { x = 1, y = 0; return a; }
    re d = exgcd(b, a%b, x, y), z;
    z = x, x = y, y = z - (a / b)*y;
    return d;
}
priority_queue<int>q, delq;
priority_queue<int, vector<int>, greater<int>>p, delp;
signed main() {
    re n = read<int>(), m = read<int>();
    long long mulit = 1;
    for (re i = 1; i <= n; i++) {
        re x = read<int>();
        mulit = mulit * x % mod;
        q.push(x), p.push(x);
    }
    while (m--) {
        re op = spread();
        if (!op) {
            re x = read<int>(), b, inv, d;
            delq.push(x), delp.push(x);
            exgcd(x, mod, inv, d);
            mulit = mulit * ((inv+mod)%mod) % mod;
        }
        else if (op == 1) {
            while (!delq.empty() && delq.top() == q.top())delq.pop(), q.pop();
            printf("%d\n", q.top());
        }
        else if (op == 2) {
            while (!delp.empty() && delp.top() == p.top())delp.pop(), p.pop();
            printf("%d\n", p.top());
        }
        else if (op == 3) {
            while (!delq.empty() && delq.top() == q.top())delq.pop(), q.pop();
            while (!delp.empty() && delp.top() == p.top())delp.pop(), p.pop();
            printf("%d\n", qpow(q.top(), p.top()));
        }
        else {
            printf("%lld\n", mulit);
        }
    }
}