关于
rss
哈天下凌绝顶
哈凌大侠的博客
欢迎访问 哈天下凌绝顶!
主页
共同分享
回首展望
应用程序
犄角旮旯
生活感悟
算法珠玑
解题报告
SPOJ UNTITLE1
发布时间 八.01, 2011 分类 解题报告
很久没有写题解了，为了攒点rp，写一篇吧……
题目大意：给你一个序列（N<=50000），给某个区间的数都加上一个值，询问尾部在x～y的最大前缀和。
那么我们先根号N分段，每一段维护一个凸包支持询问这一段的最大前缀和。
即Max P=sum[i]+add*i，i是这个区间的第i个位置，sum[i]表示这个区间前i项和，add表示这个区间整个增加的值。
那么设y=sum[i],x=i，y=-add*i+P，add在询问时是一个常量，我们可以想象有一个斜率为-add的直线从上往下降落，最先碰到的点就是最大化P的最优解。那么很显然要维护一个上凸包，询问时二分碰到的点就可以了。
总结一下：对于修改操作，中间的段直接修改标号，两边的直接修改sum数组求凸包。注意求凸包时按照x递增的顺序加点，使用graham维护可以不用排序。对于询问操作，两边直接暴力枚举，中间的就用前面的方法二分找出第一个斜率小于-add的直线，取左端点为当前候选答案就可以了。
?[Copy to clipboard]View Code CPP1
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long Int;
const Int MAXN=100005;
const Int MAXM=1000;//ceil(sqrt(MAXN));
const Int oo=~0ull>>1;
#define pb push_back
struct Point
{
Int x,y;
Point (Int _x=0,Int _y=0):x(_x),y(_y){}
bool operator < (const Point &b) const
{
return x<b.x || (x==b.x && y<b.y);
}
Int operator * (const Point &b) const
{
return (Int)x*b.y-(Int)b.x*y;
}
Point operator - (const Point &b) const
{
return Point (x-b.x,y-b.y);
}
}P[MAXM];
Point *hull[MAXM];
struct Block
{
Int l,r,size,add,sum[MAXM],ind[MAXM];
double slope[MAXM];
Int top;
void update()
{
for(Int i=0;i<size;i++)
P[i].x=i+1,P[i].y=sum[i+1];
gethull(size);
}
Int getsum(Int t=-1)
{
if (t==-1)
return sum[size]+add*size;
else
return sum[t]+add*t;
}
void addval(Int x,Int y,Int k)
{
x=x-l+1,y=y-l+1;
for(Int i=x,j=k;i<=y;i++,j+=k)
sum[i]+=j;
for(Int i=y+1,j=(y-x+1)*k;i<=size;i++)
sum[i]+=j;
if (add!=0)
{
for(Int i=1,j=add;i<=size;i++,j+=add)
sum[i]+=j;
add=0;
}
update();
}
Int getmax()
{
Int pos=lower_bound(slope,slope+top,add)-slope;
return getsum(ind[pos]);
}
void gethull(Int size)
{
if (size>=2)
{
hull[0]=&P[0];
hull[1]=&P[1];
top=2;
for(Int i=2;i<si