注意：并不是所有的区间修改需要懒标记，如果复杂度不高，可以直接单点改。
ll w[N]; struct node { int l, r; ll sum; }tr[N*4]; void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void build(int u, int l, int r) { if (l == r)tr[u] = { l,l,w[l] }; else { tr[u] = { l,r }; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } void modify(int u,int le,int re) { if (tr[u].r - tr[u].l + 1 == tr[u].sum)return;//全部为1，无需更改 if (tr[u].l == tr[u].r)tr[u].sum = (ll)sqrt(tr[u].sum); else { int mid = tr[u].l + tr[u].r >> 1; if (le <= mid)modify(u << 1, le, re); if (re > mid)modify(u << 1 | 1, le, re); pushup(u); } } ll query(int u,int l,int r) { if (tr[u].l >= l && tr[u].r <= r)return tr[u].sum; ll sum = 0; int mid = tr[u].l + tr[u].r >> 1; if (l <= mid)sum += query(u << 1, l, r); if (r > mid)sum += query(u << 1 | 1, l, r); return sum; } int main()//一个数开几次根号马上变1，所以单点修改不会超时 { ios::sync_with_stdio(false);cin.tie(nullptr); //freopen("in.txt", "r", stdin); int n,m; int cas = 0; while (cin >> n) { f(i, 1, n)cin >> w[i]; cin >> m; build(1, 1, n); printf("Case #%d:\n", ++cas); while (m--) { int a, b, c; cin >> a >> b >> c; if (b > c)swap(b, c); if (a == 0) { modify(1, b, c); } else printf("%lld\n", query(1,b, c)); } printf("\n"); } return 0; }