目录

  1. 引言
  2. UOJ #228. 基础数据结构练习题
    1. 输入格式
    2. 输出格式
    3. 样例一
      1. input
      2. output
    4. 样例二
    5. 限制与约定
    6. 下载
    7. 题目分析
    8. 代码

引言

UOJ #228. 基础数据结构练习题 题解

UOJ #228. 基础数据结构练习题

sylvia 是一个热爱学习的女孩子,今天她想要学习数据结构技巧。

在看了一些博客学了一些姿势后,她想要找一些数据结构题来练练手。于是她的好朋友九条可怜酱给她出了一道题。

给出一个长度为 $n$ 的数列 $A$,接下来有 $m$ 次操作,操作有三种:

  1. 对于所有的 $i \in [l,r]$,将 $A_i$ 变成 $A_i+x$。
  2. 对于所有的 $i \in [l,r]$,将 $A_i$ 变成 $\lfloor \sqrt {A_i} \rfloor$。
  3. 对于所有的 $i \in [l,r]$,询问 $A_i$ 的和。

作为一个不怎么熟练的初学者,sylvia 想了好久都没做出来。而可怜酱又外出旅游去了,一时间联系不上。于是她决定向你寻求帮助:你能帮她解决这个问题吗。

输入格式

第一行两个数:$ n, m $。

接下来一行 $ n $ 个数 $A_i$。

接下来 $ m $ 行中,第 $ i $ 行第一个数 $ t_i $ 表示操作类型:

若 $ t_i = 1 $,则接下来三个整数 $ l_i, r_i, x_i $,表示操作一。

若 $ t_i = 2 $,则接下来三个整数 $ l_i, r_i$,表示操作二。

若 $ t_i = 3 $,则接下来三个整数 $ l_i, r_i$,表示操作三。

输出格式

对于每个询问操作,输出一行表示答案。

样例一

input

5 5
1 2 3 4 5
1 3 5 2
2 1 4
3 2 4
2 3 5
3 1 5

output

5
6

样例二

见样例数据下载。

限制与约定

测试点编号$n$ 的规模$m$ 的规模其他约定
1$n \leq 3000$$m \leq 3000$
2
3
4$n \leq 100000$$m \leq 100000$数据随机生成
5
6$t_i \neq 1$
7
8
9
10

对于所有数据,保证有 $1 \leq l_i \leq r_i \leq n,1 \leq A_i,x_i \leq 10^5$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载

题目分析

首先,这非常显然是一道平摊分析线段树的题对吧……因为有开方这种无法批量快速维护的操作

我们知道,在没有增加的操作的时候,开方的运算量级是$O(\log \log n)$,是极其地小的,可以直接暴力操作

但是这道题有区间加,所以,我们就考虑什么时候我们可以批量更改信息,我们可以维护一个区间的最大值和最小值,显然如果这两个值开方后相同,那么就可以直接区间覆盖对吧

然后,我们可以考虑开方操作分到两边的次数(这意味着我们暴力的量级), 这说明,当前这个区间的最大值和最小值开方后不相等,但这个差距在经过开方的运算量级这么多次操作以后,这个差距就会被消除掉,而要想再制造出这样的差距,每个差距都需要一次区间加操作,所以暴力是很稳的

但是如果只是这样做其实是不行的,因为当差距为$1$的时候,已经无法再消除的更小了,但是这个时候最大值和最小值的开方也可以不相同啊,比如一个是$n ^ 2 - 1$,另一个是$n ^ 2$。,这样,我们可以这样构造数据,$0$和$1$间隔放置,然后开方操作和区间加65535间隔放置(至于为什么是这个数,请自行思考),这样这个算法就会退化到$O(n ^ 2)$级别

所以,我们只要再特殊判断一下这种坑人的情况就可以了(其实应该很容易想到,因为$1$开多少次方都还是$1$,相等于是差距经过数次开方减少到了边界)

