SP2713 GSS4 - Can you answer these queries IV
题目大意
\(n\)个数，和在\(10^18\)范围内，两种操作:区间开方下取整，查询区间和。
思路
区间开方，其实也是区间修改，只是每个元素修改不一样，还要查询区间和，基本可以确定是线段树。做线段树，我们首先要知道两点（其实也就两点）:
①维护什么信息；②如何合并（update）。
既然是查询区间和，肯定是要维护区间和的，难点在于区间开方。
我们从暴力的思路入手，即对于区间的每个元素一个一个的开方，是会T掉的。为什么会T掉呢？因为我们是单点修改，想要加速，就得区间一起修改，但是每个元素的值不一样，不能一起开方，什么时候可以一起开方呢？开方之后值不变，也就是该区间的元素值只能是0或1，这样就可以区间修改了，那我们就看看一个数最坏什么时候变成0或1，\(10^18\)方的话，最多也就30次。
并且和在\(10^18\)范围内，单点修改的情况也就那么多，于是等某个区间全为1或0时，直接返回就可了，反正开方结果也不变，不然就单点开方。
时间复杂度：emm...这个蒟蒻不会算。\(O(能过)\)。
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
inline long long read(){
long long w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
struct tree{
int l;
int r;
long long sum;
bool mark;
}t[400005];
int n,m,tot;
long long a[100005];
void build(int root,int l,int r){
t[root].l=l,t[root].r=r;
if(l==r){
t[root].sum=a[l];
if(a[l]==1||a[l]==0){
t[root].mark=1;
}else{
t[root].mark=0;
}
return;
}
int mid=(l+r)/2;
build(root*2,l,mid);
build(root*2+1,mid+1,r);
t[root].sum=t[root*2].sum+t[root*2+1].sum;
if(t[root*2].mark==1&&t[root*2+1].mark==1){
t[root].mark=1;
}else{
t[root].mark=0;
}
}
void change(int root,int l,int r){
if(t[root].l>=l&&t[root].r<=r&&t[root].mark==1){
return;
}
if(t[root].l==t[root].r){
t[root].sum=sqrt(t[root].sum);
if(t[root].sum==1||t[root].sum==0){
t[root].mark=1;
}else{
t[root].mark=0;
}
return;
}
int mid=(t[root].l+t[root].r)/2;
if(l<=mid){
change(root*2,l,r);
}
if(r>mid){
change(root*2+1,l,r);
}
t[root].sum=t[root*2].sum+t[root*2+1].sum;
if(t[root*2].mark==1&&t[root*2+1].mark==1){
t[root].mark=1;
}else{
t[root].mark=0;
}
}
long long ask(int root,int l,int r){
if(t[root].l>=l&&t[root].r<=r){
return t[root].sum;
}
int mid=(t[root].l+t[root].r)/2;
long long ans=0;
if(l<=mid){
ans+=ask(root*2,l,r);
}
if(r>mid){
ans+=ask(root*2+1,l,r);
}
return ans;
}
int main(){
while(scanf("%d",&n)!=EOF){
tot++;
for(int i=1;i<=n;i++){
a[i]=read();
}
build(1,1,n);
printf("Case #%d:\n",tot);
m=read();
for(int i=1;i<=m;i++){
int c,l,r;
c=read(),l=read(),r=read();
if(l>r){
swap(l,r);
}
if(c==0){
change(1,l,r);
}else{
printf("%lld\n",ask(1,l,r));
}
}
}
return 0;
}