ZJOI2018 胖
题意：
题目传送门
题解：
时隔一年才来做这道题的我真是太菜了…… 我们将修建的道路所连接的点称作关键点，那么考虑每一条道路能够更新的点一定是一段连续的区间\([L, R]\)，\(\sum_i R_i - L_i + 1\)就是题目的答案。于是我们考虑如何求出每一个关键点更新的区间\([L, R]\)。很容易想到的是二分，由于右端点与左端点的方法类似，我们就以左端点为例。
假设当前二分到的点为\(p\)，那么如果\(p\)会被当前关键点\(x\)更新到，那么一定满足\([p - d, p + d]\)（\(d\)为\(x\)与\(p\)的下标差值，即\(| x - p |\)）这个区间内没有关键点到达\(p\)的距离比\(x\)更小。如果不满足，那么更新这个点\(p\)的一定是另一个关键点。于是我们转而考虑如何维护区间最小值，可以用线段树，但是常数太大，我们可以用\(ST\)表来完成。每次预处理为\(O(k log(k))\)，查询\(O(1)\)，这样总复杂度为\(O(k log(k))\)。
另外还要考虑到如果\([p - d, p + d]\)这个区间关键点到达\(p\)的距离等于\(x\)到\(p\)的距离时，这个贡献只能算\(1\)次，显然如果两个关键点到\(p\)的下标差值不同，那么贡献一定是算在下标差值小的关键点上，如果这个值也相同，那么随便选一个都行，只要答案统计时不重复就行了。
Code
#pragma GCC optimize (2,"inline","Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 50;
const ll INF = 1e16;
int n, m, k;
int w[N], Lg[N];
ll sum[N], st1[N][21], st2[N][21], lmn[N], rmn[N];
struct edge {
int pos, l;
bool operator < (const edge &rhs) const {
return pos < rhs.pos;
}
}E[N];
int Min(int x, int y) {
if(rmn[x] == rmn[y]) return min(x, y);
return rmn[x] < rmn[y] ? x : y;
}
int Max(int x, int y) {
if(lmn[x] == lmn[y]) return max(x, y);
return lmn[x] > lmn[y] ? x : y;
}
int GetMn(int l, int r) {
int G = Lg[r - l + 1];
return Min(st2[l][G], st2[r - (1 << G) + 1][G]);
}
int GetmMx(int l, int r) {
int G = Lg[r - l + 1];
return Max(st1[l][G], st1[r - (1 << G) + 1][G]);
}
void Init() {
sort(E + 1, E + 1 + k);
for(int i = 1; i <= k; i++) {
lmn[i] = sum[E[i].pos] - E[i].l; rmn[i] = sum[E[i].pos] + E[i].l;
st1[i][0] = st2[i][0] = i;
}
for(int j = 1; (1 << j) <= k; j++) {
for(int i = 1; i + (1 << j) - 1 <= k; i++) {
st1[i][j] = Max(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
st2[i][j] = Min(st2[i][j - 1], st2[i + (1 << (j - 1))][j - 1]);
}
}
}
int Judge(int a, int b, int p) {
ll len1 = E[a].l + abs(sum[p] - sum[E[a].pos]), len2 = E[b].l + abs(sum[p] - sum[E[b].pos]);
if(len1 != len2) return len1 < len2 ? a : b;
int dis1 = abs(E[a].pos - p), dis2 = abs(E[b].pos - p);
if(dis1 != dis2) return dis1 < dis2 ? a : b;
return min(a, b);
}
int Check(int a, int p) {
int dis = abs(E[a].pos - p), dom = a;
edge e1 = (edge) { p, 0 }, e2 = (edge) { p + dis, 0 }, e3 = (edge) { p - dis, 0};
int l = lower_bound(E + 1, E + 1 + k, e3) - E, r = upper_bound(E + 1, E + 1 + k, e2) - E - 1, mid = upper_bound(E + 1, E + 1 + k, e1) - E - 1;
if(l <= mid) dom = Judge(dom, GetMx(l, mid), p);
if(mid < r) dom = Judge(dom, GetMn(mid + 1, r), p);
return dom == a;
}
void Solve() {
ll ans = 0;
for(int i = 1; i <= k; i++) {
int l = 1, r = E[i].pos, ansl = E[i].pos, ansr = E[i].pos;
while(l <= r) {
int mid = (l + r) >> 1;
if(Check(i, mid)) r = mid - 1, ansl = mid;
else l = mid + 1;
}
l = E[i].pos, r = n;
while(l <= r) {
int mid = (l + r) >> 1;
if(Check(i, mid)) l = mid + 1, ansr = mid;
else r = mid - 1;
}
ans += ansr - ansl + 1;
}
printf("%lld\n", ans);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 2; i <= n; i++) Lg[i] = Lg[i >> 1] + 1;
for(int i = 2; i <= n; i++) scanf("%d", &w[i]), sum[i] = sum[i - 1] + w[i];
for(int i = 1; i <= m; i++) {
scanf("%d", &k);
for(int j = 1; j <= k; j++) scanf("%d%d", &E[j].pos, &E[j].l);
Init(); Solve();
}
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/10562586.html
相关资源：JAVA上百实例源码以及开源项目
