[BZOJ3211&3038][上帝造题的七分钟2&花神游历各国][线段树]

[BZOJ3211&3038][上帝造题的七分钟2&花神游历各国][线段树]

题目大意：

给定一棵线段树，要求支持区间开根和区间查询。

思路：

直接上线段树暴力修改就好咯，至于为什么，因为每个节点修改的次数是有限的，一个数开根多次后肯定会变成1，然后再执行开根操作的时候就直接跳过就好了（1的根号向下取整还是1）。

坑：

花神游历各国可能会出现0

代码：

BZOJ3211:

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 200100;
typedef long long ll;

ll num[Maxn << 2], mm[Maxn << 2];
ll n, m;

const ll Max(const ll &a, const ll &b) {
    return a > b ? a : b;
}
inline void read(ll &x) {
    x = 0; static char c;
    for (; !(c >= '0' && c <= '9'); c = getchar());
    for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = getchar());
}

inline void build(ll o, ll l, ll r) {
    if (l == r) {
        read(num[o]);
        mm[o] = num[o];
        return ;
    }
    ll mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    num[o] = num[o << 1] + num[o << 1 | 1];
    mm[o] = Max(mm[o << 1], mm[o << 1 | 1]);
}
inline void cover(ll o, ll l, ll r, ll L, ll R) {
    if (mm[o] <= 1) return;
    if (l == r && l >= L && r <= R) {
        num[o] = sqrt(num[o] * 1.0); 
        mm[o] = num[o];
        return; 
    }
    ll mid = (l + r) >> 1;
    if (L <= mid) cover(o << 1, l, mid, L, R);
    if (mid < R) cover(o << 1 | 1, mid + 1, r, L, R);
    num[o] = num[o << 1] + num[o << 1 | 1];
    mm[o] = Max(mm[o << 1], mm[o << 1 | 1]);
}
inline ll query(ll o, ll l, ll r, ll L, ll R) {
    if (l >= L && r <= R) {
        return num[o];
    }
    ll mid = (l + r) >> 1;
    ll ret = 0;
    if (L <= mid) ret = ret + query(o << 1, l, mid, L, R);
    if (mid < R) ret = ret + query(o << 1 | 1, mid + 1, r, L, R);
    return ret;
}
int main(void) {
    //freopen("in.txt", "r", stdin);
    read(n);

    // prllf("Case #%d:\n", ++group);
        build(1, 1, n);

        read(m);
        ll x, a, b;
        while(m--) {
            read(x); read(a), read(b);
            if (a > b) swap(a, b);
            if (x == 1) {
                printf("%lld\n", query(1, 1, n, a, b));
            } else {
                cover(1, 1, n, a, b);
            }
        }
        //putchar('\n');
    return 0;
}

BZOJ3038:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int Maxn = 200100;
typedef unsigned long long ulld;

struct Int {
    ulld a[5];
    Int(void) {
        memset(a, 0, sizeof(a));
    }
    Int operator + (Int b) const {
        Int ret;
        for (int i = 0; i < 5; i++) {
            ret.a[i] += a[i] + b.a[i];
            ret.a[i + 1] += ret.a[i] / 100000000000;
            ret.a[i] %= 100000000000;
        }
        return ret;
    }
    bool same(ulld num) {
        if (a[1] || a[2] || a[3] || a[4]) return false;
        return a[0] == num;
    }
    void value(ulld x) {
        a[1] = a[2] = a[3] = a[4] = 0;
        a[0] = x;
    }
    ulld show(void) {
        return a[0] + a[1] * 100;
    }
    void out(void) {
        if (!(a[1] || a[2] || a[3] || a[4] || a[0])) {
            putchar('0');
            return;
        }
        bool output = false;
        for (int i = 4; i >= 0; i--) {
            if (a[i]) {
                if (output) {
                    int size = 11 - log10(a[i]);
                    for (int i = 1; i <= size; i++) putchar('0');
                }
                printf ("%llu", a[i]);
                output = true;
            }
            else if (output) printf("00000000000");
        }
    }
};


Int num[Maxn << 2];
int n;
ulld m;

inline void read(ulld &x) {
    x = 0; static char c;
    for (; !(c >= '0' && c <= '9'); c = getchar());
    for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = getchar());
}

//inline void read(ulld &x) {
// scanf("%llu", &x);
//}
inline void build(int o, int l, int r) {
    if (l == r) {
        ulld tmp;
        read(tmp); num[o].value(tmp);
        return ;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    num[o] = num[o << 1] + num[o << 1 | 1];
}
inline void cover(int o, int l, int r, int L, int R) {
    if (num[o] .same((ulld)(r - l + 1))) return;
    if (l == r && l >= L && r <= R) {
        num[o].value((ulld) sqrt(num[o].show() * 1.0)); 
        return; 
    }
    int mid = (l + r) >> 1;
    if (L <= mid) cover(o << 1, l, mid, L, R);
    if (mid < R) cover(o << 1 | 1, mid + 1, r, L, R);
    num[o] = num[o << 1] + num[o << 1 | 1];
}
inline Int query(int o, int l, int r, int L, int R) {
    if (l >= L && r <= R) {
        return num[o];
    }
    int mid = (l + r) >> 1;
    Int ret;
    if (L <= mid) ret = ret + query(o << 1, l, mid, L, R);
    if (mid < R) ret = ret + query(o << 1 | 1, mid + 1, r, L, R);
    return ret;
}
int main(void) {
    int group = 0;
    scanf("%d", &n);

    // printf("Case #%d:\n", ++group);
        build(1, 1, n);

        read(m); int i;
        ulld x, a, b;
        while(m--) {
            read(x); read(a), read(b);
            if (a > b) swap(a, b);
            if (x) {
                Int ret = query(1, 1, n, a, b);
                ret.out(); putchar('\n');
            } else {
                cover(1, 1, n, a, b);
            }
        }
        //putchar('\n');
    return 0;
}

完。

By g1n0st