这题和3038几乎一样啊……

但是注意有的喜欢度可能为0，这种情况不处理的话时间效率duangduangduang……

代码：

/**************************************************************
    Problem: 3211
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1432 ms
    Memory:5108 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <cctype>
#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 || sumv[o]==0)
            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 || sumv[o]==0)
            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;
    }
}
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[20];
inline void writeint(unsigned long long x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
    register int n,m,op;
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        A[i]=readint();
    build_tree(1,1,n);
    m=readint();
    while(m--){
        op=readint();
        ql=readint();
        qr=readint();
        if(ql>qr)
            swap(ql,qr);
        if(1&op){
            writeint(query(1,1,n));
            putchar('\n');
        }else{
            update(1,1,n);
        }
    }
    return 0;
}

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