上帝造题的七分钟 2 / 花神游历各国

Problem Statement && Input

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

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

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

接下来 $m$ 行每行三个整数 k l r。

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

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

Output

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

Sample Input

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

Sample Output

Constraints

对于 $30%$ 的数据，$1\le n,m\le 10^3$，数列中的数不超过 $32767$。

对于 $100%$ 的数据，$1\le n,m\le 10^5$，$1\le l,r\le n$，数列中的数大于 $0$，且不超过 $10^{12}$。

Solving

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103


#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define Single
#define ls(p) (p << 1)       // 左子节点索引
#define rs(p) (p << 1 | 1)   // 右子节点索引
using namespace std;
const int N = 1e5+10;      // 最大数据规模
int n,m;
struct SegTree 
{
private:
    struct Node 
    {
        int l,r;   
        int sum,max;   
        Node() : l(0), r(0), sum(0), max(0) {}
    } tree[N << 2];
    vector<int> arr;

    void push_up(int p) 
    {
        tree[p].sum = tree[ls(p)].sum + tree[rs(p)].sum;
        tree[p].max = max(tree[ls(p)].max, tree[rs(p)].max);
    }

public:
    // Build Section
    SegTree(const vector<int>& _arr) : arr(_arr) 
    {
        build(1, 1, (int)arr.size()-1);//下标从1开始
      //build(1, 0, (int)arr.size()-1);//下标从0开始
    }
    void build(int p, int l, int r) 
    {
        tree[p].l = l;
        tree[p].r = r;
        if(l == r) 
        {
            tree[p].sum = tree[p].max = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(p), l, mid);
        build(rs(p), mid+1, r);
        push_up(p);
    }
    // 对区间开平方的操作无法根据懒更新去维护区间和与区间最大值，所以只能进行暴力下传到叶节点进行修改，但下传过程可以剪枝
    // 时间复杂度O(6 * N * log(N)) 6为数据最大值1e12所能开平方的最大次数，因为是暴力下传到叶节点，所以需乘上树的高度logN 
    void updateSqrt(int p, int ul, int ur) 
    {
        if (tree[p].l == tree[p].r) {
            arr[tree[p].l] = sqrt(arr[tree[p].l]);
            tree[p].sum = arr[tree[p].l];
            tree[p].max = arr[tree[p].l];
            return;
        }
        int mid = (tree[p].l + tree[p].r) >> 1;
        //剪枝：如果区间最大值已经为1，则此区间无需再进行开平方操作.
        if (ul <= mid && tree[ls(p)].max > 1)
         {
            updateSqrt(ls(p), ul, ur);
        }
        if (ur > mid && tree[rs(p)].max > 1) 
        {
            updateSqrt(rs(p), ul, ur);
        }
        push_up(p);
    }
    // Query Section
    int querySum(int p, int ql, int qr) 
    {
        if(ql <= tree[p].l && tree[p].r <= qr) return tree[p].sum;
        int mid = (tree[p].l + tree[p].r) >> 1, res = 0;
        if(ql <= mid) res += querySum(ls(p), ql, qr);
        if(qr > mid) res += querySum(rs(p), ql, qr);
        return res;
    }
};
void solve()
{
    int n;
    cin >> n;
    vector<int> arr(n+1);
    for(int i=1;i<=n;i++) cin >> arr[i];
    SegTree st(arr);
    int m;
    cin >> m;
    while(m--)
    {
        int op,l,r;
        cin >> op >> l >> r;
        if(l > r) swap(l,r);
        if(op==0)
        {
            st.updateSqrt(1,l,r);
        }
        else
        {
            cout << st.querySum(1,l,r) << endl;
        }
    }
}