[bzoj 3211] 화신 이 각국 을 여행 하 다

Description
데이터 구 조 를 작성 하 세 요.n<=10^5,m<=2*10^5,ai<=10^9
Solution
구간 제곱?폭력 이지.어차피 10 ^ 9 도 몇 번 운전 할 필요 가 없 으 니 상수 가 좀 클 뿐 이 야.선분 트 리 로 구간 과 구간 표 시 를 유지 하여 이 구간 에 개방 할 수 있 는 수 (1 & 0) 가 있 는 지 를 나타 낸다.물론 트 리 배열 로 유지 하고 재 활용 하 며 집합 을 찾 아 표 시 를 하 는 것 도 가능 하 며 상수 가 더 작다.그런데 왜 0 을 표시 해 야 하 느 냐 는 질문 이 있 습 니 다. 그렇지 않 으 면 비참 하 게 시간 을 초과 할 수 있 습 니 다.오묘 하 다
Code

#include
#include
#include
#include 
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 100005
using namespace std;
typedef long long ll;
struct note{ll v;bool bz;}t[N*3];
int n,m,z,x,y,a[N];
void back(int v,int x) {
    t[v].v=x;if (x==1||x==0) t[v].bz=1;
}
note merge(note y,note z) {
    note x;x.v=y.v+z.v;x.bz=y.bz&&z.bz;return x;
}
void build(int v,int l,int r) {
    if (l==r) {
        back(v,a[l]);
        return;
    }
    int m=(l+r)/2;
    build(v*2,l,m);build(v*2+1,m+1,r);
    t[v]=merge(t[v*2],t[v*2+1]);
}
void revise(int v,int l,int r) {
    if (t[v].bz) return;
    if (l==r) {
        a[l]=sqrt(a[l]);
        back(v,a[l]);
        return;
    }
    int m=(l+r)/2;
    revise(v*2,l,m);revise(v*2+1,m+1,r);
    t[v]=merge(t[v*2],t[v*2+1]);
}
void change(int v,int l,int r,int x,int y) {
    if (t[v].bz) return;
    if (l==x&&r==y) {revise(v,l,r);return;}
    int m=(l+r)/2;
    if (y<=m) change(v*2,l,m,x,y);
    else if (x>m) change(v*2+1,m+1,r,x,y);
    else change(v*2,l,m,x,m),change(v*2+1,m+1,r,m+1,y);
    t[v]=merge(t[v*2],t[v*2+1]);
}
ll find(int v,int l,int r,int x,int y) {
    if (l==x&&r==y) return t[v].v;
    int m=(l+r)/2;
    if (y<=m) return find(v*2,l,m,x,y);
    else if (x>m) return find(v*2+1,m+1,r,x,y);
    else return find(v*2,l,m,x,m)+find(v*2+1,m+1,r,m+1,y);
}
int main() {
    scanf("%d",&n);
    fo(i,1,n) scanf("%d",&a[i]);
    build(1,1,n);
    for(scanf("%d",&m);m;m--) {
        scanf("%d%d%d",&z,&x,&y);
        if (z==1) printf("%lld
",find(1,1,n,x,y));
        else change(1,1,n,x,y);
    }
}