代码

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
//#define DEBUG
#define maxn 300005
#define ll long long int
#define llen (mid - l + 1)
#define rlen (r - mid)
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') f = 0, ch = gc();
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m;
int a[maxn];
ll sum[maxn << 1];
ll mx[maxn << 1];
ll mi[maxn << 1];
ll set[maxn << 1];
ll add[maxn << 1];
int qx, qy;
ll qd;
void pushup(int o){
sum[o] = sum[o << 1] + sum[o << 1 | 1];
mx[o] = max(mx[o << 1], mx[o << 1 | 1]);
mi[o] = min(mi[o << 1], mi[o << 1 | 1]);
}
void pushdown(int l, int r, int o){
int mid = ((r - l) >> 1) + l, ls = o << 1, rs = o << 1 | 1;
if (set[o] != -1){
ll k = set[o];
sum[ls] = llen * k, mx[ls] = mi[ls] = set[ls] = k, add[ls] = 0;
sum[rs] = rlen * k, mx[rs] = mi[rs] = set[rs] = k, add[rs] = 0;
set[o] = -1;
}
if (add[o]){
ll k = add[o];
sum[ls] += llen * k, mx[ls] += k, mi[ls] += k, add[ls] += k;
sum[rs] += rlen * k, mx[rs] += k, mi[rs] += k, add[rs] += k;
add[o] = 0;
}
}
void init(int l, int r, int o){
set[o] = -1;
//add[o] = 0;
if (l == r){
mx[o] = mi[o] = sum[o] = a[l];
return;
}
int mid = ((r - l) >> 1) + l;
init(l, mid, o << 1);
init(mid + 1, r, o << 1 | 1);
pushup(o);
}
ll get(int l, int r, int o){
pushdown(l, r, o);
if (qx <= l && r <= qy) return sum[o];
int mid = ((r - l) >> 1) + l;
ll ans = 0;
if (qx <= mid) ans += get(l, mid, o << 1);
if (qy > mid) ans += get(mid + 1, r, o << 1 | 1);
return ans;
}
void square(int l, int r, int o){
pushdown(l, r, o);
if (qx <= l && r <= qy){
int a = (int) sqrt(mx[o]), b = (int) sqrt(mi[o]);
if (a == b) {
if (add[o] || set[o] != -1) assert(false);
set[o] = mx[o] = mi[o] = a;
sum[o] = (ll)a * (r - l + 1);
}
else if (mx[o] == mi[o] + 1){
ll k = a - mx[o];
add[o] += k, mx[o] += k, mi[o] += k;
sum[o] += k * (r - l + 1);
}
else {
int mid = ((r - l) >> 1) + l;
square(l, mid, o << 1);
square(mid + 1, r, o << 1 | 1);
pushup(o);
}
return;
}
int mid = ((r - l) >> 1) + l;
if (qx <= mid) square(l, mid, o << 1);
if (qy > mid) square(mid + 1, r, o << 1 | 1);
pushup(o);
}
void modify(int l, int r, int o){
pushdown(l, r, o);
if (qx <= l && r <= qy){
add[o] += qd, mx[o] += qd, mi[o] += qd;
sum[o] += (r - l + 1) * qd;
return;
}
int mid = ((r - l) >> 1) + l;
if (qx <= mid) modify(l, mid, o << 1);
if (qy > mid) modify(mid + 1, r, o << 1 | 1);
pushup(o);
}
void debug(){
rep(i, 1, n){
qx = qy = i;
printf("%lld ", get(1, n, 1));
}
printf("\n\n\n");
}
int main(){
#ifndef ONLINE_JUDGE
freopen("prac.in", "r", stdin);
#endif
int t;
read(n), read(m);
rep(i, 1, n) read(a[i]);
init(1, n, 1);
rep(i, 1, m){
read(t), read(qx), read(qy);
switch(t){
case 1: read(qd), modify(1, n, 1); break;
case 2: square(1, n, 1); break;
case 3: printf("%lld\n", get(1, n, 1)); break;
default: break;
}
#ifdef DEBUG
debug();
#endif
}
return 0;
}