给定一个长度为n的序列，m次操作。
每次操作
可以将一个区间内的所有数字变为它的根号。
可以查询一个区间内所有元素的和。
线段树的初级应用。
如果把一个区间内的元素都改为它的根号的话，是需要每个数字都进行修改的。这样就会超时。
一个优化就是区间修改的当区间时，若区间长度等于区间和，那这个区间里的所有元素都不用修改了。
而题目中区间里的元素之和最大是 2^63，时间完全够用。
#include#include #include #include using namespace std;#define maxn 100000 + 1000#define LL long long#define in_int(x) int x; scanf("%d", &x);struct Sect{ int l, r, flag; LL sum; Sect() : flag(0) {}}t[4*maxn];LL n, a[4*maxn];void build(int id, int l, int r){ if (l == r) { t[id].sum = a[l]; t[id].l = l, t[id].r = r; return; } int mid = (l+r) >> 1; build(id*2, l, mid); build(id*2+1, mid+1, r); t[id].sum = t[id*2].sum + t[id*2+1].sum; t[id].l = t[id*2].l, t[id].r = t[id*2+1].r;}//void update(int id, int x, int val)//{// if(t[id].l == t[id].r)// {// if (t[id].l == x) t[id].sum += val;// return;// }// int mid = (t[id].l+t[id].r) >> 1;// if (x <= mid) update(id*2, x, val);// else update(id*2+1, x, val);// t[id].sum = t[id*2].sum + t[id*2+1].sum;//}//void markdown(int id)//{// t[id].flag = 0;// t[id].sum = (int)sqrt(t[id].sum);// if (t[id*2].flag) markdown(id*2);// t[id*2].flag = 1;// if (t[id*2+1].flag) markdown(id*2+1);// t[id*2+1].flag = 1;//}LL query(int id, int l, int r){ //if(t[id].flag) markdown(id); if (t[id].l >= l && t[id].r <= r) return t[id].sum; int mid = (t[id].l + t[id].r) >> 1; if (r <= mid) return query(id*2, l, r); else if (l > mid) return query(id*2+1, l, r); else return query(id*2, l, mid) + query(id*2+1, mid+1, r);}void change(int id, int l, int r){ if (t[id].l == t[id].r) { t[id].sum = sqrt(t[id].sum); return; } if (t[id].r - t[id].l + 1 == t[id].sum) return; int mid = (t[id].l + t[id].r) >> 1; if (r <= mid) change(id*2, l, r); else if (l > mid) change(id*2+1, l, r); else { change(id*2, l, mid); change(id*2+1, mid+1, r); } t[id].sum = t[id*2].sum + t[id*2+1].sum;}int main(){ int n, ca = 0; while(scanf("%lld", &n) != EOF) { for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); build(1, 1, n); printf("Case #%d:\n", ++ca); in_int(m); for (int i = 1; i <= m; i++) { in_int(x); in_int(l); in_int(r); if (l > r) swap(l, r); if (x) printf("%lld\n", query(1, l, r)); else change(1, l, r); } printf("\n"); }}