这题也真是的……

其实也不难，开多了就成1了，成1了再怎么开也是1……所以暴力单点修改+配合标记乱搞搞就行了

代码：

/**************************************************************
    Problem: 3038
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1168 ms
    Memory:5104 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=100001,maxnode=maxn*4;
unsigned long long sumv[maxnode];
bool lazy[maxnode];
unsigned long long A[maxn];
void build_tree(int o,int L,int R){
    if(L==R){
        sumv[o]=A[L];
        if(sumv[o]==1)
            lazy[o]=true;
    }else{
        int M=L+(R-L)/2,lc=o*2,rc=o*2+1;
        build_tree(lc,L,M);
        build_tree(rc,M+1,R);
        sumv[o]=sumv[lc]+sumv[rc];
        lazy[o]=lazy[lc]&&lazy[rc];
    }
}
int ql,qr;
void update(int o,int L,int R){
    if(L==R){
        sumv[o]=(unsigned long long)floor(sqrt(sumv[o]));
        if(sumv[o]==1)
            lazy[o]=true;
    }else{
        int M=L+(R-L)/2,lc=o*2,rc=o*2+1;
        if(ql<=M && !lazy[lc])
            update(lc,L,M);
        if(qr>M && !lazy[rc])
            update(rc,M+1,R);
        lazy[o]=lazy[lc]&&lazy[rc];
        sumv[o]=sumv[lc]+sumv[rc];
    }
}
unsigned long long query(int o,int L,int R){
    if(ql<=L && R<=qr){
        return sumv[o];
    }else{
        int M=L+(R-L)/2;
        unsigned long long ans=0;
        if(ql<=M)
            ans+=query(o*2,L,M);
        if(qr>M)
            ans+=query(o*2+1,M+1,R);
        return ans;
    }
}
int main(){
    int n,m,op;
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%llu",&A[i]);
    build_tree(1,1,n);
    scanf("%d",&m);
    while(m--){
        scanf("%d%d%d",&op,&ql,&qr);
        if(ql>qr)
            swap(ql,qr);
        if(op){
            printf("%llu\n",query(1,1,n));
        }else{
            update(1,1,n);
        }
    }
    return 0;
}

• 相关文章
• 全局相关文章