题意
给定$n$个正整数,每次可以将一个区间内的每个数取算术平方根(向下取整),以及询问一个区间的和,初始时每个数不超过$2^{63}$
分析
直接分析数据,因为每个数最大不超过$2^{63}$,因此最多取$6$次算术平方根其值就不变了,因此最多所有数最多只会进行$6n$次改变,且最终值为$1$,因此我们只需要处理求和操作和判断当前区间的数是否已经不变了即可。因为最后每个数会变成1,因此判断不变的条件就是区间长度是否等于区间和。
#include <bits/stdc++.h>
#define int long long
#define lc u << 1
#define rc u << 1 | 1
using namespace std;
const int N = 100010;
int n, w[N];
struct Node{
int l, r, sum;
}tr[N * 4];
void pushup (int u)
{
tr[u].sum = tr[lc].sum + tr[rc].sum;
}
void build (int u, int l, int r)
{
tr[u] = {l, r, w[l]};
if (l == r) return;
int mid = l + r >> 1;
build (lc, l, mid), build (rc, mid + 1 , r);
pushup (u);
}
void modify (int u, int l, int r)
{
if (tr[u].sum == tr[u].r - tr[u].l + 1) return;
if (tr[u].l == tr[u].r)
{
tr[u].sum = sqrt(tr[u].sum);
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify (lc, l, r);
if (r > mid) modify (rc, l, r);
pushup (u);
}
int query (int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if (l <= mid) res = query (lc, l, r);
if (r > mid) res += query (rc, l, r);
return res;
}
signed main()
{
cin.sync_with_stdio(0);cin.tie(0);cout.tie(0);
int turn = 0;
while (cin >> n) {
cout << "Case #" << ++turn << ":\n";
for (int i = 1; i <= n; i++) cin >> w[i];
build (1, 1, n);
int m;
cin >> m;
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (l > r) swap(l, r);
if (!op) modify (1, l, r);
else cout << query (1, l, r) << endl;
}
cout << endl;
}
}