[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
题意:给一个序列,要求维护两个操作
1:将区间[L,R]里面的数开方下取整
2:求区间[L,R]里面元素的和
第一反应是线段树,但是这里面有个矛盾:开方不好处理,如果将序列表示成对数,求和又不好处理……
幸运的是,开方操作收敛的很快,从long long 到 1,只要8次,于是每次对区间操作,我们在线段树基础上进行改动:线段树最后将待查询区间会分成Log(N)个区间,绝对不能将操作区间分成小段……但是现在要这么做,因为每个点最多被覆盖8次之后就是1了……于是对每个节点维护一个isone标记,标记这一段是不是1,每次修改都递归下去直接修改非1的点,并且维护isone标记……这样均摊下来,每个点最多被改8次……

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cassert>
 4 
 5 typedef long long Long;
 6 Long sum[410000];
 7 Long data[110000];
 8 bool isone[410000];
 9 int n;
10 const int root = 1;
11 
12 void build(int now,int left,int right) {
13     if (left == right) {
14         sum[now] = data[left];
15         isone[now] = sum[now] == right - left + 1;
16     } else {
17         int mid = (left + right) >> 1;
18         build(now + now,left,mid);
19         build(now + now + 1,mid + 1,right);
20         sum[now] = sum[now + now] + sum[now + now + 1];
21         isone[now] = sum[now] == right - left + 1;
22     }
23 }
24 
25 Long mySqrt(Long x) {
26     double tmp = x;
27     x = Long(sqrt(tmp) + 1e-8);
28     return x;
29 }
30 
31 Long getSum(int now,int left,int right,int l,int r) {
32     if (left > r || right < l) return 0;
33     if (l <= left && right <= r) return sum[now];
34     int mid = (left + right) >> 1;
35     return getSum(now + now,left,mid,l,r) 
36         + getSum(now + now + 1,mid + 1, right, l, r);
37 }
38 
39 void change(int now,int left,int right,int l,int r) {
40     if (left > r || right < l) return;
41     if (isone[now]) return;
42     if (left == right) {
43         sum[now] = mySqrt(sum[now]);
44         isone[now] = sum[now] == right - left + 1;
45     } else {
46         int mid = (left + right) >> 1;
47         change(now + now,left,mid,l,r);
48         change(now + now + 1,mid + 1,right,l,r);
49         sum[now] = sum[now + now] + sum[now + now + 1];
50         isone[now] = sum[now] == right - left + 1;
51     }
52 }
53 
54 int main() {
55     int nn = 0;
56     while (scanf("%d",&n) == 1) {
57         for (int i = 0; i < n; i++) {
58             scanf("%lld",data + i);
59             assert(data[i] > 0);
60         }
61         build(root,0,n-1);
62         int m;
63         scanf("%d",&m);
64         printf("Case #%d:\n"++ nn);
65         while (m--) {
66             int ctrl,l,r;
67             scanf("%d%d%d",&ctrl,&l,&r);
68             l --; r --;
69             if (l > r) {int tmp = l; l = r; r = tmp;}
70             if (ctrl == 1) {
71                 printf("%lld\n",getSum(root,0,n-1,l,r));
72             } else {
73                 change(root,0,n-1,l,r);
74             }
75         }
76         printf("\n");
77     }
78     return 0;
79 }
posted on 2011-09-10 20:19 sweetsc 阅读(1001) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: