首页 > 代码库 > [BZOJ2388]旅行规划
[BZOJ2388]旅行规划
[BZOJ2388]旅行规划
试题描述
OIVillage是一个风景秀美的乡村，为了更好的利用当地的旅游资源，吸引游客，推动经济发展，xkszltl决定修建了一条铁路将当地n个最著名的经典连接起来，让游客可以通过火车从铁路起点（1号景点）出发，依次游览每个景区。为了更好的评价这条铁路，xkszltl为每一个景区都哦赋予了一个美观度，而一条旅行路径的价值就是它所经过的景区的美观度之和。不过，随着天气与季节的变化，某些景点的美观度也会发生变化。
xkszltl希望为每位旅客提供最佳的旅行指导，但是由于游客的时间有限，不一定能游览全部景区，然而他们也不希望旅途过于短暂，所以每个游客都希望能在某一个区间内的车站结束旅程，而xkszltl的任务就是为他们选择一个终点使得旅行线路的价值最大。可是当地的景点与前来观光的旅客实在是太多了，xkszltl无法及时完成任务，于是找到了准备虐杀NOI2011的你，希望你能帮助他完成这个艰巨的任务。
输入
第一行给出一个整数n，接下来一行给出n的景区的初始美观度。
第三行给出一个整数m，接下来m行每行为一条指令：
1. 0 x y k：表示将x到y这段铁路边上的景区的美观度加上k；
2. 1 x y：表示有一名旅客想要在x到y这段（含x与y）中的某一站下车，你需要告诉他最大的旅行价值。
输出
对于每个询问，输出一个整数表示最大的旅行价值。
输入示例
5 1 8 -8 3 -7 3 1 1 5 0 1 3 6 1 2 4
输出示例
9 22
数据规模及约定
对于20%的数据，n，m≤3000；
对于40%的数据，n，m≤30000；
对于50%的数据，n，m≤50000；
另外20%的数据，n，m≤100000，修改操作≤20；
对于100%的数据，n，m≤100000。
题解
这题就是让维护区间最大前缀和（前缀和左端点为 1）。那么我们不妨就维护这个前缀和。
那么区间 [l, r] 的修改操作就变成了从第 l 个数开始，依次给每个位置加上 k, 2k, 3k, ... , (r-l+1)k。
查询操作就是询问区间最大值。
我们对序列分块。考虑修改操作，对于整块的我们打两个懒标记：addv[i] 表示这一块中的所有数增加 addv[i] 的值；K[i] 表示这一块中增加的等差数列的公差，即这一块中的元素在加完 addv[i] 后依次要加上 K[i], 2K[i], 3K[i], ... , siz · K[i]。再想想询问如何处理，对于整块的询问相当于就是找到 max{ S[x] + addv[i] + (x - st[i] + 1)K[i] | st[i] ≤ x ≤ en[i] }（st[i] 和 en[i] 表示第 i 个块的起始和终点位置），我们发现如果把 (x - st[i] + 1, S[x]) 当作坐标系上的点，那么询问就相当于用一条斜率为 -K[i] 的直线去碰那个点，要求找到最大的截距，解决这个问题维护凸包即可。
注意当 K[i] 和 addv[i] 变化时（即整块都被修改），不需要重新维护凸包形态（想一想，为什么）。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
return x * f;
}
#define maxn 100010
#define maxbl 320
#define oo (1ll << 60)
#define LL long long
int n, cb, st[maxbl], en[maxbl], blid[maxn];
LL Sa[maxn], addv[maxbl], K[maxbl], cp[maxbl];
struct Vec {
LL x, y;
Vec() {}
Vec(LL _, LL __): x(_), y(__) {}
Vec operator + (const Vec& t) const { return Vec(x + t.x, y + t.y); }
Vec operator - (const Vec& t) const { return Vec(x - t.x, y - t.y); }
LL operator ^ (const Vec& t) const { return x * t.y - y * t.x; }
} poly[maxbl][maxbl];
void pushdown(int bl) {
for(int i = st[bl]; i <= en[bl]; i++) Sa[i] += addv[bl] + K[bl] * (i - st[bl] + 1);
addv[bl] = K[bl] = 0;
return ;
}
void build_poly(int bl) {
cp[bl] = 0;
for(int i = st[bl]; i <= en[bl]; i++) {
while(cp[bl] > 1 && (poly[bl][cp[bl]] - poly[bl][cp[bl]-1] ^ Vec(i - st[bl] + 1, Sa[i]) - poly[bl][cp[bl]]) >= 0) cp[bl]--;
poly[bl][++cp[bl]] = Vec(i - st[bl] + 1, Sa[i]);
}
return ;
}
void update(int ql, int qr, int k) {
if(blid[ql] == blid[qr]) {
int b = blid[ql];
pushdown(b);
for(int i = ql; i <= qr; i++) Sa[i] += (LL)k * (i - ql + 1);
for(int i = qr + 1; i <= en[b]; i++) Sa[i] += (LL)k * (qr - ql + 1);
build_poly(b);
}
else {
int b = blid[ql];
pushdown(b);
for(int i = ql; i <= en[b]; i++) Sa[i] += (LL)k * (i - ql + 1);
build_poly(b);
b = blid[qr];
pushdown(b);
for(int i = st[b]; i <= qr; i++) Sa[i] += (LL)k * (i - ql + 1);
for(int i = qr + 1; i <= en[b]; i++) Sa[i] += (LL)k * (qr - ql + 1);
build_poly(b);
for(int i = blid[ql] + 1; i <= blid[qr] - 1; i++) {
addv[i] += (LL)k * (st[i] - ql);
K[i] += k;
}
}
for(int i = blid[qr] + 1; i <= cb; i++) addv[i] += (LL)k * (qr - ql + 1);
return ;
}
LL getans(int bl, int p) {
if(p > cp[bl]) return -oo;
return poly[bl][p].x * K[bl] + poly[bl][p].y + addv[bl];
}
LL query(int ql, int qr) {
LL ans = -oo;
if(blid[ql] == blid[qr]) {
int b = blid[ql];
pushdown(b); build_poly(b);
for(int i = ql; i <= qr; i++) ans = max(ans, Sa[i]);
return ans;
}
int b = blid[ql];
pushdown(b); build_poly(b);
for(int i = ql; i <= en[b]; i++) ans = max(ans, Sa[i]);
b = blid[qr];
pushdown(b); build_poly(b);
for(int i = st[b]; i <= qr; i++) ans = max(ans, Sa[i]);
for(int i = blid[ql] + 1; i <= blid[qr] - 1; i++) {
int l = 1, r = cp[i];
while(l < r) {
int mid = l + r >> 1;
if(getans(i, mid) <= getans(i, mid + 1)) l = mid + 1;
else r = mid;
}
ans = max(ans, getans(i, l));
}
return ans;
}
int main() {
n = read();
for(int i = 1; i <= n; i++) Sa[i] = Sa[i-1] + read();
int m = sqrt(n + .5);
for(int i = 1; i <= n; i++) {
int bl = (i - 1) / m + 1; cb = max(cb, bl);
blid[i] = bl;
if(!st[bl]) st[bl] = i; en[bl] = i;
}
for(int i = 1; i <= cb; i++) build_poly(i);
int q = read();
while(q--) {
int tp = read();
if(!tp) {
int ql = read(), qr = read(), k = read();
update(ql, qr, k);
}
else {
int ql = read(), qr = read();
printf("%lld\n", query(ql, qr));
}
}
return 0;
}
分块打起来好爽 ^_^
[BZOJ2388]旅行规划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。