能卡掉下面这个 $O(n\times m)$ 的奇怪做法。

AC 记录

如果数据随机的话跑的飞快。如果无修改只有查询，就会被

卡出翔
           ————lxl

#include <math.h>
#include <stdio.h>
#define N 100005
#define LL long long
LL a[N], ret;
int b[N], c[N], S[N];
int n, m, k;
int Find_Up(int x) {
	int pos = 0, k = b[0];
	for (int i = log2(k); i >= 0; --i) {
		int Nex = pos + (1 << i);
		if (Nex <= k && x > b[Nex])
			pos = Nex;
	}
	return (++pos) > k ? -1 : pos;
}
int Find_Low(int x) {
	int pos = b[0] + 1;
	for (int i = log2(pos); i >= 0; --i) {
		int Nex = pos - (1 << i);
		if (Nex >= 1 && x < b[Nex])
			pos = Nex;
	}
	return (--pos) < 1 ? -1 : pos;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		if (a[i] != 1)
			b[++b[0]] = i;
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; ++i) {
		int opt, l, r, t, L, R;
		scanf("%d %d %d", &opt, &l, &r);
		if (l > r)
			t = l, l = r, r = t;
		L = Find_Up(l), R = Find_Low(r);
		if (opt == 0) {
			if (L <= R) {
				S[0] = c[0] = 0;
				for (int j = L; j <= R; ++j) {
					a[b[j]] = sqrt(a[b[j]]);
					if (a[b[j]] == 1)
						S[++S[0]] = j;
				}
				for (int j = 1, pos = 1; j <= b[0]; ++j) ((pos > S[0]) || (S[pos] != j)) ? (c[++c[0]] = b[j]) : ++pos;
				for (int j = 0; j <= c[0]; ++j) b[j] = c[j];
			}
		} else {
			ret = k = 0;
			for (int j = L; j <= R; ++j) ret += a[b[j]], ++k;
			printf("%lld\n", ret + (r - l + 1 - k));
		}
	}
	return 0;
}