HDU 4027 Can you answer these queries?

发表于 | 分类于 ，

题意：给N个数，进行两种操作：1.0 X Y对第X和第Y个数之间的数开根号；2.1 X Y对
第X和第Y个数之间的数求和。

开根号操作需要对区间内的每个数进行，才能使得区间的和得到更新。
没有想到的地方在于，\(2^{64}\)恰好需要开7次根号变为1，一个小于\(2^{63}\)的数最多开6次根号会变为1（如果最初的数>0)，之后再开根号数值不会变化。

因此，可以得到的解法是，更新操作更新到叶结点，并记录线段树结点开根号的次数，如果次数>=6，则不再向下更新。也就是说，开始的时候每次更新都会更新到叶结点，复杂度为\(O(n)\)，对整个区间更新6次后，复杂度变为\(O(logn)\).interesting…

坑：1.输入的Ei要用long long存，看题目描述integers Ei，默认就用了int…
2.T X Y操作，X可能大于Y，题目描述的是between X-th and Y-th😄

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 100000 + 10;
const int ST_SIZE = 1 << 18;
const int MAX_SQRT = 6;

int N, M;
ll E[MAX_N];
ll dat[ST_SIZE];
int tag[ST_SIZE];

void build(int k, int l, int r) {
  if (l == r - 1) {
    dat[k] = E[l];
  } else {
    int lc = 2 * k + 1, rc = 2 * k + 2;
    int m = (l + r) / 2;
    build(lc, l, m);
    build(rc, m, r);
    dat[k] = dat[lc] + dat[rc];
  }
  tag[k] = 0;
}

void update(int k, int l, int r, int a, int b) {
  if (b <= l || r <= a) {
    return;
  } else {
    // don't go down
    if (tag[k] >= MAX_SQRT) return;
    if (a <= l && r <= b) tag[k]++;
    if (l == r - 1) {
      dat[k] = (ll) sqrt(dat[k]);
    } else {
      // go down
      int lc = 2 * k + 1, rc = 2 * k + 2;
      int m = (l + r) / 2;
      update(lc, l, m, a, b);
      update(rc, m, r, a, b);
      dat[k] = dat[lc] + dat[rc];
    }
  }
}

ll query(int k, int l, int r, int a, int b) {
  if (b <= l || r <= a) {
    return 0;
  } else if (a <= l && r <= b) {
    return dat[k];
  } else {
    int lc = 2 * k + 1, rc = 2 * k + 2;
    int m = (l + r) / 2;
    return query(lc, l, m, a, b) + query(rc, m, r, a, b);
  }
}

int main() {
  int c = 1;
  while (scanf("%d", &N) != EOF) {
    printf("Case #%d:\n", c++);
    for (int i = 0; i < N; i++)
      scanf("%lld", E + i);
    build(0, 0, N);
    scanf("%d", &M);
    for (int i = 0; i < M; i++) {
      int T, X, Y;
      scanf("%d %d %d", &T, &X, &Y);
      if (X > Y) swap(X, Y);
      if (T == 0) {
        update(0, 0, N, X - 1, Y);
      } else {
        printf("%lld\n", query(0, 0, N, X - 1, Y));
      }
    }
    printf("\n");
  }
  return 0;
}