【题目链接】
【BZOJ 3211】 点击打开链接
【BZOJ 3038】 点击打开链接
【算法】
线段树
开根操作直接开到叶子节点,注意当区间中所有数都是0或1时,不需要开根
【代码】
#include<bits/stdc++.h> using namespace std; #define MAXN 100010 int i,n,m,opt,l,r; long long a[MAXN]; struct SegmentTree { struct Node { int l,r; long long sum; bool flag; } Tree[MAXN<<2]; inline void update(int index) { Tree[index].sum = Tree[index<<1].sum + Tree[index<<1|1].sum; Tree[index].flag = Tree[index<<1].flag & Tree[index<<1|1].flag; } inline void build(int index,int l,int r) { int mid; Tree[index].l = l; Tree[index].r = r; if (l == r) { Tree[index].sum = a[l]; if (a[l] == 0 || a[l] == 1) Tree[index].flag = true; else Tree[index].flag = false; return; } mid = (l + r) >> 1; build(index<<1,l,mid); build(index<<1|1,mid+1,r); update(index); } inline void modify(int index,int l,int r) { int mid; if (Tree[index].flag) return; if (Tree[index].l == Tree[index].r) { Tree[index].sum = (long long)sqrt(Tree[index].sum); if (Tree[index].sum == 0 || Tree[index].sum == 1) Tree[index].flag = true; return; } mid = (Tree[index].l + Tree[index].r) >> 1; if (mid >= r) modify(index<<1,l,r); else if (mid + 1 <= l) modify(index<<1|1,l,r); else { modify(index<<1,l,mid); modify(index<<1|1,mid+1,r); } update(index); } inline long long query(int index,int l,int r) { int mid; if (Tree[index].l == l && Tree[index].r == r) return Tree[index].sum; mid = (Tree[index].l + Tree[index].r) >> 1; if (mid >= r) return query(index<<1,l,r); else if (mid + 1 <= l) return query(index<<1|1,l,r); else return query(index<<1,l,mid) + query(index<<1|1,mid+1,r); } } T; template <typename T> inline void read(T &x) { int f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; } for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x/10); putchar(x%10+'0'); } template <typename T> inline void writeln(T x) { write(x); puts(""); } int main() { read(n); for (i = 1; i <= n; i++) read(a[i]); T.build(1,1,n); read(m); while (m--) { read(opt); if (opt == 1) { read(l); read(r); writeln(T.query(1,l,r)); } else { read(l); read(r); T.modify(1,l,r); } } return 0; }