首页 > 代码库 > HDU 4027 Can you answer these queries?（线段树的单点更新+区间查询）

HDU 4027 Can you answer these queries?（线段树的单点更新+区间查询）

2024-07-16 06:17:58   224人阅读

题目链接

题意 ： 给你N个数，进行M次操作，0操作是将区间内的每一个数变成自己的平方根（整数），1操作是求区间和。

思路 ：单点更新，区间查询，就是要注意在更新的时候要优化，要不然会超时，因为所有的数开几次方之后都会变成1，所以到了1不用没完没了的更新。

 1 //HDU 4027 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <iostream> 6 #define LL __int64 7 using namespace std ; 8  9 LL p[100010 * 4],lz[100010 * 4] ;10 void pushup(int rt)11 {12     p[rt] = p[rt << 1] + p[rt << 1 | 1] ;13 }14 //void pushdown(int rt,int m)15 //{16 //    if(lz[rt])17 //    {18 //        lz[rt << 1] = lz[rt << 1 | 1] = lz[rt] ;19 //        p[rt << 1] = (m - m/2) * lz[rt] ;20 //        p[rt << 1|1] = m/2 * lz[rt] ;21 //        lz[rt] = 0 ;22 //    }23 //}24 void build(int l,int r,int rt)25 {26     lz[rt] = 0 ;27     LL a ;28     if(l == r)29     {30         scanf("%I64d",&a) ;31         p[rt] = a ;32         return ;33     }34     int mid = (l+r) >> 1 ;35     build(l,mid,rt << 1) ;36     build(mid+1,r,rt << 1 | 1) ;37     pushup(rt) ;38 }39 void update(int L,int R ,int l,int r,int rt)40 {41     if(p[rt] == r-l+1)42         return ;43     if(l == r)44     {45         p[rt] = sqrt(p[rt]*1.0) ;46         return ;47     }48     //pushdown(rt,r-l+1) ;49     int mid = (l+r) >> 1 ;50     if(mid >= L)51         update(L,R,l,mid,rt << 1) ;52     if(R > mid)53         update(L,R,mid+1,r,rt << 1 | 1) ;54     pushup(rt) ;55 }56 LL query(int L,int R,int l,int r,int rt)57 {58     LL sum = 0 ;59     if(l >= L && R >= r)60         return p[rt] ;61     //pushdown(rt,r-l+1) ;62     int mid = (l+r) >> 1 ;63     if(mid >= L)64         sum += query(L,R,l,mid,rt << 1) ;65     if(mid < R)66         sum += query(L,R,mid+1,r,rt << 1 | 1) ;67     return sum ;68 }69 int main()70 {71     int N,M,x,y,z ,casee = 1;72     while(cin >> N)73     {74         build(1,N,1) ;75         scanf("%d",&M) ;76         printf("Case #%d:\n",casee++) ;77         while(M--)78         {79             scanf("%d %d %d",&x,&y,&z) ;80             if(y > z)81                 swap(y,z) ;82             if(x == 0)83             {84                 update(y,z,1,N,1) ;85             }86             else87             {88                 printf("%I64d\n",query(y,z,1,N,1) ) ;89             }90         }91         puts("") ;92     }93     return 0 ;94 }
View Code

 


联系
我们