记录编号	577189	评测结果	AAAAAAAAAA
题目名称	3738.逆元数列	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	1.289 s
提交时间	2022-10-25 08:27:57	内存使用	5.27 MiB

#include <bits/stdc++.h>
#define Chtholly std::set<node>::iterator
typedef long long ll;

const int maxn = 1e5 + 5;
struct node {
	int l,r;
	mutable bool v;
	node() {
		l = r = 0;
		v = false;
	}
	node(int l,int r = 0,bool v = false):l(l),r(r),v(v){}
	bool operator < (const node& p)const {
		return l < p.l;
	}
};

std::set<node> s;

Chtholly split(int pos) {
	Chtholly it = s.lower_bound(node(pos));
	if(it != s.end()&&it -> l == pos)return it;
	-- it;
	if(it -> r < pos)return s.end();
	int l = it -> l,r = it -> r;
	bool v = it -> v;
	s.erase(it);
	s.insert(node(l , pos - 1 , v));
	return s.insert(node(pos , r , v)).first;
}

void assign(int l,int r) {
	Chtholly itr = split(r + 1),itl = split(l);
	for(;itl != itr;++ itl)
		itl -> v ^= true;
	return ;
}

ll p,a[maxn],b[maxn],sum[maxn],cnt[maxn];
int n,m,t;

ll query(int l,int r) {
	ll ans = 0;
	for(Chtholly it = s.begin();it != s.end();++ it) {
		if(it -> r < l)continue ;
		if(it -> l > r)break ;
		int L = std::max(l , it -> l),R = std::min(r , it -> r);
		if(it -> v)ans += cnt[R] - cnt[L - 1];
		else ans += sum[R] - sum[L - 1];
	}
	return ans;
}


ll power(ll x,ll y) {
	ll ans = 1;
	for(;y;y >>= 1) {
		if(y & 1)(ans *= x) %= p;
		(x *= x) %= p;
	}
	return ans;
}

void build() {
	for(node k : s) {
		if(!k.v)continue ;
		int l = k.l,r = k.r;
		for(int i = l;i <= r;++ i)
			std::swap(a[i] , b[i]);
	}
	for(int i = 1;i <= n;++ i) {
		sum[i] = sum[i - 1] + a[i];
		cnt[i] = cnt[i - 1] + b[i];
	}
	s.clear();
	s.insert(node(1 , n , false));
	t = std::sqrt(m) + rand() % 100;
	return ;
}

int main() {
	freopen("invarray.in","r",stdin);
	freopen("invarray.out","w",stdout);
	scanf("%d %d %lld",&n,&m,&p);
	s.insert(node(1 , n , false));
	for(int i = 1;i <= n;++ i) {
		scanf("%lld",&a[i]);
		b[i] = power(a[i] , p - 2);
		sum[i] = sum[i - 1] + a[i];
		cnt[i] = cnt[i - 1] + b[i];
	}
	
	t = std::sqrt(m) + rand() % 100;
	for(int i = 1;i <= m;++ i) {
		int op,l,r;
		scanf("%d %d %d",&op,&l,&r);
		if(op == 1) {
			assign(l , r);
		}
		else {
			printf("%lld\n",query(l , r));
		}
		if((int)s.size() >= t)build();
	}
	return 0;
}