UOJ #496.秋蝉鸣泣之时

奇怪的题目背景

所误入的 是回忆的教室

所响起的 是通向绝望的计时器

所到达的 是开始的结束

你能相信吗?
题目背景

最近礼奈酱学会了线段树和树状数组两种数据结构

由于礼奈酱上课听的很认真，所以她知道

树状数组常见的操作是 单点加区间求和

线段树常见的操作是 区间加区间求和

但她认为自己已经不是小学生了,觉得只能维护加法标记这件事简直太蠢了~

所以她将题目加强了一下，但她发现自己不会写这题的标程了

因为 rina酱非常可爱，所以你要帮她写这题的标程
题意描述

礼奈给了你一列数(n个)

要求支持以下两类操作共m次

    区间求和 [L,R]
    区间开平方[L,R]即将区间内每一个数Ai修改为 Ai??√Ai 向下取整

输入输出格式

第一行 n

第二行 m

第三行n个数 表示 Ai

接下来m行

每行三个数 op,L,R

op=1 为1操作

op=2 为2操作

对于每次1操作，请输出一行答案
样例输入

4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4

样例输出

101
11
11

数据范围

所有数据点保证

n,m≤2?10^6,Ai≤10^9

本题中可以使用树状数组或线段树,大体思想是当一个数开方到1时,后面无论怎样开方都还是1,相同的,0开方后也还是0。那么只要去处理有大于1的数的区间即可。
由于题目中的每一个元素,最多只会开方5次,所以这道题就不会超时了。(另:树状数组需要并查集来辅助,将每个数的父亲设为它右边第一个不小于1的数,每次更新时将它的父亲并到它右边的数的父亲上,这样并查集数组会有递推性,即可以通过这种手段不断递推找到右边第一个不小于1的数)。

Code:
//线段树
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=100005;
int n,m,a[N];
long long sum[N*4],mx[N*4];
void build(int k,int l,int r){
    if(l==r){
        sum[k]=a[l];
        mx[k]=sum[k];
        return ;
    }
    int mid=(l+r)>>1;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    sum[k]=sum[k*2]+sum[k*2+1];
    mx[k]=max(mx[k*2],mx[k*2+1]);
}

long long query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        return sum[k];
    }
    int mid=(l+r)>>1;
    long long res=0;
    if(x<=mid){
        res+=query(k*2,l,mid,x,y);
    }
    if(mid<y){
        res+=query(k*2+1,mid+1,r,x,y);
    }
    return res;
}
void update(int k,int l,int r,int x,int y){
    if(mx[k]<=1){
        return;
    }
    if(l==r){
        sum[k]=sqrt(sum[k]);
        mx[k]=sum[k];
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=x){
        update(k*2,l,mid,x,y);
    }
    if(mid<y){
        update(k*2+1,mid+1,r,x,y);
    }
    sum[k]=sum[k*2]+sum[k*2+1];
    mx[k]=max(mx[k*2],mx[k*2+1]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    scanf("%d",&m);
    while(m--){
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(l>r){
            swap(l,r);
        }
        if(opt==1){
            printf("%lld\n",query(1,1,n,l,r));
        }
        else if(opt==2){
            update(1,1,n,l,r);
        }
    }
    return 0;
}
//树状数组
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=100005;
int n,m,a[N],fa[N],opt,l,r;
long long c[N];
int find(int x){
    if(x==fa[x]){
        return x;
    }
    return fa[x]=find(fa[x]);
}
int lowbit(int x){
    return x&-x;
}
void update(int i,int val){
    while(i<=n){
        c[i]+=val;
        i+=lowbit(i);
    }
}
long long sum(int i){
    long long ans=0;
    while(i){
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        update(i,a[i]);
    }
    scanf("%d",&m);
    for(int i=1;i<=n;i++){
        if(a[i]<=1){
            fa[i]=i+1;
        }
        else{
            fa[i]=i;
        }
    }
    fa[n+1]=n+1;
    while(m--){
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1){
            printf("%lld\n",sum(r)-sum(l-1));
        }
        else if(opt==2){
            for(int i=l;i<=r;i=find(i+1)){
                int res=(int)sqrt(a[i]);
                update(i,res-a[i]);
                a[i]=res;
                if(a[i]<=1){
                    fa[i]=find(i+1);
                }
            }
        }
    }
    return 0;
}

UOJ #496.秋蝉鸣泣之时

原文：https://www.cnblogs.com/ukcxrtjr/p/11198492.html