首页 > 代码库 > hdu 4027 Can you answer these queries?

hdu 4027 Can you answer these queries?

2024-07-17 22:22:22   223人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4027

x可能比y大。 区间的每一个数在经过几次开方之后会变成1之后，在这个区间全部变成1之后，这个区间不用向下更新。这里可以判断一下。。

  1 #include <cstdio>  2 #include <cstring>  3 #include <cmath>  4 #include <algorithm>  5 #define maxn 100010  6 #define ll __int64  7 using namespace std;  8   9 ll a[maxn]; 10 int n,m; 11 int op,x,y; 12 struct node 13 { 14     int l,r; 15     ll sum; 16 }tree[maxn*4]; 17  18 void build(int i,int l,int r) 19 { 20     tree[i].l=l; 21     tree[i].r=r; 22     if(l==r) 23     { 24         tree[i].sum=a[l]; 25         return ; 26     } 27     int mid=(l+r)>>1; 28     build(i<<1,l,mid); 29     build(i<<1|1,mid+1,r); 30     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; 31 } 32  33 void update(int i,int l,int r) 34 { 35     if(tree[i].l==l&&tree[i].r==r&&tree[i].sum==tree[i].r-tree[i].l+1) return; 36     if(tree[i].l==tree[i].r) 37     { 38         tree[i].sum=sqrt(tree[i].sum*1.0); 39         return ; 40     } 41     int mid=(tree[i].l+tree[i].r)>>1; 42     if(r<=mid) 43     { 44         update(i<<1,l,r); 45     } 46     else if(l>mid) 47     { 48         update(i<<1|1,l,r); 49     } 50     else 51     { 52         update(i<<1,l,mid); 53         update(i<<1|1,mid+1,r); 54     } 55     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; 56 } 57  58 ll search1(int i,int l,int r) 59 { 60     if(tree[i].l==l&&tree[i].r==r) 61     { 62         return tree[i].sum; 63     } 64     int mid=(tree[i].l+tree[i].r)>>1; 65     if(r<=mid) 66     { 67         return search1(i<<1,l,r); 68     } 69     else if(l>mid) 70     { 71         return search1(i<<1|1,l,r); 72     } 73     else 74     { 75         return search1(i<<1,l,mid)+search1(i<<1|1,mid+1,r); 76     } 77 } 78  79  80 int main() 81 { 82     int cas=1; 83     while(scanf("%d",&n)!=EOF) 84     { 85         for(int i=1; i<=n; i++) 86         { 87             scanf("%I64d",&a[i]); 88         } 89         build(1,1,n); 90         scanf("%d",&m); 91         printf("Case #%d:\n",cas); 92         cas++; 93         for(int i=1; i<=m; i++) 94         { 95             scanf("%d%d%d",&op,&x,&y); 96             if(x>y) swap(x,y); 97             if(op==0) 98             { 99                 update(1,x,y);100             }101             else if(op==1)102             {103                 printf("%I64d\n",search1(1,x,y));104             }105         }106         printf("\n");107     }108     return 0;109 }
View Code

 


联系
我们