You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
122 lines
3.4 KiB
122 lines
3.4 KiB
|
|
##[$GSS4$ - $Can$ $you$ $answer$ $these$ $queries$ $IV$](http://acm.hdu.edu.cn/showproblem.php?pid=4027)
|
|
|
|
|
|
### 一、题目描述
|
|
给定的$n$个数，我们定义两个操作，分别是区间**开根号**以及**区间求和**。共有$m$次查询，其中$n,m≤1e5$。
|
|
|
|
### 二、解题思路
|
|
一个$1e18$以内的数，经过最多$6$次开平方操作后，会变成$1$。
|
|
```cpp {.line-numbers}
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
int main() {
|
|
long long a = 1e18;
|
|
for (int i = 1; i <= 6; i++) {
|
|
a = sqrt(a);
|
|
cout << a << endl;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
输出:
|
|
1000000000
|
|
31622
|
|
177
|
|
13
|
|
3
|
|
1
|
|
```
|
|
建立线段树，对于每一个叶子节点我们最多进行$6$次的更新操作后，再开方就不会改变大小了。那么我们可以有两种方法:
|
|
|
|
* ① 维护区间和，**如果区间和等于区间长度则不需要更新**
|
|
* ② 维护区间最大值，**对于区间最大值是$1$的区间**，我们就可以直接不考虑了
|
|
|
|
就是为了减枝，真是无所不用其极！
|
|
|
|
|
|
对于需要进行开平方的区间，我们一直 **暴力** 更新到叶子节点，因为每个叶子节点最多更新$6$次，所以这个是可以接受的，时间复杂度$O(nlogn)$。
|
|
|
|
* 坑点$1$：题目中并没有说明输入区间时$x$和$y$谁大谁小，所以要加一个条件，来找出小的值和大的值
|
|
|
|
* 坑点$2$：在开始的时候输入战舰的寿命的时候一定要用`long long`类型，要不然过不了（之前用来`int`型，结果一直`TLE`，也不知道为啥，之后该为`long long`之后就`AC`了）
|
|
* 坑点$3$：在每次结束之后，一定不要忘了最后在输出一个空行
|
|
|
|
### 三、实现代码
|
|
```cpp {.line-numbers}
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
#include <algorithm>
|
|
#include <iostream>
|
|
#include <cmath>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
const int N = 1e6 + 10;
|
|
#define ls u << 1
|
|
#define rs u << 1 | 1
|
|
LL a[N];
|
|
|
|
struct Node {
|
|
int l, r;
|
|
LL sum;
|
|
} tr[N << 2];
|
|
|
|
void pushup(int u) {
|
|
tr[u].sum = tr[ls].sum + tr[rs].sum;
|
|
}
|
|
|
|
void build(int u, int l, int r) {
|
|
tr[u] = {l, r, 0};
|
|
if (l == r) {
|
|
tr[u].sum = a[l];
|
|
return;
|
|
}
|
|
int mid = (l + r) >> 1;
|
|
build(ls, l, mid), build(rs, mid + 1, r);
|
|
pushup(u);
|
|
}
|
|
|
|
void modify(int u, int l, int r) {
|
|
if (tr[u].sum == (tr[u].r - tr[u].l + 1)) return; //伟大的剪枝
|
|
|
|
if (tr[u].l == tr[u].r) {
|
|
tr[u].sum = sqrt(tr[u].sum);
|
|
return;
|
|
}
|
|
|
|
int mid = tr[u].l + tr[u].r >> 1;
|
|
if (l <= mid) modify(ls, l, r);
|
|
if (r > mid) modify(rs, l, r);
|
|
pushup(u);
|
|
}
|
|
|
|
LL query(int u, int l, int r) {
|
|
if (r < tr[u].l || l > tr[u].r) return 0;
|
|
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
|
|
return query(ls, l, r) + query(rs, l, r);
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
int n, q, cas = 1;
|
|
while (cin >> n) {
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
|
build(1, 1, n);
|
|
|
|
cin >> q;
|
|
printf("Case #%d:\n", cas++);
|
|
while (q--) {
|
|
int c, l, r;
|
|
cin >> c >> l >> r;
|
|
if (l > r) swap(l, r);
|
|
if (c == 0)
|
|
modify(1, l, r);
|
|
else
|
|
printf("%lld\n", query(1, l, r));
|
|
}
|
|
printf("\n");
|
|
}
|
|
return 0;
|
|
}
|
|
``` |