题面#

题目描述#

给定一个长为 $n$ 的数列 $a_1\dots a_n$ ，以及 $n$ 个操作，操作涉及区间开方，区间求和。

输入格式#

第一行输入一个数字 $n$ 。

第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$ ，以空格隔开。

接下来输入 $n$ 行询问，每行输入四个数字 $\rm{opt},l,r,c$ ，以空格隔开。

若 $\rm opt=0$ ，表示将位于 $\left[l, r\right]$ 的之间的数字都开方。对于区间中每个 $a_i\left(l\leq i\leq r\right)\longleftarrow \lfloor \sqrt a_i \rfloor$

若 $\rm opt=1$ ，表示询问位于 $\left[l, r\right]$ 的所有数字的和。

输出格式#

对于每次询问，输出一行一个数字表示答案。

样例（很水）#

Input

Output

数据范围与提示#

对于 $100\%$ 的数据， $1\leq n\leq 50000,-2^{31}\leq {\rm others}$ 、 ${\rm ans}\leq 2^{31}-1$ 。

写博客时的吐槽#

$\rm \LaTeX$ 是真nm难打啊。。

思路#

审题#

与平时最简单的数列分块入门的区别在于，这个数列分块入门五并不是加上or减去一个数，而是开方。这两者的区别在于，加上或者减去一个数与这个数本身无关，可以直接相加减，可以直接做记号表示这个块加上或减去了某个数。

加上或减去某个数时，在完整块中，这一个块每一个数增加或减少的值都相同，就可以很容易地给这一整个块做标记。

但是做开方运算时（其实乘方、乘除都很坑），每一个块增加或者减小的值不相等，就导致了不能把这一整个块增加或减小的值做一个标记，这就相当于把分块废掉了。

解法#

这是一道题目，总不可能没有解法吧。

我们用到了下面这个 $\rm sol()$ 函数来解决这个问题。

1
void sol(int x) {
2
  if (flag[x]) return; //如果这个块被标记了，就废了，直接返回，节省时间
3
                       //标记原则后面会讲
4
  flag[x] = true;      //先把这个块标记
5
  sum[x] = 0;          //将sum[]数组初始化为零
6
  for (int i = (x - 1) * len + 1; i <= x * len; i++) { //循环块内每一个值
7
    a[i] = sqrt(a[i]), sum[x] += a[i]; //对块内每一个数都做开方运算，再把他们的和存进sum[]数组里面
8
    if (a[i] > 1) flag[x] = false;     //如果这一个值还大于1，也就是还能够进行开方，这个块就还能继续开放，把flag[]标记去除
9
  }
10
  return;
11
}

从上面的函数中可以看出，我们把已经不能再开方的块进行跳过，大大节约了程序开方的时间。这就是代码的关键。

剩下的地方就和普通的数列分块差不多了。

代码#

1
#include <cstdio> //getchar()和putchar()要用
2
#include <cmath>  //取块大小和开方时需要用到sqrt()函数
3

4
int b[50005], a[50005], sum[255];
5
bool flag[255];
6
int len;
7

8
int read() {//快速读入，因为LibreOJ默认吸氧，所以没有了前面的inline
9
  int X = 0; bool flag = 1; char ch = getchar();
10
  while (ch < '0' || ch > '9') {if (ch == '-') flag = 0; ch = getchar();}
11
  while (ch >= '0' && ch <= '9') {X = (X << 1) + (X << 3) + ch - '0'; ch = getchar();}
12
  if (flag) return X;
13
  return ~ (X - 1);
14
}
15

16
void write(int X) {//快速输出，同上
17
  if (X < 0) {putchar('-'); X = ~ (X - 1);}
18
  int s[50], top = 0;
19
  while (X) {s[++top] = X % 10; X /= 10;}
20
  if (!top) s[++top] = 0;
21
  while (top) putchar(s[top--] + '0');
22
  putchar('\n');
23
  return;
24
}
25

26
void sol(int x) {
27
  if (flag[x]) return; //如果这个块被标记了，就废了，直接返回，节省时间
28
  flag[x] = true;      //先把这个块标记
29
  sum[x] = 0;          //将sum[]数组初始化为零
30
  for (int i = (x - 1) * len + 1; i <= x * len; i++) { //循环块内每一个值
31
    a[i] = sqrt(a[i]), sum[x] += a[i]; //对块内每一个数都做开方运算，再把他们的和存进sum[]数组里面
32
    if (a[i] > 1) flag[x] = false;     //如果这一个值还大于1，也就是还能够进行开方，这个块就还能继续开放，把flag[]标记去除
33
  }
34
  return;
35
}
36

37
void add(int l, int r) {
38
  for (int i = l; i <= (b[l] * len < r ? b[l] * len : r); i++) { //从左往右暴力循环左侧不完整块
39
    sum[b[l]] -= a[i];
40
    a[i] = sqrt(a[i]);
41
    sum[b[l]] += a[i];
42
  }
43
  if (b[l] != b[r]) //如果l和r不在同一块内
44
    for (int i = r; b[i] == b[r]; i--) { //同右往左暴力循环右侧不完整块
45
  //循环条件这里我原来一直写i == b[r]就错了，要注意，下面query()函数也是
46
      sum[b[r]] -= a[i];
47
      a[i] = sqrt(a[i]);
48
      sum[b[r]] += a[i];
49
    }
50
  for (int i = b[l] + 1; i <= b[r] - 1; i++) sol(i); //中间完整块使用sol()函数解决
51
  return;
52
}
53

54
int query(int l, int r) { //查询函数，与普通分块差不多
55
  int ans = 0;
56
  for (int i = l; i <= (b[l] * len < r ? b[l] * len : r); i++) ans += a[i];//左侧
57
  if (b[l] != b[r]) for (int i = r; b[i] == b[r]; i--) ans += a[i];//右侧
58
  for (int i = b[l] + 1; i <= b[r] - 1; i++) ans += sum[i];//中间
59
  return ans;
60
}
61

62
int main() {
63
  int n;
64
  n = read();
65
  len = sqrt(n);
66
  for (int i = 1; i <= n; i++) a[i] = read();
67
  for (int i = 1; i <= n; i++) {
68
    b[i] = (i - 1) / len + 1;
69
    sum[b[i]] += a[i];
70
  }
71
  for (int i = 1; i <= n; i++) {
72
    bool opt; int l, r;
73
    opt = read(); l = read(); r = read(); read();
74
    opt ? write(query(l, r)) : add(l, r);
75
    //三目运算符，如果opt==1就add()，else就query()
76
  }
77
  return 0;
78
}