洛谷P4145《上帝造题的七分钟2 / 花神游历各国》

十月 20, 2019 3632

你会支持区间开平方的数据结构吗？

题目背景

XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。

题目描述

“第一分钟，X说，要有数列，于是便给定了一个正整数数列。

第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。

第三分钟，k说，要能查询，于是便有了求一段数的和的操作。

第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。

第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。

第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”

——《上帝造题的七分钟·第二部》

所以这个神圣的任务就交给你了。

输入格式

第一行一个整数n，代表数列中数的个数。

第二行n个正整数，表示初始状态下数列中的数。

第三行一个整数m，表示有m次操作。

接下来m行每行三个整数k,l,r，

  • k=0表示给[l,r]中的每个数开平方(下取整)
  • k=1表示询问[l,r]中各个数的和。

数据中有可能l>r，所以遇到这种情况请交换l和r。

输出格式

对于询问操作，每行输出一个回答。

输入输出样例

输入 #1复制

1
2
3
4
5
6
7
8
10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

输出 #1

1
2
3
19
7
6

解析

我不会支持区间开方的数据结构。怎么办呢？

一个很容易发现的事实是题目给的所有数最多被开方6次（原题数据范围1e12）。为什么呢？

KMPKDH.png

懂了吧

所以开方操作直接暴力修改就好。每次修改之前查询一下这个块的最大值是不是1，是的话就不去开方这个区间了，这样跑的飞快

查询操作就是正常的不带 lazy tag 的查询函数

还有一个坑点就是 l 和 r 的大小关系，这个注意一下就好了

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//
// Created by HandwerSTD.
// Copyright (c) 2019 HandwerSTD. All rights reserved.
// Title: 上帝造题的七分钟2 / 花神游历各国
//
// sto Qingyu orz
// 感谢真神sqy无私的教诲。膜时队者处处阿克，只因大师sqy在他背后。不膜大师者违背了真神的旨意，真神必将降下天谴，
// 使其天天爆零
// 我不由自主地膜拜真神sqy。
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define down(a,t,s,i) for (int a = t; a >= s; a -= i)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

const int MAXN = 1e5 + 10;

int n, m;
lli osq[MAXN];

namespace SegmentTree {
#define lson (root << 1)
#define rson (root << 1 | 1)

    lli sum[MAXN << 2], max[MAXN << 2];

    void update(int root)
    { sum[root] = sum[lson] + sum[rson]; max[root] = std::max(max[lson], max[rson]); }
    void buildTree(int root = 1, int l = 1, int r = n) {
        if (l == r) return (void) (sum[root] = max[root] = osq[l]);
        int mid = (l + r) >> 1;
        buildTree(lson, l, mid); buildTree(rson, mid + 1, r);
        update(root);
    }
    void modify(int ll, int rr, int root = 1, int l = 1, int r = n) {
        if (l == r) {
            sum[root] = max[root] = sqrt(sum[root]);
            return;
        }
        int mid = (l + r) >> 1;
        if (ll <= mid && max[lson] > 1)
            modify(ll, rr, lson, l, mid);
        if (mid + 1 <= rr && max[rson] > 1)
            modify(ll, rr, rson, mid + 1, r);
        update(root);
    }
    lli querySum(int ll, int rr, int root = 1, int l = 1, int r = n) {
        if (ll <= l && r <= rr) return sum[root];
        lli rt = 0; int mid = (l + r) >> 1;
        if (ll <= mid) rt += querySum(ll, rr, lson, l, mid);
        if (mid + 1 <= rr) rt += querySum(ll, rr, rson, mid + 1, r);
        return rt;
    }
}

int main() {
    n = getint();
    rap (i, 1, n, 1) osq[i] = getll();
    SegmentTree::buildTree();
    m = getint();
    rap (i, 1, m, 1) {
        int cmd = getint();
        int l = getint(); int r = getint();
        if (l > r) std::swap(l, r);
        if (!cmd) SegmentTree::modify(l, r);
        else printf("%lld\n", SegmentTree::querySum(l, r));
    }
    return 0;
}