Jinglei's blog
0%

「Luogu P4145」上帝造题的七分钟 2 花神游历各国

Posted on Edited on

题目链接：https://www.luogu.com.cn/problem/P4145

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

题目背景

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

题目描述

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

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

  • k=0k=0 表示给 [l,r][l,r] 中的每个数开平方（下取整）。

  • k=1k=1 表示询问 [l,r][l,r] 中各个数的和。

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

输出格式

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

样例 #1

样例输入 #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

提示

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

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

思路

这道题让我想起了 MssCTF2021 初赛的一道 PPC（也就是OI）题目，题面是这样的：

Screenshot_20220801_171724

比赛时我百思不得其解，这个式子太诡异了，题面看上去很容易理解，然而不知道怎么做。由于 nn 的范围甚至超出了 1e9，直接 O(n)O(n) 的暴力肯定是会 TLE 的，直到我看了他们的官方讲评：

Screenshot_20220801_172127

我直接被震惊了，可谓是人类智慧的充分发扬。这提醒我们，如果有题目要求你计算多次开根号，记得往输出精度方面考虑，如果硬想如何去算出来精确值的话很可能方向错了。

同样，这道题的唯一一个修改操作就是把区间内的每一个数开方，而且这些数初始值都在 1e121e12 以内。经过计算，开方 7 次即可保证所有可能的值都收敛到 1 。所以，我们只需要把数列分块，然后记录每个块开方 n(1<=n<=7)n (1<=n<=7) 次的和。修改时，左右两边的那些点暴力修改区间和，中间的整块打 lazytag，如果 tag 大于 7，就把它设成 7，这样查询的时候就可以直接查询开方 tag 次对应的区间和了。

代码

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <cstdio>
#include <iostream>
#include <cmath>
using std::swap;

const int Maxn = 1e5+5, Maxsq = 1e3+5;
typedef long long lol;
int block, num, n, start[Maxsq], end[Maxsq], tag[Maxsq];
lol a[Maxn], sqs[10][Maxn], sum[10][Maxsq];
void work(int, int);
lol query(int, int);

int main(){
//	freopen("data.in", "r", stdin);

	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%lld", &a[i]);
	}

	block = sqrt(n); num = n/block;
	for(int i=0; i<num; i++){
		start[i] = i*block;
		end[i] = (i+1)*block;
		for(int j=start[i]; j<end[i]; j++){
			sqs[0][j] = a[j];
			sum[0][i] += sqs[0][j];
		}
		for(int k=1; k<=7; k++){
			for(int j=start[i]; j<end[i]; j++){
				sqs[k][j] = sqrt(sqs[k-1][j]);
				sum[k][i] += sqs[k][j];
			}
		}
	}
	if(n%block != 0){
		start[num] = num*block;
		end[num] = n;
		for(int j=start[num]; j<end[num]; j++){
			sqs[0][j] = a[j];
			sum[0][num] += sqs[0][j];
		}
		for(int k=1; k<=7; k++){
			for(int j=start[num]; j<end[num]; j++){
				sqs[k][j] = sqrt(sqs[k-1][j]);
				sum[k][num] += sqs[k][j];
			}
		}
	}

	int m, k, l, r;
	scanf("%d", &m);
	while(m--){
		scanf("%d %d %d", &k, &l, &r);
		if(l > r) swap(l, r);
		if(k == 0) work(l-1, r-1);
		else printf("%lld\n", query(l-1, r-1));
	}

	return 0;
}

void work(int l, int r){
	int lb = l/block, rb = r/block;
	if(lb != rb){
		for(int i=l; i==l||i%block!=0; i++){
			sqs[0][i] = sqrt(sqs[0][i]);
			sum[0][lb] -= a[i];
			sum[0][lb] += sqs[0][i];
			a[i] = sqrt(a[i]);
			for(int k=1; k<=7; k++){
				sqs[k][i] = sqrt(sqs[k][i]);
				sum[k][lb] -= sqs[k-1][i];
				sum[k][lb] += sqs[k][i];
			}
		}
		for(int i=r; i==r||i%block!=block-1; i--){
			sqs[0][i] = sqrt(sqs[0][i]);
			sum[0][rb] -= a[i];
			sum[0][rb] += sqs[0][i];
			a[i] = sqrt(a[i]);
			for(int k=1; k<=7; k++){
				sqs[k][i] = sqrt(sqs[k][i]);
				sum[k][rb] -= sqs[k-1][i];
				sum[k][rb] += sqs[k][i];
			}
		}
		for(int i=lb+1; i<rb; i++){
			tag[i]++;
			tag[i] = tag[i]>7?7:tag[i];
		}
	}
	else{
		for(int i=l; i<=r; i++){
			sqs[0][i] = sqrt(sqs[0][i]);
			sum[0][lb] -= a[i];
			sum[0][lb] += sqs[0][i];
			a[i] = sqrt(a[i]);
			for(int k=1; k<=7; k++){
				sqs[k][i] = sqrt(sqs[k][i]);
				sum[k][lb] -= sqs[k-1][i];
				sum[k][lb] += sqs[k][i];
			}
		}
	}
}

lol query(int l, int r){
	int lb = l/block, rb = r/block;
	lol summ = 0;
	if(lb != rb){
		for(int i=l; i==l||i%block!=0; i++){
			summ += sqs[tag[lb]][i];
		}
		for(int i=r; i==r||i%block!=block-1; i--){
			summ += sqs[tag[rb]][i];
		}
		for(int i=lb+1; i<rb; i++){
			summ += sum[tag[i]][i];
		}
	}
	else{
		for(int i=l; i<=r; i++){
			summ += sqs[tag[lb]][i];
		}
	}
	return summ;
}