?
对n个整数有m个操作，共有两种操作：0 l r表示把区间[l,r]之间的数开方，1 l r表示询问[l,r]的和。
开方即单点更新。但所有的数都单点更新和模拟每什么差别。重点就是成段维护区间的和，因为当操作次数相当多时，这些数大部分就会变成1，因此可以用线段树维护区间的和，当这个区间的数全部是1就没必要更新了。
#include #include #include #include #include #include #include #include #include #include #include #include #include //#define LL long long #define LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 100010; struct node { int l,r; LL sum; }tree[maxn*4]; LL a[maxn]; void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; if(l == r) { tree[v].sum = a[l]; return; } int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); tree[v].sum = tree[v*2].sum + tree[v*2+1].sum; } void update(int v, int l, int r) { if(tree[v].sum == tree[v].r - tree[v].l + 1) return; if(tree[v].l == tree[v].r) { tree[v].sum = sqrt(tree[v].sum*1.0); return; } int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) update(v*2,l,r); else if(l > mid) update(v*2+1,l,r); else { update(v*2,l,mid); update(v*2+1,mid+1,r); } tree[v].sum = tree[v*2].sum + tree[v*2+1].sum; } LL query(int v, int l, int r) { if(tree[v].l == l && tree[v].r == r) return tree[v].sum; int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) return query(v*2,l,r); else if(l > mid) return query(v*2+1,l,r); else return query(v*2,l,mid) + query(v*2+1,mid+1,r); } int main() { int n,m,item = 1; int x,l,r; while(~scanf(%d,&n)) { for(int i = 1; i <= n; i++) scanf(%I64d,&a[i]); build(1,1,n); scanf(%d,&m); printf(Case #%d: ,item++); while(m--) { scanf(%d %d %d,&x,&l,&r); if(l > r) swap(l,r); if(x == 0) update(1,l,r); else printf(%I64d ,query(1,l,r)); } printf( ); } return 0; }