记录编号	577186	评测结果	AAAAAAAAAA
题目名称	逆元数列	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	1.227 s
提交时间	2022-10-25 07:57:59	内存使用	5.73 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 100010;
int n, m, p, s, a[MAXN], b[MAXN], sum1[MAXN], sum2[MAXN], tag[MAXN];
int power(int x, int y) {
	int res = 1;
	while(y) {
		if(y & 1) {
			res = res * x % p;
		}
		x = x * x % p;
		y /= 2;
    }
    return res;
}
void update(int x, int y) {
	int ka = x / s, kb = y / s;
	if(ka == kb) {
		for(int i = x; i <= y; i ++) {
			sum1[ka] += b[i] - a[i];
			sum2[ka] += a[i] - b[i];
			swap(a[i], b[i]);
		}
		return ;
	}
	for(int i = x; i < (ka + 1) * s; i ++) {
		sum1[ka] += b[i] - a[i];
		sum2[ka] += a[i] - b[i];
		swap(a[i], b[i]);
	}
	for(int i = kb * s; i <= y; i ++) {
		sum1[kb] += b[i] - a[i];
		sum2[kb] += a[i] - b[i];
		swap(a[i], b[i]);
	}
	for(int i = ka + 1; i < kb; i ++) {
		tag[i] ++;
		tag[i] %= 2;
//		swap(sum1[i], sum2[i]);
	}
}
void query(int x, int y) {
	int ka = x / s, kb = y / s, sum = 0;
	if(ka == kb) {
		for(int i = x; i <= y; i ++) {
			if(tag[ka]) {
				sum += b[i];
			}
			else {
				sum += a[i];
			}
		}
		cout << sum << endl;
		return ;
	}
	for(int i = x; i < (ka + 1) * s; i ++) {
		if(tag[ka]) {
			sum += b[i];
		}
		else {
			sum += a[i];
		}
	}
	for(int i = kb * s; i <= y; i ++) {
		if(tag[kb]) {
			sum += b[i];
		}
		else {
			sum += a[i];
		}
	}
	for(int i = ka + 1; i < kb; i ++) {
		if(tag[i]) {
			sum += sum2[i];
		}
		else
		sum += sum1[i];
	}
	cout << sum << endl;
}
signed main() {
	freopen("invarray.in", "r", stdin);
	freopen("invarray.out", "w", stdout);
	cin >> n >> m >> p;
	s = sqrt(n);
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		sum1[i / s] += a[i];
	}
	for(int i = 1; i <= n; i ++) {
		b[i] = power(a[i], p - 2);
		sum2[i / s] += b[i];
	}
	for(int i = 1; i <= m; i ++) {
		int op, l, r;
		cin >> op >> l >> r;
		if(op == 1) {
			update(l, r);
		}
		else {
			query(l, r);
		}
	}
	return 0;
} 

// 分块大法好啊 ！