HDU 5828 Rikka with Sequence【线段树】

ACM_数据结构

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5828

题意：

给定序列，给定操作，
有三种操作：

  1. 给定区间内所有数将上$x$
  2. 给定区间内所有数开根
  3. 求给定区间内所有数的和

分析：

集训的时候做过一道只有开根和求和操作的题，在题目给定范围内，一个数最多开根$7$次就变为$1$，当时是利用这个进行优化。
而这道题还有加的操作，所以不能用$1$这个性质， 但是不断开根之后区间内的数最终会趋近相同，所以我们可以加个$same$标记相应区间内所有数是否相同。
但是这样还是会$T$，因为存在两个数，开根和加$x$不断交替进行，永远不会相同(例如$8,9$不断开根、加$6$)。对于这两个数组成的排列，每次都要更新到叶结点，肯定爆炸。
分析可得对于一个区间，我们一共有三种情况：

  1. 区间内所有数相等
  2. 区间内极差大于1
  3. 区间内极差等于1

首先我们对于每个区间维护最大值和最小值。
情况1直接进行区间操作，情况2最终会转化成3或者1，
而情况3中，当极差等于1时，再次开根，极差可能相等，问题转化为情况1，或者仍然差一，此时显然区间所有数减去了相同的值，直接修改区间和。
也就是说对于$maxx == minn + 1$的情况进行一下特殊处理，其余情况正常处理即可。

代码：

额为啥

