SPOJ

Luogu

算法

这题和花神游历各国那题是一样的,只不过改成了多组数据。

原题解

记得清空标记。

代码

#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;

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) { scanf("%lld",&s[o]); 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,m,T=0;
    while (scanf("%lld",&n)==1) {
        printf("Case #%lld:\n",++T);
        memset(Dalao.f,0,sizeof(Dalao.f));
        Dalao.build(1,1,n);
        scanf("%lld",&m);
        while (m--) {
            int x,a,b;
            scanf("%lld%lld%lld",&x,&a,&b);
            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);
        }
        putchar('\n');
    }
    return 0;
}

事实证明跑得非常快qwq

最后修改:2019 年 09 月 24 日 01 : 27 PM