SP2713 GSS4

这是一道假题，表面上看起来，好像使用了什么奇妙的操作，其实就是一个无脑暴力

我们会发现，即使是\(1e18\)，在开方\(6\)次之后也已经变成了\(1\)，而\(1\)再怎么开方还是\(1\)，也就是说，每个数最多被修改\(6\)次，那么我们记录区间内是否都是\(1\)，如果都是\(1\)则无需修改，然后对于需要修改的区间，我们直接暴力修改到底即可，这样复杂度就是\(O(n \lg n)\)常数在6左右，完全不用担心

下面放代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#include<cmath>

#define ll long long

#define gc getchar

#define maxn 100005

using namespace std;

inline ll read(){

    ll a=0;int f=0;char p=gc();

    while(!isdigit(p)){f|=p=='-';p=gc();}

    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

    return f?-a:a;

}int T,n,m;

struct ahaha{

    ll v,v1;

}t[maxn<<2];

#define lc p<<1

#define rc p<<1|1

inline void pushup(int p){

    t[p].v=t[lc].v+t[rc].v;

    t[p].v1=max(t[lc].v1,t[rc].v1);

}

void build(int p,int l,int r){

    if(l==r){t[p].v=t[p].v1=read();return;}

    int m=l+r>>1;

    build(lc,l,m);build(rc,m+1,r);

    pushup(p);

}

void update(int p,int l,int r,int L,int R){

    if(l>R||r<L)return;

    if(t[p].v1==1)return;

    if(l==r){t[p].v=t[p].v1=sqrt(t[p].v1);return;}

    int m=l+r>>1;

    update(lc,l,m,L,R);update(rc,m+1,r,L,R);

    pushup(p);

}

ll query(int p,int l,int r,int L,int R){

    if(l>R||r<L)return 0;

    if(L<=l&&r<=R)return t[p].v;

    int m=l+r>>1;

    return query(lc,l,m,L,R)+query(rc,m+1,r,L,R);

}

inline void solve_1(){

    int x=read(),y=read();if(x>y)swap(x,y);

    update(1,1,n,x,y);

}

inline void solve_2(){

    int x=read(),y=read();if(x>y)swap(x,y);

    printf("%lld\n",query(1,1,n,x,y));

}

int main(){

    while(~scanf("%d",&n)){

        printf("Case #%d:\n",++T);

        build(1,1,n);

        m=read();

        while(m--){

            int zz=read();

            switch(zz){

                case 0:solve_1();break;

                case 1:solve_2();break;

            }

        }

        puts("");

    }

    return 0;

}

巴特西

SP2713 GSS4

最新文章

热门文章