赌书消得泼茶香 2017-10-15
有一只猴子,他生活在一个环形的公园里。有n棵树围绕着公园。第i棵树和第i+1棵树之间的距离是 di ,而第n棵树和第一棵树之间的距离是 dn 。第i棵树的高度是 hi 。
这只猴子每天要进行晨跑。晨跑的步骤如下:
· 他先选择两棵树;
· 然后爬上第一棵树;
· 再从第一棵树上下来,接着围绕着公园跑(有两个可能的方向)到第二棵树,然后爬上第二棵树;
· 最后从第二棵树上下来。
但是有一些小孩会在连续的一些树上玩耍。所以猴子不能经过这些树。
比如现在猴子选择的第x棵和第y棵树,那么该早晨他消耗的能量是 2(hx+hy)+dist(x,y) 。由于某一条路径是被小孩子占据的,所以他只能跑另外一条,因此 dist(x,y) 是确定的。
现在给出第i天,孩子们会在第 ai 棵树和 bi 棵树之间玩耍。具体的,如果 ai≤bi ,那么孩子玩耍的区间就是 [ai,bi] ,否则孩子玩耍的区间就是 [ai,n]⋃[1,bi] 。
请帮助这只猴子找出两棵树,让他晨跑的时候他能够消耗最大的能量。
Input
单组测试数据。
第一行有两个整数 n 和m (3≤n≤10^5, 1≤m≤10^5),表示树的数目,以及猴子跑步的天数。
第二行有n个整数d1,d2,...,dn (1≤di≤10^9),表示树之间的距离。
第三行有n个整数h1,h2,...,hn (1≤hi≤10^9),表示树的高度。
接下来m行,第一行有两个整数 ai和bi (1≤ai,bi≤n),描述每一天孩子玩耍的区间。输入保证至少有两个棵树孩子不会进行玩耍,这样猴子每天都可以晨跑了。
Output
对于每一天,输出猴子消耗的最大能量。
Input示例
样例输入1
5 3
2 2 2 2 2
3 5 2 1 4
1 3
2 2
4 5
Output示例
样例输出1
12
16
18
设d[i]为i点距离的前缀和,h[i]为原题中的2*h[i](因为要上一次树、下一次树),那么 i, j (i > j)两点间的价值可以表示为 d[i] - d[j] + h[i] + h[j], 设 A[i] = d[i] + h[i], B[j] = d[j] - h[j], 则价值就是 A[i] - B[j],在可选区间中选最大的A[i]减去最小的B[j]即可。
但需要考虑:如果使A[i]最大的i和使B[j]最小的j相同怎么办? 这时候,i和j中只能选择一个,然后分别在剩下的可用的位置中选择另一个即可。
具体实现我使用的是st表,线段树也可以……但是st表写起来短啊2333
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define INF 0x7fffffffffffffff #define space putchar(' ') #define enter putchar('\n') template <class T> bool read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; else if(c == EOF) return 0; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; return 1; } template <class T> void write(T x){ if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int N = 200005; ll n, m, d[N], h[N], A[N], B[N]; ll mi[N][20], ma[N][20], lg[N]; ll MAX(int a, int b) { return A[a] > A[b] ? a : b; } ll MIN(int a, int b) { return B[a] < B[b] ? a : b; } void init(){ A[0] = -INF, B[0] = INF; for(ll i = 1, sum = 0; i <= 2 * n; i++){ sum += d[i]; A[i] = sum + h[i]; B[i] = sum - h[i]; ma[i][0] = mi[i][0] = i; } for(ll i = 0, j = 1; j <= 2 * n; j++) lg[j] = 1 << (i + 1) == j ? ++i : i; for(int j = 1; (1 << j) <= 2 * n; j++) for(int i = 1; i + (1 << j) - 1 <= 2 * n; i++){ ma[i][j] = MAX(ma[i][j - 1], ma[i + (1 << (j - 1))][j - 1]); mi[i][j] = MIN(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]); } } ll getma(int l, int r){ if(l > r) return 0; int j = lg[r - l + 1]; return MAX(ma[l][j], ma[r - (1 << j) + 1][j]); } ll getmi(int l, int r){ if(l > r) return 0; int j = lg[r - l + 1]; return MIN(mi[l][j], mi[r - (1 << j) + 1][j]); } ll query(int l, int r){ int x = getma(l, r), y = getmi(l, r); if(x != y) return A[x] - B[y]; int another_x = MAX(getma(l, x - 1), getma(x + 1, r)); int another_y = MIN(getmi(l, x - 1), getma(x + 1, r)); return max(A[another_x] - B[y], A[x] - B[another_y]); } int main(){ read(n), read(m); for(int i = 1; i <= n; i++) read(d[i % n + 1]), d[i % n + 1 + n] = d[i % n + 1]; for(int i = 1; i <= n; i++) read(h[i]), h[i] <<= 1, h[i + n] = h[i]; init(); while(m--){ int a, b; read(a), read(b); if(a <= b) printf("%lld\n", query(b + 1, n + a - 1)); else printf("%lld\n", query(b + 1, a - 1)); } return 0; }