BZOJ 3211 선분 트 리 구간 업데이트 구간 구 화

전송 문: 제목
제목:
하나의 서열 을 주 고 두 가지 조작 이 있 습 니 다.

구간 [l, r] 에 주 고 구간 의 모든 값 은 근호

를 엽 니 다.

검색 구간 [l, r] 의 sum

문제 풀이:
순수한 선분 트 리, 구간 업데이트, 구간 구 화, 템 플 릿 을 설치 하면 됩 니 다.그 다음 에 기술 이 있 습 니 다. 109 10 9 개 5 개 근호 가 1 입 니 다. 그래서 우 리 는 나 무 를 만 들 거나 갱신 할 때 값 ≤ ≤ 1 을 발 견 했 을 때 표 시 를 한 다음 에 업데이트 할 때 이미 표 시 된 점 을 만 났 습 니 다. 이 점 들 은 근호 가 다시 열 려 도 원래 의 값 임 을 설명 합 니 다. 그래서 우 리 는 표 시 된 점 들 을 직접 뛰 어 넘 으 면 됩 니 다.
갱 점:
cin, cout 를 사용 할 수 없습니다. 시간 을 초과 하지 않 으 면 안 됩 니 다.
AC 코드:

#include 
#include 
#include 
#include 
#include 
#define debug(x) cout<
#define INF 0x3f3f3f3f
using namespace std;

const int maxn = 1e5 + 10;
int a[maxn];
bool flag[maxn << 2];
/******************     **********************/
long long SegTree[maxn << 2];
void BuildTree(int l, int r, int rt) {//  ，lr    ,rt       1
    if (l == r) {
        SegTree[rt] = a[l];//      
        if (SegTree[rt] <= 1)
            flag[rt] = true;
        return ;
    }
    int m = (l + r) >> 1;
    BuildTree(l, m, rt << 1);
    BuildTree(m + 1, r, rt << 1 | 1);
    SegTree[rt] = SegTree[rt << 1] + SegTree[rt << 1 | 1];
    flag[rt] = flag[rt << 1] & flag[rt << 1 | 1];
}
long long Query(int L, int R, int l, int r, int rt) {//    ,LR     ,lr    ,rt       1
    if (l >= L && r <= R)
        return SegTree[rt];
    int m = (l + r) >> 1;
    long long ans = 0;
    if (L <= m)
        ans += Query(L, R, l, m, rt << 1);
    if (R > m)
        ans += Query(L, R, m + 1, r, rt << 1 | 1);
    return ans;
}
void Update(int L, int R, int l, int r, int rt) {
    if (flag[rt] == true)
        return;
    if (l == r) {
        SegTree[rt] = (long long)sqrt(SegTree[rt]);
        if (SegTree[rt] <= 1)
            flag[rt] = true;
        return;
    }
    int m = (l + r) >> 1;
    if (R <= m)
        Update(L, R, l, m, rt << 1);
    else if (L > m)
        Update(L, R, m + 1, r, rt << 1 | 1);
    else {
        Update(L, m, l, r, rt);
        Update(m + 1, R, l, r, rt);
    }
    SegTree[rt] = SegTree[rt << 1] + SegTree[rt << 1 | 1];
    flag[rt] = flag[rt << 1] & flag[rt << 1 | 1];
}
/******************     **********************/
int main(void) {
    int n, m, t1, t2, t3;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++)
        scanf("%d",&a[i]);
    BuildTree(1, n, 1);
    scanf("%d",&m);
    while (m--) {
        scanf("%d%d%d",&t1,&t2,&t3);
        if (t1 == 1)
            printf("%lld
",Query(t2, t3, 1, n, 1));
        else if (t1 == 2)
            Update(t2, t3, 1, n, 1);
    }
    return 0;
}