M_sea

洛谷4145 上帝造题的七分钟2 / 花神游历各国
Luogu算法题意即维护一个数列,支持区间开平方(取下整)和区间求和。容易发现,对于最大的数据$10^{12}$,...
扫描右侧二维码阅读全文
20
2018/08

洛谷4145 上帝造题的七分钟2 / 花神游历各国

Luogu

算法

题意即维护一个数列,支持区间开平方(取下整)和区间求和。

容易发现,对于最大的数据$10^{12}$,开6次方即可得到1,之后再开方就不会变。

那么对于线段树的每个节点维护一个f,表示该节点对应的区间是否全为1或0。

修改时如果修改到一个$f=1$的区间,则不用修改;否则暴力修改每个叶节点。

注意可能有$l>r$的情况,要交换$l$和$r$。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
typedef int mainint;
#define int long long
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100010;

struct Segment_Tree {
    int s[MAXN<<2];
    bool f[MAXN<<2];
#define lson (o<<1)
#define rson (o<<1|1)
    inline void pushup(int o) {
        s[o]=s[lson]+s[rson];
        f[o]=f[lson]&f[rson];
    }
    inline void build(int o,int l,int r) {
        if (l==r) { s[o]=read(); return; }
        int mid=(l+r)>>1;
        build(lson,l,mid);
        build(rson,mid+1,r);
        pushup(o);
    }
    inline void update(int o,int l,int r,int ql,int qr) {
        if (f[o]) return;
        if (l==r) {
            s[o]=floor(sqrt(s[o]));
            if (s[o]<=1) f[o]=1;
            return;
        }
        int mid=(l+r)>>1;
        if (ql<=mid) update(lson,l,mid,ql,qr);
        if (qr>mid) update(rson,mid+1,r,ql,qr);
        pushup(o);
    }
    inline int query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return s[o];
        int mid=(l+r)>>1,rt=0;
        if (ql<=mid) rt+=query(lson,l,mid,ql,qr);
        if (qr>mid) rt+=query(rson,mid+1,r,ql,qr);
        return rt;
    }
#undef lson
#undef rson
};

Segment_Tree Dalao;

mainint main() {
    int n=read(); Dalao.build(1,1,n);
    int m=read();
    while (m--) {
        int x=read(),a=read(),b=read();
        if (a>b) swap(a,b);
        if (x==1) printf("%lld\n",Dalao.query(1,1,n,a,b));
        else if (x==0) Dalao.update(1,1,n,a,b);
    }
    return 0;
}
最后修改:2018 年 12 月 01 日 08 : 16 PM

发表评论