Bzoj 3211(线段树/树状数组+并查集)

BZOJ 3211
2017.8.19:
本题就是线段树模板题,但是sqrt慢,并且点也只能一个个sqrt,不能一起sqrt,维护一个lazy标记区间是否全是1或0,然后写就行了(并不知道之前写的并查集是什么东西。。)

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n, Q, data[MAXN];
int flag[MAXN * 4];
LL sumv[MAXN * 4];
#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)
void pushup(int o) {
sumv[o] = sumv[lc] + sumv[rc];
flag[o] = (flag[lc] && flag[rc]);//记得传,不然TLE
}
void build(int o, int l, int r) {
if (l == r) {
sumv[o] = data[l];
if (sumv[o] == 0 || sumv[o] == 1) flag[o] = true;//对这个(点)开方已经没有意义
} else flag[o] = sumv[o] = 0, build(lc, l, M), build(rc, M + 1, r), pushup(o);
}
void update(int o, int l, int r, int x, int y) {
if (flag[o]) return ;//这个区间都是1或0
if (l == r) {
sumv[o] = sqrt(sumv[o]);
if (sumv[o] == 0 || sumv[o] == 1) flag[o] = true;//对这个(点)开方已经没有意义
return ;
}
if (x <= M) update(lc, l, M, x, y);
if (M < y) update(rc, M + 1, r, x, y);
pushup(o);
}
LL query(int o, int l, int r, int x, int y) {
LL ret = 0;
if (x <= l && r <= y) {
return sumv[o];
}
if (x <= M) ret += query(lc, l, M, x, y);
if (M < y) ret += query(rc, M + 1, r, x, y);
return ret;
}
void clean() {}
void solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &data[i]);
build(1, 1, n);
scanf("%d", &Q);
while (Q--) {
int x, l, r;
scanf("%d%d%d", &x, &l, &r);
if (x == 1) {
printf("%lld\n", query(1,1,n,l,r));
} else {
update(1,1,n,l,r);
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d", &n), solve();
return 0;
}

树状数组裸题,但是因为sqrt的速度很慢,所以我们在一个数为1或者为0就删掉它(用并查集维护)
ps:交题时注意文件声明部分要注释掉!坑死了

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define ms(i,j) memset(i, j, sizeof i);
#define ll long long
using namespace std;
const int MAXN = 100000 + 5;
ll a[MAXN], f[MAXN];
int data[MAXN];
int n,m;
int lowbit(ll x) {return x&(-x);}
int find(int x)
{
if (f[x]==x) return x;
else return f[x] = find(f[x]);
}
ll sum(int x)
{
ll ret = 0;
for (ll i=x;i>0;i-=lowbit(i))
{
ret += (ll)a[i];
}
return ret;
}
int update(int x, int c)
{
for (ll i=x;i<=n;i+=lowbit(i))
{
a[i] += c;
}
}
int main()
{
//freopen("bzoj3211.in", "r", stdin); freopen("bzoj3211.out", "w", stdout);
scanf("%d\n", &n); ms(a, 0);
for (int i=1;i<=n+1;i++) f[i] = i;
for (int i=1;i<=n;i++)
{
scanf("%lld", &data[i]);
if (data[i]==1||data[i]==0) f[i] = find(i+1);
update(i, data[i]);
}
scanf("%d", &m);
for (int i=1;i<=m;i++)
{
int x, l, r;
scanf("%d%d%d", &x, &l, &r);
if (x==1) printf("%lld\n", sum(r)-sum(l-1)); else if (x==2)
{
for (int j=find(l);j<=r;j=find(j+1))
{
update(j, (ll)(sqrt(data[j]))-data[j]);
data[j] = (ll)(sqrt(data[j]));
if(data[j]==1)
{
f[j] = find(j+1);
}
}
}
}
return 0;
}

------ 本文结束 ------