题目链接

BZOJ4105

题解

平方操作orz，虽说应该是线段树，但是不会维护啊QAQ

小瞧一眼题解。。。

平方成环？环长\(lcm\)小于\(60\)?

果然还是打表找规律题。。。。

那就很好做了，先预处理每个数是否在环上，如果当前区间存在数不在环上，就暴力修改

如果当前区间都在环上了，就处理出环，之后每次修改只在环上走一步即可

每次修改可能会重置\(logn\)个节点的信息，由于重置一次要求出环，是\(O(60)\)的，所以修改总复杂度是\(O(60nlogn)\)的，可以接受

#include<algorithm>

#include<iostream>

#include<cstdio>

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define ls (u << 1)

#define rs (u << 1 | 1)

#define res register

using namespace std;

const int maxn = 100005,maxm = 10005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int ou[20];

inline void write(int x){

	if (!x) {putchar('0'); return;}

	int tmp = 0;

	while (x) ou[++tmp] = x % 10,x /= 10;

	while (tmp) putchar(ou[tmp--] + '0');

}

int n,m,P,A[maxn],Nxt[maxn],inc[maxn];

int sum[maxn << 2],tag[maxn << 2],val[maxn << 2];

int pos[maxn << 2],siz[maxn << 2];

int cir[maxn << 2][65],L,R;

inline int gcd(int a,int b){return b ? gcd(b,a % b) : a;}

inline int lcm(int a,int b){return a / gcd(a,b) * b;}

void upd(int u){

	sum[u] = sum[ls] + sum[rs];

	val[u] = val[ls] & val[rs];

	if (val[u]){

		pos[u] = 0;

		siz[u] = lcm(siz[ls],siz[rs]);

		for (int i = pos[ls],j = pos[rs],k = 0; k < siz[u]; k++){

			cir[u][k] = cir[ls][i] + cir[rs][j];

			i = i + 1 == siz[ls] ? 0 : i + 1;

			j = j + 1 == siz[rs] ? 0 : j + 1;

		}

	}

}

void pd(int u){

	if (tag[u]){

		pos[ls] = pos[ls] + tag[u];

		pos[rs] = pos[rs] + tag[u];

		if (pos[ls] >= siz[ls]) pos[ls] %= siz[ls];

		if (pos[rs] >= siz[rs]) pos[rs] %= siz[rs];

		sum[ls] = cir[ls][pos[ls]];

		sum[rs] = cir[rs][pos[rs]];

		tag[ls] += tag[u]; tag[rs] += tag[u];

		tag[u] = 0;

	}

}

void build(int u,int l,int r){

	if (l == r){

		sum[u] = A[l];

		val[u] = inc[A[l]];

		if (val[u]){

			pos[u] = 0;

			siz[u] = 0;

			cir[u][siz[u]++] = A[l];

			for (int i = Nxt[A[l]]; i != A[l]; i = Nxt[i])

				cir[u][siz[u]++] = i;

		}

		return;

	}

	int mid = l + r >> 1;

	build(ls,l,mid);

	build(rs,mid + 1,r);

	upd(u);

}

void modify(int u,int l,int r){

	if (l == r){

		if (val[u]){

			pos[u] = (pos[u] + 1) % siz[u];

			sum[u] = cir[u][pos[u]];

		}

		else {

			sum[u] = Nxt[sum[u]];

			if (inc[sum[u]]){

				val[u] = true;

				pos[u] = 0;

				siz[u] = 0;

				cir[u][siz[u]++] = sum[u];

				for (int i = Nxt[sum[u]]; i != sum[u]; i = Nxt[i])

					cir[u][siz[u]++] = i;

			}

		}

		return;

	}

	if (l >= L && r <= R && val[u]){

		pos[u] == siz[u] - 1 ? pos[u] = 0 : pos[u]++;

		sum[u] = cir[u][pos[u]];

		tag[u]++;

		return;

	}

	pd(u);

	int mid = l + r >> 1;

	if (mid >= L) modify(ls,l,mid);

	if (mid < R) modify(rs,mid + 1,r);

	upd(u);

}

int query(int u,int l,int r){

	if (l >= L && r <= R) return sum[u];

	pd(u);

	int mid = l + r >> 1;

	if (mid >= R) return query(ls,l,mid);

	if (mid < L) return query(rs,mid + 1,r);

	return query(ls,l,mid) + query(rs,mid + 1,r);

}

int vis[maxn],fa[maxn],now;

void dfs(int u){

	vis[u] = now;

	if (vis[Nxt[u]]){

		if (vis[Nxt[u]] != now) return;

		else {

			for (int i = u; i != Nxt[u]; i = fa[i])

				inc[i] = true;

			inc[Nxt[u]] = true;

			return;

		}

	}

	fa[Nxt[u]] = u; dfs(Nxt[u]);

}

int main(){

	n = read(); m = read(); P = read(); REP(i,n) A[i] = read();

	for (int i = 0; i < P; i++) Nxt[i] = i * i % P;

	for (int i = 0; i < P; i++)

		if (!vis[i]){now++; dfs(i);}

	build(1,1,n);

	int opt;

	while (m--){

		opt = read(); L = read(); R = read();

		if (!opt) modify(1,1,n);

		else write(query(1,1,n)),putchar('\n');

	}

	return 0;

}