自动搬运

查看原文

来自洛谷，原作者为

	Chinese_zjc_ 发生肾么事了?

搬运于2025-08-24 21:34:46，当前版本为作者最后更新于2020-06-26 12:25:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

不会离线和高级数据结构和中国剩余定理的人的福音!

Update 2020.6.26 21:00: 使用了离散化,防止在$D$操作中被卡$O(n^2log_2(n))$

你以为这题要么离线,要么高级数据结构,要么中国剩余定理这三种解法吗?

其实还有一种解法!

题目里只有五种操作,下面我们一个个来剖析这几种操作.

Part A:最大值

要求最大值,我们可以用一个排好序的数组的最后一个元素的下标$b(biggest)$来存储.

当这个数不复存在时,显然在剩下的元素中的最大值的下标比$b$要小.

那我们只要简单地向左一个个地缩小范围,直到找到一个还存在的元素即可.

Part B:最小值

最小值跟最大值不是可以用同样的方法嘛,只不过反过来而已,我们用$s(smallest)$来表示最小值元素的下标.

Part C:$a_b^{a_s}\mod317847191$

这不就是把上面两个玩意合在一起加个快速幂吗,没什么好讲的,略.

Part D:$\prod x(x\in A)\mod317847191$

这自然成为了这种解法最复杂的地方.

自然容易想到使用一个变量$sum$来存储这个答案,然后使用乘法逆元来当作删除.

但是远没有这么简单,因为我们的模数$317847191$并不是一个质数,有一部分的数字是没有模$317847191$意义下的乘法逆元的.

比如说,因为$317847191=71\times113\times173\times229$,所以说因数中有$71,113,173,229$的数字都是没有模$317847191$意义下的逆元的.

那怎么办?

我马上就想到把这几个因子从$sum$中单独提取出来,在最后的时候统一处理.

可以得到一个式子:

$$\prod x(x\in A)\equiv sum\times71^{t_{71}}\times113^{t_{113}}\times173^{t_{173}}\times229^{t_{229}}\pmod{317847191} $$

其中$t_x$表示因子$x$出现的次数.

但是,毒瘤的出题人肯定不愿意让我们一点思考都没有就让我们过.

$As\ a\ result$,我$TLE$了.

显然还要继续找方法优化,但是我们可以从哪里入手呢?

现在我们计算一次这个式子需要计算$4$次快速幂,有没有方法可以减少计算快速幂的次数吗?

答案是有的.

下面有一个引理:

$$p_b^a\bmod\prod_{i=1}^np_i=p_b\times(p_b^{a-1}\bmod(\frac{\prod_{i=1}^np_i}{p_b})) $$

其中$p_i$是质数,且$p_i\not=p_j(i\not=j)$.

证明:

我们在小学二年级就学过:若$a\div b=c\cdots\cdots d$,则$ae\div be=c\cdots\cdots de$.

那我们把这个式子套进去就可以了,我们不用管$c$,令$a=p_b^{a-1},b=\frac{\prod_{i=1}^np_i}{p_b},d=p_b^{a-1}\bmod(\frac{\prod_{i=1}^np_i}{p_b}),e=p_b$.

则可以得到$a\bmod b=d,(ae)\bmod(be)=de$.

那么就有$(ae)\bmod(be)=de=e\cdot(a\bmod b)$.

即可得$(p_b^{a-1}\cdot p_b)\bmod(\frac{\prod_{i=1}^np_i}{p_b}\cdot p_b)=p_b\cdot(p_b^{a-1}\bmod\frac{\prod_{i=1}^np_i}{p_b})$.

即$p_b^a\bmod\prod_{i=1}^np_i=p_b\cdot(p_b^{a-1}\bmod\frac{\prod_{i=1}^np_i}{p_b})$.

$Q.E.D.$

好,现在就可以直接用这个玩意来先代入了.

$$\prod x(x\in A)\equiv sum\times(71\times(71^{t_{71}-1}\bmod(\frac{317847191}{71})))\times(113\times(113^{t_{113}-1}\bmod(\frac{317847191}{113})))\times(173\times(173^{t_{173}-1}\bmod(\frac{317847191}{173})))\times(229\times(229^{t_{229}-1}\bmod(\frac{317847191}{229})))\pmod{317847191} $$

也可以简写为:

$$\prod x(x\in A)\equiv sum\times\prod_{p_i|317847191}(p_i\times(p_i^{t_{p_i}-1}\bmod(\frac{317847191}{p_i})))\pmod{317847191} $$

其中$p_i$是质数,且$p_i\not=p_j(i\not=j)$.

可是这样算还是要算快速幂啊.

但是,我们可以发现$p_i$在取模$\frac{317847191}{p_i}$意义下已经是有乘法逆元的了.

所以我们可以预先算好$p_i^{t_{p_i}-1}\bmod\frac{317847191}{p_i}$的值,用$s_i$存储,要加一个数就乘以$p_i$,要删一个数就乘以$p_i$在取模$\frac{317847191}{p_i}$意义下的乘法逆元.

这样就可以$O(1)$处理了.

代码如下:

//This code was made by Chinese_zjc_.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<unordered_map>
#include<queue>
#define int long long//小心爆零
#define INF 0x3fffffffffffffff
#define MOD 317847191
using namespace std;
const int q71=1387153,q113=1020576,q173=785883,q229=1248575;//预先算好四个特殊数字的相应逆元
int n,m,tmp,b,s,sum=1,x,y,a[1000001],cnt,s71=q71,s113=q113,s173=q173,s229=q229,ans71,ans113,ans173,ans229,t71,t113,t173,t229;
//n,m,a如题意所述;
//b,s,sxxx,txxx如上文所述;
//tmp是暂存用的工具变量;
//sum是除了四个特殊值外的总乘积;
//x,y是用在exgcd里的变量,exgcd完后x是X模Y意义下的逆元;
//ansxxx表示xxx在T操作里的贡献;
//cnt表示集合里不重复元素的总个数(包括删掉的);
struct NUM{
	int v,t;
}num[1000001];//离散化,把重复的放到一起方便删除
char c;//工具变量
inline int power(int A,int B,int C)//快速幂&cdd(不是)
{
	int TMP=1;
	while(B)
	{
		if(B&1)
		{
			TMP=(TMP*A)%C;
		}
		B>>=1;
		A=(A*A)%C;
	}
	return TMP;
}
inline void exgcd(int X,int Y)//算乘法逆元用
{
	if(Y==0)
	{
		x=1;
		y=0;
		return;
	}
	exgcd(Y,X%Y);
	int TMP=x;
	x=y;
	y=TMP-X/Y*y;
}
inline void d(int now)//删除操作,通过二分找到一个还没被删掉的,把used标记打成true
{
	int l=s,r=b,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(num[mid].v<now)
		{
			l=mid+1;
			continue;
		}
		if(num[mid].v>now)
		{
			r=mid-1;
			continue;
		}
		if(num[mid].v==now)
		{
			--num[mid].t;
			return;
		}
	}
	--num[l].t;
}
inline void write(int now)//快写
{
	if(now==0)
	{
		putchar('0');
	}
	char s[100];
	int len=0;
	while(now)
	{
		s[len++]=now%10+'0';
		now/=10;
	}
	while(len)
	{
		putchar(s[--len]);
	}
	putchar('\n');
}
inline void read(int &now)//快读数字
{
	now=0;
	char cc=getchar();
	while('0'>cc||'9'<cc)
	{
		cc=getchar();
	}
	while('0'<=cc&&cc<='9')
	{
		now=(now<<3)+(now<<1)+(cc^'0');
		cc=getchar();
	}
}
inline void rd(char &now)//快读字符
{
	now=getchar();
	while('A'>now||now>'Z')
	{
		now=getchar();
	}
}
signed main()
{
	read(n);
	read(m);
	for(int i=1;i<=n;++i)
	{
		read(a[i]);
		tmp=a[i];
        //特殊处理几个特殊数字并提出因子
		while(tmp%71==0)
		{
			++t71;
			s71=s71*71%(MOD/71);
			tmp/=71;
		}
		while(tmp%113==0)
		{
			++t113;
			s113=s113*113%(MOD/113);
			tmp/=113;
		}
		while(tmp%173==0)
		{
			++t173;
			s173=s173*173%(MOD/173);
			tmp/=173;
		}
		while(tmp%229==0)
		{
			++t229;
			s229=s229*229%(MOD/229);
			tmp/=229;
		}
		sum=(sum*tmp)%MOD;//把剩下的其它数字直接丢一起
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)
	{
		if(a[i]!=num[cnt].v)
		{
			num[++cnt].v=a[i];
		}
		++num[cnt].t;
	}
	s=1;
	b=cnt;
	while(m)
	{
		--m;
		rd(c);
		if(c=='D')//删除
		{
			read(tmp);
			d(tmp);
			while(tmp%71==0)
			{
				--t71;
				s71=s71*q71%(MOD/71);
				tmp/=71;
			}
			while(tmp%113==0)
			{
				--t113;
				s113=s113*q113%(MOD/113);
				tmp/=113;
			}
			while(tmp%173==0)
			{
				--t173;
				s173=s173*q173%(MOD/173);
				tmp/=173;
			}
			while(tmp%229==0)
			{
				--t229;
				s229=s229*q229%(MOD/229);
				tmp/=229;
			}
			exgcd(tmp,MOD);
			sum=(sum*(x%MOD+MOD))%MOD;
		}
		if(c=='B')//最大值
		{
			while(!num[b].t)
			{
				--b;
			}
			write(num[b].v);
		}
		if(c=='S')//最小值
		{
			while(!num[s].t)
			{
				++s;
			}
			write(num[s].v);
		}
		if(c=='M')//a[b]^a[s] mod MOD
		{
			while(!num[b].t)
			{
				--b;
			}
			while(!num[s].t)
			{
				++s;
			}
			write(power(num[b].v,num[s].v,MOD));
		}
		if(c=='T')//总乘积
		{
            //t为0时是唯一的ans为1的时候,特判处理
			if(t71)
			{
				ans71=71*s71;
			}
			else
			{
				ans71=1;
			}
			if(t113)
			{
				ans113=113*s113;
			}
			else
			{
				ans113=1;
			}
			if(t173)
			{
				ans173=173*s173;
			}
			else
			{
				ans173=1;
			}
			if(t229)
			{
				ans229=229*s229;
			}
			else
			{
				ans229=1;
			}
			write(sum*ans71%MOD*ans113%MOD*ans173%MOD*ans229%MOD);//得到答案
		}
	}
	return 0;
}