1
2
#define lson i << 1
#define rson i << 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
/*************************************************************************
    > File Name: test.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/7/26 21:06:05
 ************************************************************************/
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5, oo = 0x3f3f3f3f;
#define lson i << 1
#define rson i << 1 | 1
int a[maxn];
struct Tree{
    int l, r;
    ll lazy, val;
	ll maxx, minn;
}tree[maxn * 4 + 5];
void push_up(int i)
{
    tree[i].minn = min(tree[lson].minn, tree[rson].minn);
	tree[i].maxx = max(tree[lson].maxx, tree[rson].maxx);
	tree[i].val = tree[lson].val + tree[rson].val;
}
void build(int i, int l, int r)
{
	tree[i].l = l;
	tree[i].r = r;
	tree[i].val = 0;
	tree[i].lazy = 0;
	tree[i].minn = oo;
	tree[i].maxx = 0;
	if(l == r){
		tree[i].val = a[l];
		tree[i].maxx = a[l];
		tree[i].minn = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(lson, l, mid);
	build(rson, mid + 1, r);
	push_up(i);
}
void push_down(int i)
{
   if(tree[i].lazy){
        tree[lson].lazy += tree[i].lazy;
        tree[rson].lazy += tree[i].lazy;
		tree[lson].minn += tree[i].lazy;
		tree[lson].maxx += tree[i].lazy;
		tree[rson].minn += tree[i].lazy;
		tree[rson].maxx += tree[i].lazy;
		tree[lson].val += tree[i].lazy * (tree[lson].r - tree[lson].l + 1);
		tree[rson].val += tree[i].lazy * (tree[rson].r - tree[rson].l + 1);
        tree[i].lazy = 0;
   }
}
void update(int i, int l, int r, int val)
{
    if(tree[i].l == l && tree[i].r == r){
        tree[i].lazy += val;
		tree[i].maxx += val;
		tree[i].minn += val;
		tree[i].val += (r - l + 1) * (ll)val;
        return;
    }
    push_down(i);
    int mid = tree[i].l + tree[i].r >> 1;
    if(r <= mid) update(lson, l, r, val);
    else if(l > mid) update(rson, l, r, val);
    else{
        update(lson, l, mid, val);
        update(rson, mid + 1, r, val);
    }
	push_up(i);
}
void update2(int i, int l, int r)
{
	if(tree[i].l >= l && tree[i].r <= r){
		if(tree[i].minn == tree[i].maxx){
			ll tmp = (ll)sqrt((double)tree[i].minn);
			tree[i].lazy -= tree[i].minn - tmp;
			tree[i].minn = tmp;
			tree[i].maxx = tmp;
			tree[i].val = (tree[i].r - tree[i].l + 1) * tmp;
			return;
		}else if(tree[i].minn == tree[i].maxx - 1){
			ll tmp1 = (ll)sqrt((double)tree[i].minn);
			ll tmp2 = (ll)sqrt((double)tree[i].maxx);
			if(tmp1 == tmp2 - 1){
				tree[i].lazy -= tree[i].maxx - tmp2;
				tree[i].val -= (tree[i].maxx - tmp2) * (tree[i].r - tree[i].l + 1);
				tree[i].minn = tmp1;
				tree[i].maxx = tmp2;
				return;
			}
		}
	}
    push_down(i);
    int mid = tree[i].l + tree[i].r >> 1;
    if(r <= mid) update2(lson, l, r);
    else if(l > mid) update2(rson, l, r);
    else{
        update2(lson, l, mid);
        update2(rson, mid + 1, r);
    }
	push_up(i);
}
ll query(int i, int l, int r)
{
    if(tree[i].l == l && tree[i].r == r){
		return tree[i].val;
    }
    push_down(i);
    int mid = tree[i].l + tree[i].r >> 1;
    if(r <= mid) return query(lson, l, r);
	else if(l > mid)  return query(rson, l, r);
	else return query(lson, l, mid) + query(rson, mid + 1, r);
}
int main(void)
{
    int T;scanf("%d", &T);
	while(T--){
        int n, m;scanf("%d%d", &n, &m);
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        build(1, 0, n);
		int op, l, r, x;
        for(int i = 0; i < m; i++){
           scanf("%d%d%d", &op, &l, &r);
		   l--;r--;
		   if(op == 1){
			   scanf("%d", &x);
			   update(1, l, r, x);
		   }else if(op == 2){
			   update2(1, l, r);
		   }else{
			   printf("%lld\n", query(1, l, r));
		   }
        }
    }
    return 0;
}

其他：

下面是加强数据后TLE的程序，每次更新到区间元素值相同的区间，这个思想还是很好的。

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
/*************************************************************************
    > File Name: test.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/7/26 21:06:05
 ************************************************************************/
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int a[maxn];
struct Tree{
    int l, r;
    ll lazy, val;
	ll same;
}tree[maxn * 4 + 5];
void push_up(int i)
{
	if(tree[i << 1].same && tree[i << 1].same == tree[(i << 1)|1].same){
		tree[i].same = tree[i << 1].same;
	}else tree[i].same = 0;
	tree[i].val = tree[(i << 1) | 1].val + tree[i << 1].val;
}
void build(int i, int l, int r)
{
	tree[i].l = l;
	tree[i].r = r;
	tree[i].val = 0;
	tree[i].lazy = 0;
	tree[i].same = 0;
	if(l == r){
		tree[i].val = a[l];
		tree[i].same = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(i << 1, l, mid);
	build((i << 1) | 1, mid + 1, r);
	push_up(i);
}
void push_down(int i)
{
   if(tree[i].lazy){
        tree[i << 1].lazy += tree[i].lazy;
        tree[(i << 1) | 1].lazy += tree[i].lazy;
		if(tree[i << 1].same) 
			tree[i << 1].same += tree[i].lazy;
		if(tree[(i << 1) | 1].same) 
			tree[(i << 1) | 1].same += tree[i].lazy;
		tree[i << 1].val += tree[i].lazy * (tree[i << 1].r - tree[i << 1].l + 1);
		tree[(i << 1) | 1].val += tree[i].lazy * (tree[(i << 1)|1].r - tree[(i << 1)|1].l + 1);
        tree[i].lazy = 0;
   }
}
void update(int i, int l, int r, int val)
{
    if(tree[i].l == l && tree[i].r == r){
        tree[i].lazy += val;
		if(tree[i].same) tree[i].same += val;
		tree[i].val += (r - l + 1) * (ll)val;
        return;
    }
    push_down(i);
    int mid = tree[i].l + tree[i].r >> 1;
    if(r <= mid) update(i << 1, l, r, val);
    else if(l > mid) update((i << 1) | 1, l, r, val);
    else{
        update(i << 1, l, mid, val);
        update((i << 1) | 1, mid + 1, r, val);
    }
	push_up(i);
}
void update2(int i, int l, int r)
{
	if(tree[i].l >= l && tree[i].r <= r && tree[i].same){
		ll tmp = (ll)sqrt((double)tree[i].same);
		tree[i].lazy -= tree[i].same - tmp;
		tree[i].same = tmp;
		tree[i].val = (tree[i].r - tree[i].l + 1) * tree[i].same;
		return;
	}
	if(tree[i].l == tree[i].r){
		ll tmp = (ll)sqrt((double)tree[i].same);
		tree[i].lazy -= tree[i].same - tmp;
		tree[i].same = tmp;
		tree[i].val = tree[i].same;
		return;
	}
    push_down(i);
    int mid = tree[i].l + tree[i].r >> 1;
    if(r <= mid) update2(i << 1, l, r);
    else if(l > mid) update2((i << 1) | 1, l, r);
    else{
        update2(i << 1, l, mid);
        update2((i << 1) | 1, mid + 1, r);
    }
	push_up(i);
}
ll query(int i, int L, int R)
{
    if(tree[i].l == L && tree[i].r == R){
		return tree[i].val;
    }
    push_down(i);
    int mid = tree[i].l + tree[i].r >> 1;
    if(R <= mid) return query(i << 1, L, R);
	else if(L > mid)  return query((i <<1)|1, L, R);
	else return query(i << 1, L, mid) + query((i <<1)|1, mid + 1, R);
}
int main(void)
{
    int T;scanf("%d", &T);
	while(T--){
        int n, m;scanf("%d%d", &n, &m);
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        build(1, 0, n);
		int op, l, r, x;
        for(int i = 0; i < m; i++){
           scanf("%d%d%d", &op, &l, &r);
		   l--;r--;
		   if(op == 1){
			   scanf("%d", &x);
			   update(1, l, r, x);
		   }else if(op == 2){
			   update2(1, l, r);
		   }else{
			   printf("%lld\n", query(1, l, r));
		   }
        }
    }
    return 0;
}
文章目录
  1. 1. 题目链接：
  2. 2. 题意：
  3. 3. 分析：
  4. 4. 代码：
  5. 5. 其他：