花神游历各国

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1712 字
n个数，x=1询问区间[l,r]的和；x=2
一本通
练习
正文

/*
原题：一本通 4.3 练习 2 花神游历各国 (BZOJ 3211)
题意：n 个数，x=1 询问区间 [l,r] 的和；x=2 把区间 [l,r] 每个数开平方并下取整。
思路：线段树维护区间和与区间最大值；开平方下传时若区间最大值<=1 则跳过（开根不变），否则递归到叶子。
复杂度：时间 O((n+m) log n * 开根次数)，空间 O(n)；每个数最多开根约 6 次。
易错点：0/1 开根不变需剪枝否则 TLE；区间和用 long long；sqrt 用整型下取整。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll a[N];
ll sum[N*4];
ll mx[N*4];
void pushup(int node){
    sum[node]=sum[node*2]+sum[node*2+1];
    mx[node]=max(mx[node*2],mx[node*2+1]);
}
void build(int node,int l,int r){
    if(l==r){
        sum[node]=mx[node]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    pushup(node);
}
void update(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr&&mx[node]<=1){
        return;
    }
    if(l==r){
        mx[node]=(ll)sqrt((long double)mx[node]);
        sum[node]=mx[node];
        return;
    }
    int mid=(l+r)/2;
    if(ql<=mid){
        update(node*2,l,mid,ql,qr);
    }
    if(qr>mid){
        update(node*2+1,mid+1,r,ql,qr);
    }
    pushup(node);
}
ll query(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sum[node];
    }
    int mid=(l+r)/2;
    ll res=0;
    if(ql<=mid){
        res+=query(node*2,l,mid,ql,qr);
    }
    if(qr>mid){
        res+=query(node*2+1,mid+1,r,ql,qr);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    int m;
    cin>>m;
    while(m--){
        int x,l,r;
        cin>>x>>l>>r;
        if(x==1){
            cout<<query(1,1,n,l,r)<<"\n";
        }else{
            update(1,1,n,l,r);
        }
    }
    return 0;
}
花神游历各国

正文

一本通·提高篇的其它内容
