记录编号	607812	评测结果	AAAAAAAAAA
题目名称	3134.[Codeforces] Willem, Chtholly and Seniorious	最终得分	100
用户昵称	梧叶已同秋雨去	是否通过	通过
代码语言	C++	运行时间	4.436 s
提交时间	2025-10-21 16:26:57	内存使用	8.55 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,y; 
struct node_t{
	int l,r;
	mutable long long v;
	node_t(const int &il,const int &ir,const long long &iv):l(il),r(ir),v(iv){}
	bool operator<(const node_t &o) const {return l<o.l;}
};
set<node_t>odt;
auto split(int x){
	auto it=odt.lower_bound(node_t(x,0,0));
	if(it!=odt.end()&&it->l==x)return it;
	it--;
	int l=it->l,r=it->r;long long v=it->v;
	odt.erase(it);
	odt.insert(node_t(l,x-1,v));
	return odt.insert(node_t(x,r,v)).first;
}
void assgin(int l,int r,long long v){//区间修改 
	auto itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert(node_t(l,r,v));
}
long long ci(long long a, long long b, long long mod) {  // 修正的幂运算函数
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
void perform(int l,int r,int op,int x){//区间遍历 
	auto itr=split(r+1),itl=split(l);
	if (op == 3) {
        vector<pair<long long, long long>> segments; 
        for (auto it = itl; it != itr; ++it) {
            segments.push_back({it->v, it->r - it->l + 1});
        }
        sort(segments.begin(), segments.end());
        int cnt = 0;
        for (auto p : segments) {
            if (cnt + p.second >= x) {
                cout << p.first << "\n";
                return;
            }
            cnt += p.second;
        }
//        if (!segments.empty()) {
//            cout << segments.back().first << "\n";
//        }
        return; 
	}
	long long sum=0;
	for(;itl!=itr;itl++){
		int l=itl->l,r=itl->r;
		if(op==1){
			itl->v+=x;
		}
		if(op==4){
			sum+=((r-l+1)*ci(itl->v,x,y))%y;
			sum%=y;
		}
	}
	if(op==4){
		cout<<sum<<"\n";
		return;
	}return;
} 
long long a[200005];
int main(){
	freopen("kdl.in","r",stdin); 
	freopen("kdl.out","w",stdout); 
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i]; 
		odt.insert(node_t(i,i,a[i]));
	}
	for(int i=1;i<=m;i++){
		int l,r,op,x;
		cin>>op>>l>>r; 
		if(l>r){
			swap(l,r);
		}
//		printf("l:%d  r:%d  op:%d\n",l,r,op); 
		if(op==3){
			cin>>x;
			perform(l,r,op,x);
		}else{
			cin>>x;
			if(op==4){
				cin>>y;
				perform(l,r,op,x);
			}
			if(op==1){
				perform(l,r,op,x);
			} 
			if(op==2){
				assgin(l,r,x);
			}
		}
	}
	return 0;
}