HDU5828 Rikka with Sequence

2016多校, HDU, 线段树

　　2016 Multi-University Training Contest 8

　　题意：n元素序列，给定m种操作——区间加法，区间开方，区间求和。对于每个求和操作，输出结果。 - 原题链接

　　很显然的线段树，然而直接思路也很显然会T。
　　赛时一直在纠结线段树应该维护什么东西，若维护操作序列，那只能朴素求和；若维护区间和，那sqrt要落实到所有叶子结点，代价太大。

　　后来学习了官方题解和网上的博客，其实主要性质是，开方操作使元素减小非常快，不断开方后区间内元素最终会趋近相同，于是可以用到以下两种优化：

  • 若区间元素相同，转化为区间加法，tmp+=(sqrt(val)-val)
  • 若区间元素极差为1且开方后极差仍为1，转化为区间加法，tmp+=(sqrt(min)-min)

　　大概是很多细节没处理好，套上读入优化也只能到2839MS，过得很勉强＝ ＝

　　敲完这题想到了多校1的那道GCD，当时我用极端数据a[i]=2^i推翻了自己的算法，却没有注意到在a[i]的限制范围内不可能出现持续的极端数据。两道题其实是用开方和对数将题面的大范围缩小到了可操作的小范围内，以后遇到类似问题要有这样的意识。
　　（谁能告诉我这篇代码为什么不能高亮😭） 


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
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define kl (k<<1)
#define kr ((k<<1)+1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long lint;
const int maxn=1e5 + 10;
  
int T, n, m;
struct node
{
	lint mn, mx, sum, tmp;
	node(lint _mn=0, lint _mx=0, lint s=0, lint t=0) { mn=_mn, mx=_mx, sum=s, tmp=t; }
}tr[maxn<<2];
  
void Get_lint(lint &num, char c=0)
{
	for(c=getchar(); c<'0'||c>'9'; c=getchar());
	for(num=c-48; c=getchar(), c>='0'&&c<='9'; num=num*10+c-48);
	return ;
}
  
void Build(int k=1, int l=1, int r=n)
{
	tr[k].mn=tr[k].mx=tr[k].sum=tr[k].tmp=0;
	if(l==r)	return ;
	Build(kl, l, mid);
	Build(kr, mid+1, r);
	return ;
}
  
void Push_down(int k, int l, int r)
{
	tr[kl].mn+=tr[k].tmp, tr[kl].mx+=tr[k].tmp, tr[kl].sum+=(mid-l+1)*tr[k].tmp, tr[kl].tmp+=tr[k].tmp;
	tr[kr].mn+=tr[k].tmp, tr[kr].mx+=tr[k].tmp, tr[kr].sum+=(r-mid)*tr[k].tmp, tr[kr].tmp+=tr[k].tmp;
	tr[k].tmp=0;
	return ;
}
  
void Push_up(int k, int l, int r)
{
	tr[k].mn=min(tr[kl].mn, tr[kr].mn);
	tr[k].mx=max(tr[kl].mx, tr[kr].mx);
	tr[k].sum=tr[kl].sum+tr[kr].sum;
	return ;
}
  
void Insert(int ll, int rr, lint x, int k=1, int l=1, int r=n)
{
	if(rr <l||r< ll)	return ;
	if(ll<=l&&r<=rr)
	{
		tr[k].mn+=x, tr[k].mx+=x, tr[k].sum+=(r-l+1)*x, tr[k].tmp+=x;
		return ;
	}
	if(tr[k].tmp)	Push_down(k, l, r);
	Insert(ll, rr, x, kl, l, mid);
	Insert(ll, rr, x, kr, mid+1, r);
	Push_up(k, l, r);
	return ;
}
  
void Modify(int ll, int rr, int k=1, int l=1, int r=n)
{
	if(rr <l||r< ll)	return ;
	if(ll<=l&&r<=rr)
	{
		if(tr[k].mn==tr[k].mx)
		{
			lint tmp=sqrt(tr[k].mn);
			tr[k].tmp+=tmp-tr[k].mn, tr[k].sum=(r-l+1)*tmp, tr[k].mn=tr[k].mx=tmp;
			return ;
		}
		else if(tr[k].mn+1==tr[k].mx)
		{
			lint tp1=sqrt(tr[k].mn), tp2=sqrt(tr[k].mx);
			if(tp1+1==tp2)
			{
				tr[k].tmp+=tp1-tr[k].mn, tr[k].sum+=(r-l+1)*(tp1-tr[k].mn), tr[k].mn=tp1, tr[k].mx=tp2;
				return ;
			}
		}
	}
	if(tr[k].tmp)	Push_down(k, l, r);
	Modify(ll, rr, kl, l, mid);
	Modify(ll, rr, kr, mid+1, r);
	Push_up(k, l, r);
	return ;
}
  
lint Query(int ll, int rr, int k=1, int l=1, int r=n)
{
	if(rr <l||r< ll)	return 0;
	if(ll<=l&&r<=rr)	return tr[k].sum;
	if(tr[k].tmp)	Push_down(k, l, r);
	return Query(ll, rr, kl, l, mid)+Query(ll, rr, kr, mid+1, r);
}
  
int main()
{
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d", &n, &m);
		Build();
		  
		lint d, l, r, x;
		for(int i=1; i<=n; i++)
		{
			Get_lint(x);
			Insert(i, i, x);
		}
		  
		for(int i=1; i<=m; i++)
		{
			Get_lint(d), Get_lint(l), Get_lint(r);
			if(d==1)
			{
				Get_lint(x);
				Insert(l, r, x);
			}
			else if(d==2)	Modify(l, r);
			else printf("%lld\n", Query(l, r));
		}
	}
	return 0;
}