记录编号	607785	评测结果	AAAAAAAAAA
题目名称	3134.[Codeforces] Willem, Chtholly and Seniorious	最终得分	100
用户昵称	李金泽	是否通过	通过
代码语言	C++	运行时间	2.701 s
提交时间	2025-10-20 21:59:43	内存使用	8.79 MiB

#include<cstdio>
#include<ctime>
#include<algorithm>
#include<map>
#define N 100005
#define ll long long
using namespace std;
ll n,m,a[N],cnt,op,l,r,x,y,ans;
struct node{ll v,l;}b[N];
bool operator<(const node &x,const node &y){return x.v<y.v;}
map<ll,ll>mp;
void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
map<ll,ll>::iterator split(ll x)
{
	auto it=prev(mp.upper_bound(x));
	if(it->first==x)return it;
	return mp.insert(it,make_pair(x,it->second));
}
ll fp(ll a,ll n,ll mod)
{
	ll ans=1;a%=mod;
	while(n)
	{
		if(n&1)ans=ans*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return ans;
}
int main(){
	freopen("kdl.in","r",stdin);freopen("kdl.out","w",stdout);
	scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%lld",a+i);
	for(ll i=1;i<=n;i++)
		if(i==1||a[i]^a[i-1])
			mp[i]=a[i];
	mp[n+1]=0;
	while(m--)
	{
		scanf("%lld%lld%lld%lld",&op,&l,&r,&x);
		if(l>r)swap(l,r);
		switch(op)
		{
			case 1:{
				split(l);split(r+1);
				for(auto it=mp.find(l);it->first<=r;it++)
					it->second+=x;
				break;
			}
			case 2:{
				split(l);split(r+1);
				auto it=mp.find(l);
				while(it->first!=r+1)it=mp.erase(it);
				mp[l]=x;
				break;
			}
			case 3:{
				split(l);split(r+1);cnt=0;
				for(auto it=mp.find(l);it->first<=r;)
				{
					ll len=it->first,v=it->second;it++;len=it->first-len;
					b[++cnt]={v,len};
				}
				sort(b+1,b+cnt+1);
				for(ll i=1;;i++)
				{
					if(b[i].l>=x){printf("%lld\n",b[i].v);break;}
					x-=b[i].l;
				}
				break;
			}
			case 4:{
				scanf("%lld",&y);ans=0;
				split(l);split(r+1);
				for(auto it=mp.find(l);it->first<=r;)
				{
					ll len=it->first,v=it->second;it++;len=it->first-len;
					ans=(ans+fp(v,x,y)*len)%y;
				}
				printf("%lld\n",ans);
				break;
			}
		}
	}
	return 0;
}