洛谷花神游历各国2 线段树-白红宇的个人博客

洛谷花神游历各国2 线段树

发布日期：2021-09-25 23:57:42 浏览次数：5 分类：技术文章

本文共 2224 字，大约阅读时间需要 7 分钟。

上帝造题的七分钟2 / 花神游历各国

题目描述

"第一分钟，X说，要有数列，于是便给定了一个正整数数列。

第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。

第三分钟，k说，要能查询，于是便有了求一段数的和的操作。

第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。

第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。

第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。"

——《上帝造题的七分钟·第二部》

所以这个神圣的任务就交给你了。

输入格式

第一行一个整数nn，代表数列中数的个数。

第二行nn个正整数，表示初始状态下数列中的数。

第三行一个整数mm，表示有mm次操作。

接下来mm行每行三个整数k,l,r，

k=0表示给[l,r][l,r]中的每个数开平方(下取整)

k=1表示询问[l,r][l,r]中各个数的和。

数据中有可能l>rl>r，所以遇到这种情况请交换l和r。

输出格式

对于询问操作，每行输出一个回答。

输入输出样例

输入 #1复制

1 2 3 4 5 6 7 8 9 10

0 1 10

1 1 10

1 1 5

0 5 8

1 4 8

输出 #1复制

说明/提示

对于30%的数据，1\le n,m\le 10001≤n,m≤1000，数列中的数不超过3276732767。

对于100%的数据，1 \le n,m \le 1000001≤n,m≤100000，1 \le l,r \le n1≤l,r≤n，数列中的数大于00，且不超过10^{12}10 12。

注意l有可能大于r，遇到这种情况请交换l,r。

这个题暴力能过是我没想到的，我还以为要什么高级的结构来实现区间开平方。

因为1e18开6次方就能到1，所以对于一个数，最多能开6次方。

(1)当区间最大值是1的时候，直接返回。

(2)当区间最大值大于1的时候，直接暴力递归就行了，因为每个叶结点最多遍历6次。

所以用线段树不仅需要维护区间和，还需要维护区间最大值。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;LL a[N];struct Node{ int l,r; LL mx,sum;}tr[N<<2];void push(int u){ tr[u].mx=max(tr[L].mx,tr[R].mx); tr[u].sum=tr[L].sum+tr[R].sum;}void build(int u,int l,int r){ tr[u]={ l,r,0,0}; if(l==r) { tr[u].mx=tr[u].sum=a[l]; return; } build(L,l,mid),build(R,mid+1,r); push(u);}void modify(int u,int l,int r){ if(tr[u].l==tr[u].r) { tr[u].mx=sqrt(tr[u].mx); tr[u].sum=sqrt(tr[u].sum); return; } if(tr[u].mx<=1) return; if(l<=mid) modify(L,l,r); if(r>mid) modify(R,l,r); push(u);}LL query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum; LL t=0; if(l<=mid) t+=query(L,l,r); if(r>mid) t+=query(R,l,r); return t;}int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); cin>>m; while(m--) { int op,l,r; cin>>op>>l>>r; if(l>r) swap(l,r); if(op==0) modify(1,l,r); else printf("%lld\n",query(1,l,r)); } return 0;}/**/

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105920797 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：upc 小y的序列

下一篇：upc 要塞任务数论

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章