USACO16JAN 割草场 Mowing the Field

本文约定

S\left\vert S\right\vert:集合SS的元素数量

{xp(x)}\{x\vert p(x)\}:符合p(x)p(x)的元素组成的集合

\land:逻辑与

\lor:逻辑或

思路

首先根据题意(以及官方题解),一个交点应该只会出现一次,所以只要考虑时间在范围外的交点数即可。也就是说,与第ii条竖直线段相交的线段

ci={jxjl<xi<xjryil<yj<yirtitjT}c_i=\left\vert\{j\vert x_j^l<x_i<x_j^r\land y_i^l<y_j<y_i^r\land\left\vert t_i-t_j\right\vert\ge T\}\right\vert

当然,这个可以O(N2)O(N^2)枚举。如果把绝对值拆开,就变成tj+Ttitj+Tt_j+T\le t_i\le t_j+T,这时就变成经典的三维偏序问题了,可以在O(Nlog2N)O(N\log^2N)内解决。

我们可以把竖直线段作为查询操作。按照x坐标排序,用扫描线维护水平线段ii,保存点(ti,yi)(t_i,y_i)。对于竖直线段ii,查询{(tj,yj)(tjtiTtjti+T)(yil<yj<yir)}\left\vert\{(t_j,y_j)\vert(t_j\le t_i-T\lor t_j\ge t_i+T)\land(y_i^l<y_j<y_i^r)\}\right\vert即为答案。注意,线段端点相交不计入答案,在处理x坐标时也要注意。

至于数据结构,我用了官方的树状数组套线段树。

代码

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005, LOGN = 32;
struct node
{
int sum, ls, rs;
} tree[N * LOGN * 4];
int cc;
//线段树
void modify(int &id, int l, int r, int x, int val)
{
if (!id)
id = ++cc;
if (l == r)
tree[id].sum += val;
else
{
int mid = (l + r) / 2;
if (x <= mid)
modify(tree[id].ls, l, mid, x, val);
else
modify(tree[id].rs, mid + 1, r, x, val);
tree[id].sum = tree[tree[id].ls].sum + tree[tree[id].rs].sum;
}
}
int query(int id, int l, int r, int L, int R)
{
if (!id)
return 0;
if (L <= l && R >= r)
return tree[id].sum;
int mid = (l + r) / 2;
if (R <= mid)
return query(tree[id].ls, l, mid, L, R);
if (L > mid)
return query(tree[id].rs, mid + 1, r, L, R);
return query(tree[id].ls, l, mid, L, R) + query(tree[id].rs, mid + 1, r, L, R);
}
int n, t;
//树状数组
struct BIT
{
int root[N];
void modify(int t, int x, int val)
{
for (; t <= n; t += t & -t)
::modify(root[t], 0, 1e9, x, val);
// ^ 全局名称空间
}
int query(int t, int l, int r)
{
int ans = 0;
for (; t; t -= t & -t)
ans += ::query(root[t], 0, 1e9, l, r);
return ans;
}
} T;
struct event
{
int x, y, t, val;
event() {}
event(int x, int y, int t, int val) : x(x), y(y), t(t), val(val) {}
bool operator<(const event &rhs) const
{
return x < rhs.x;
}
} E[N * 2];
struct query_t
{
int x, yl, yr, t;
query_t() {}
query_t(int x, int yl, int yr, int t) : x(x), yl(yl), yr(yr), t(t) {}
bool operator<(const query_t &rhs) const
{
return x < rhs.x;
}
} Q[N];
int main()
{
ios::sync_with_stdio(false);
int px, py;
cin >> n >> t >> px >> py;
int en = 0, qn = 0;
for (int i = 2; i <= n; i++)
{
int x, y;
cin >> x >> y;
if (y == py)
{
E[++en] = event(min(px, x) + 1, y, i, 1);
E[++en] = event(max(px, x), y, i, -1);
//本来应该为[l,r+1],去除端点为[l+1,r]
}
else
Q[++qn] = query_t(x, min(py, y) + 1, max(py, y) - 1, i);
px = x;
py = y;
}
sort(E + 1, E + en + 1);
sort(Q + 1, Q + qn + 1);
long long ans = 0;
for (int i = 1, j = 1; i <= qn; i++)
{
for (; j <= en && E[j].x <= Q[i].x; j++)
T.modify(E[j].t, E[j].y, E[j].val);
if (Q[i].t - t > 0)
ans += T.query(Q[i].t - t, Q[i].yl, Q[i].yr);
if (Q[i].t + t <= n)
ans += T.query(n, Q[i].yl, Q[i].yr) - T.query(Q[i].t + t - 1, Q[i].yl, Q[i].yr);
}
cout << ans << endl;
return 0;
}