数列分块入门5
题意
有 个数， 次操作，每次操作为区间开方或者区间求和。
解法
分块。
，而 ，所以 最多开方 次就变成 。所以可以用一个 来标记每一个块中有多少个 ，如果 ，其中 表示块的大小，则这个块中全是 ，那么就不用再对这个块进行操作了。然后用 来维护每一个块的答案即可。
修改的操作复杂度为小块 次操作 的 加大块的 。
查询的复杂度为 ， 次查询。
所以总复杂度为 。
代码
#pragma region
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
namespace fastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
//fread->R
bool IOerror = 0;
//inline char nc(){char ch=getchar();if(ch==-1)IOerror=1;return ch;}
inline char nc() {static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;if (p1 == pend) {p1 = buf;pend = buf + fread(buf, 1, BUF_SIZE, stdin);if (pend == p1) {IOerror = 1;return -1;}}return *p1++;
}
inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
template <class T>
inline bool R(T &x) {bool sign = 0;char ch = nc();x = 0;for (; blank(ch); ch = nc());if (IOerror) return false;if (ch == '-') sign = 1, ch = nc();for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';if (sign) x = -x;return true;
}
inline bool R(double &x) {bool sign = 0;char ch = nc();x = 0;for (; blank(ch); ch = nc());if (IOerror) return false;if (ch == '-') sign = 1, ch = nc();for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';if (ch == '.') {double tmp = 1;ch = nc();for (; ch >= '0' && ch <= '9'; ch = nc())tmp /= 10.0, x += tmp * (ch - '0');}if (sign)x = -x;return true;
}
inline bool R(char *s) {char ch = nc();for (; blank(ch); ch = nc());if (IOerror)return false;for (; !blank(ch) && !IOerror; ch = nc())*s++ = ch;*s = 0;return true;
}
inline bool R(char &c) {c = nc();if (IOerror) {c = -1;return false;}return true;
}
template <class T, class... U>
bool R(T &h, U &... t) { return R(h) && R(t...); }
#undef OUT_SIZE
#undef BUF_SIZE
}; // namespace fastIO
using namespace fastIO;
template <class T>
void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) { _W(x.F), putchar(' '), _W(x.S); }
template <class T>
void _W(const vector<T> &x) {for (auto i = x.begin(); i != x.end(); _W(*i++))if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &... tail) { _W(head), putchar(sizeof...(tail) ? ' ' : '\n'), W(tail...); }
#pragma endregion
const int maxn = 1e5 + 5;
ll a[maxn], B, cnt[maxn];
ll res[maxn];
void update(int l, int r) {int idl = l / B, idr = r / B;if (idl == idr) {rep(i, l, r) {if (a[i] == 2 || a[i] == 3) cnt[idl]++;res[idl] -= a[i];a[i] = sqrt(a[i]);res[idl] += a[i];}} else {rep(i, l, (idl + 1) * B - 1) {if (a[i] == 2 || a[i] == 3) cnt[idl]++;res[idl] -= a[i];a[i] = sqrt(a[i]);res[idl] += a[i];}rep(id, idl + 1, idr - 1) {if (cnt[id] == B) continue;rep(i, id * B, (id + 1) * B - 1) {if (a[i] == 2 || a[i] == 3) cnt[id]++;res[id] -= a[i];a[i] = sqrt(a[i]);res[id] += a[i];}}rep(i, idr * B, r) {if (a[i] == 2 || a[i] == 3) cnt[idr]++;res[idr] -= a[i];a[i] = sqrt(a[i]);res[idr] += a[i];}}
}
ll query(int l, int r) {int idl = l / B, idr = r / B;ll ans = 0;if (idl == idr) {rep(i, l, r) ans += a[i];} else {rep(i, l, (idl + 1) * B - 1) ans += a[i];rep(id, idl + 1, idr - 1) ans += res[id];rep(i, idr * B, r) ans += a[i];}return ans;
}int main() {int n;R(n);B = sqrt(n);rep(i, 1, n) {R(a[i]);cnt[i / B] += (a[i] == 1);res[i / B] += a[i];}rep(i, 1, n) {ll op, l, r, x;R(op, l, r, x);if (op == 1)W(query(l, r));elseupdate(l, r);}
}