这8个测试点的所有数的乘积貌似都没有超过那个mod? 不然我这种代码怎么会AC了
代码如下:
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <unordered_map>
typedef long long ll;
const ll mod = 317847191;
int n, m;
ll multi = 1;
unordered_map<ll, int> ump;
vector<ll> v1, v2;
ll getmax()
{
while (!ump[v2[0]])
{
pop_heap(v2.begin(), v2.end());
v2.pop_back();
}
return v2[0];
}
ll getmin()
{
while (!ump[v1[0]])
{
pop_heap(v1.begin(), v1.end(), greater<int>());
v1.pop_back();
}
return v1[0];
}
ll fastpow(ll a, ll b, ll mod)
{
ll res = 1;
a %= mod;
while (b > 0)
{
if (b & 1)
res = (res * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
ll t;
for (int i = 1; i <= n; ++i)
{
cin >> t;
multi = multi * t % mod;
if (!ump[t])
{
v1.push_back(t);
v2.push_back(t);
push_heap(v1.begin(), v1.end(), greater<int>());
push_heap(v2.begin(), v2.end());
}
ump[t]++;
}
char op;
ll x;
while (m--)
{
cin >> op;
if (op == 'D')
{
cin >> x;
if (ump[x] > 0)
{
ump[x]--;
multi = multi / x; //问题在这里,这里这么写,直接除掉被删掉的数,本不应该AC的
}
}
else if (op == 'B')
{
cout << getmax() << "\n";
}
else if (op == 'S')
{
cout << getmin() << "\n";
}
else if (op == 'M')
{
cout << fastpow(getmax(), getmin(), mod) << "\n";
}
else if (op == 'T')
{
cout << multi << "\n";
}
}
return 0;
}