Luogu

分析

题意即维护一个数列，支持区间开平方（取下整）和区间求和。

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

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

修改时如果修改到一个满足条件的区间，则不用修改；否则往下递归修改直到到达叶节点或者满足条件的节点。这样子复杂度是对的。

注意可能有 $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;
}