P4145 上帝造题的七分钟 2 / 花神游历各国[线段树 区间开方(剪枝) + 区间求和]
P4145 上帝造题的七分钟 2 / 花神游历各国
时间限制: 1.00s 内存限制: 125.00MB
复制 Markdown
中文
退出 IDE 模式
题目背景
XLk 觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。
题目描述
“第一分钟，X 说，要有数列，于是便给定了一个正整数数列。
第二分钟，L 说，要能修改，于是便有了对一段数中每个数都开平方（下取整）的操作。
第三分钟，k 说，要能查询，于是便有了求一段数的和的操作。
第四分钟，彩虹喵说，要是 NOIP 难度，于是便有了数据范围。
第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。
第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过 64 位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。
输入格式
第一行一个整数 n，代表数列中数的个数。
第二行 n 个正整数，表示初始状态下数列中的数。
第三行一个整数 m，表示有 m 次操作。
接下来 m 行每行三个整数k l r。
k=0 表示给 [l,r] 中的每个数开平方（下取整）。
k=1 表示询问 [l,r] 中各个数的和。
数据中有可能 l>r，所以遇到这种情况请交换 l 和 r。
输出格式
对于询问操作，每行输出一个回答。
输入输出样例
输入 #1复制运行
10 1 2 3 4 5 6 7 8 9 10 5 0 1 10 1 1 10 1 1 5 0 5 8 1 4 8
输出 #1复制运行
19 7 6
说明/提示
对于 30% 的数据，1≤n,m≤103，数列中的数不超过 32767。
对于 100% 的数据，1≤n,m≤105，1≤l,r≤n，数列中的数大于 0，且不超过 1012。
显然对于0 和1 无论怎么开方都是自己 由于数据都是整数 所以如果一段区间的最大值是0 或1 那么取反后仍为自己 换句话说就是不用管 加上这一层剪枝会使效率提高 因为开方操作不能用懒标记实现
#include <bits/stdc++.h> using namespace std; const int N=1e5+5; #define int long long int a[N],n,m; struct SegmentTree{ int l,r,sum,maxn; #define l(x) tree[x].l #define r(x) tree[x].r #define sum(x) tree[x].sum #define maxn(x) tree[x].maxn }tree[N<<2]; void pushup(int p){ sum(p)=sum(p<<1)+sum(p<<1|1); maxn(p)=max(maxn(p<<1),maxn(p<<1|1)); } void build(int p,int l,int r){ l(p)=l,r(p)=r; if(l==r){ sum(p)=maxn(p)=a[l];return; } int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); pushup(p); } void change(int p,int l,int r){ if(l(p)==r(p)){ sum(p)=sqrt(sum(p)); maxn(p)=sqrt(maxn(p)); return; } int mid=(l(p)+r(p))>>1; if(l<=mid&&maxn(p<<1)>1)change(p<<1,l,r); if(r>mid&&maxn(p<<1|1)>1)change(p<<1|1,l,r); pushup(p); } int query(int p,int l,int r){ if(l<=l(p)&&r>=r(p)){ return sum(p); } int mid =(l(p)+r(p))>>1; int val=0; if(l<=mid)val+=query(p<<1,l,r); if(r>mid)val+=query(p<<1|1,l,r); return val; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.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){ change(1,l,r); }else cout<<query(1,l,r)<<'\n'; } return 0; }