首页 > 其他 > 详细

BZOJ3211 花神游历各国

时间:2018-09-26 23:14:13      阅读:156      评论:0      收藏:0      [点我收藏+]

题目蓝链

Solution

由于每一个数最多被开根\(5\)次就会为\(1\),所以我们可以用一个并查集维护下一个大于\(1\)的数的位置。然后再用树状数组维护一下区间和,每次修改直接暴力改就行了,修改的时候在树状数组上更新一下

时间复杂度\(\mathcal{O}(n\ log\ log\ val + m\ logn)\)

Code

#include <bits/stdc++.h>

using namespace std;

#define squ(x) ((LL)(x) * (x))
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef pair<int, int> pii;

inline int read() {
    int sum = 0, fg = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == ‘-‘) fg = -1;
    for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
    return fg * sum;
}

const int maxn = 1e5 + 10;

int to[maxn];
int find(int x) { return x == to[x] ? x : to[x] = find(to[x]); }

int n, m, a[maxn];

namespace BIT {
    LL A[maxn];
    int lowbit(int x) { return x & (-x); }
    void change(int x, int v) { for (int i = x; i <= n; i += lowbit(i)) A[i] += v; }
    LL sum(int x) { LL res = 0; for (int i = x; i; i -= lowbit(i)) res += A[i]; return res; }
    LL query(int l, int r) { return sum(r) - sum(l - 1); }
}

int main() {
#ifdef xunzhen
    freopen("path.in", "r", stdin);
    freopen("path.out", "w", stdout);
#endif

    n = read();
    for (int i = 1; i <= n + 1; i++) to[i] = i;
    for (int i = 1; i <= n; i++) BIT :: change(i, a[i] = read());

    m = read();
    while (m--) {
        int op = read();
        if (op == 1) {
            int l = read(), r = read();
            printf("%lld\n", BIT :: query(l, r));
        }else {
            int l = read(), r = read();
            for (int i = find(l); i <= r; i = (i == find(i) ? i + 1 : to[i])) {
                int tmp = sqrt(a[i]);
                BIT :: change(i, tmp - a[i]);
                a[i] = tmp;
                to[i] = a[i] > 1 ? i : i + 1;
            }
        }
    }

    return 0;
}

Summary

区间开根板子题,练练板子

我在做这道题的时候,发现了一个很神奇的东西,那就是三目运算符的常数竟然是\(if\)的五分之一!

BZOJ3211 花神游历各国

原文:https://www.cnblogs.com/xunzhen/p/9710532.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!