本文共 1994 字，大约阅读时间需要 6 分钟。
题目：
大意：先给你n个数。然后m次操作。。1：访问给定区间的和
0：把给定区间的每个数都开根号
注意一个特点。。。。。。总和最多2^63。。。如果只有1个数。。。。也就最多开7次根号。。。。。
即开着开着就恒为1。。。。。。所以，当该区间的和等于区间长度（r-l）+1的时候，该区间的值都不会再更新了。。。
通过这题知道：线段树提高效率的关键在于寻找合适的lazy标记，到满足一定条件的时候就不继续更新到点。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //Constant Declaration /*--------------------------*/ //#define LL long long #define LL __int64 const int M=100010;// const int INF=1<<30; const double EPS = 1e-11; const double PI = acos(-1.0); /*--------------------------*/ // some essential funtion /*----------------------------------*/ void Swap(int &a,int &b){ int t=a;a=b;b=t; } int Max(int a,int b){ return a>b?a:b; } int Min(int a,int b){ return a > 1; BuildTree(lson); BuildTree(rson); PushUP(rt); } void Update(int L,int R, int l,int r,int rt) { if (T[rt] == r - l + 1)//lazy { return; } if (l == r) { T[rt] = (LL)sqrt((double)T[rt]);//只能到底层改该点的值。。。 return ; } int m = (l + r) >> 1; if (L <= m) { Update(L, R , lson); } if (R > m) { Update(L, R , rson); } PushUP(rt); } LL Query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return T[rt]; } int m = (l + r) >> 1; LL ret = 0; if (L <= m) ret += Query(L , R , lson); if (m < R) ret += Query(L , R , rson); return ret; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int t, case1 = 0; //scanf("%d", &t); int n, m; int i, j; //scanf("%d%d", &n, &m); while (~scanf("%d", &n)) { printf("Case #%d:\n", ++case1); BuildTree(1, n, 1); scanf("%d", &m); while (m--) { int l, r, a; scanf("%d%d%d", &a, &l, &r); if (l > r) { l ^= r, r ^= l, l ^= r;//l要小于等于r } if (a == 0) { Update(l, r, 1, n, 1); } else { printf("%I64d\n", Query(l, r, 1, n, 1)); } } puts(""); } return 0; }
转载于:https://www.cnblogs.com/qiufeihai/archive/2012/04/05/2433073.html