This problem is quite tricky considering that it contains multiple nontrivial subproblems:

- Which posts are connected by fence segments?
- Given a cow, where along the fence is it located?
- Once we know which range of fence posts a walk will touch, how do we efficiently add one to the number of touches for each fence post within the range?

We will answer these subproblems one at a time.

**Part 1:**

Consider the set of fenceposts with a fixed $x$-coordinate (that is, all fenceposts on a given vertical line), ordered by $y$-coordinate. Note that every fencepost is the endpoint of exactly one vertical fence segment, so the fenceposts must be connected in adjacent pairs. That is, the first fencepost must be connected by a vertical fence segment to the second, the third to the fourth, and so on. The same applies to horizontal lines.

**Part 2:**

Using a dictionary of lists, we can store a list of posts along every vertical line that has a post. We do the same for each horizontal line. At the end of this, we sort each list -- for a line with $k$ posts, this takes at most $O(k \log k) \le O(k \log P)$ time, so the total amount of time taken is $O(P \log P)$. Now, we can start at an arbitrary post, and follow the fence (in either direction). As we traverse the fence, we can renumber the posts in order from $1$ to $P$, storing the mapping from old to new post numbers in a list. Also, we can record the total distance traveled so far, so that we know how far each fencepost is from post 1 (in the direction of traversal). At the end, we record the total perimeter $\ell$ of the fence.

Now, upon receiving a query consisting of two points on the fence, we first ascertain which fence segment each point is on. To do this, we check the horizontal and vertical lines it lies on, binary search for the posts it lies between, and check if it is between an odd-indexed and the following even-indexed fencepost. This binary search takes $O(\log P)$ time per cow. Thus, we can find the fence segment each cow lies on, and from this we can also determine the distance between them in the direction of traversal. If this distance is more than $\ell/2$, then the cow will actually travel in the reverse direction of traversal (or equivalently, from the second point to the first point).

**Part 3:**

From the numberings of posts, we can determine the range of posts that will be painted. This range is one contiguous interval along the fence, which may be split up into two subintervals of $[1, P]$ if it goes from $P$ to $1$. We use a difference array to store how many times each post has been painted (by the number of each post - see the analysis for Haybale Stacking). Adding 1 to every element of a range takes $O(1)$ time.

Finally, to calculate the final answers, we take prefix sums of the difference array, look up each old post number's new number, and then query its entry in the difference array. This step takes $O(\log P)$ time per step. Thus the overall running time of this algorithm is $O((N+P) \log P)$.

Benjamin Qi's C++ code:

#include <algorithm> #include <cassert> #include <iostream> #include <map> #include <optional> #include <vector> using namespace std; using ll = int64_t; using pi = pair<int, int>; template <class T> using V = vector<T>; #define f first #define s second V<ll> tot_along; // represent a position along a fence by // - the index of the last fence post you touch when walking from the first // fence post to that point (idx) // - the additional distance you walk after touching that fence post (along) struct Position { int idx, along; ll val() { return tot_along.at(idx) + along; } // dist along fence int round_up() { // next fence post if (along == 0) return idx; return idx + 1; } int round_down() { return idx; } // prev fence post }; int dist(pi a, pi b) { return abs(a.f - b.f) + abs(a.s - b.s); } V<int> index_in_ord; map<int, V<pi>> by_x, by_y; int P; // get position of a cow along the fence, if // located on a vertical segment optional<Position> lookup(const V<pi> &v, int y) { int i = lower_bound(begin(v), end(v), make_pair(y, 0)) - begin(v); if (i < size(v) && v.at(i).f == y) return Position{index_in_ord.at(v.at(i).s), 0}; if (i & 1) { pi a = v.at(i - 1), b = v.at(i); if ((index_in_ord.at(a.s) + 1) % P != index_in_ord.at(b.s)) swap(a, b); assert((index_in_ord.at(a.s) + 1) % P == index_in_ord.at(b.s)); return Position{index_in_ord.at(a.s), abs(a.f - y)}; } return nullopt; } // get position of a cow along the fence Position get_pos(pi p) { if (by_x.count(p.f)) { auto res = lookup(by_x.at(p.f), p.s); if (res.has_value()) return res.value(); } auto res = lookup(by_y.at(p.s), p.f); assert(res.has_value()); return res.value(); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N >> P; V<pi> posts(P); for (auto &[x, y] : posts) cin >> x >> y; for (int i = 0; i < P; ++i) { // fence posts for each x-coordinate, sorted by y by_x[posts[i].f].push_back({posts[i].s, i}); // fence posts for each y-coordinate, sorted by x by_y[posts[i].s].push_back({posts[i].f, i}); } V<V<int>> adj(P); // posts adjacent to each post for (auto &[_, v] : by_x) { assert(size(v) % 2 == 0); sort(begin(v), end(v)); for (int i = 0; i < size(v); ++i) adj[v[i].s].push_back(v[i ^ 1].s); } for (auto &[_, v] : by_y) { assert(size(v) % 2 == 0); sort(begin(v), end(v)); for (int i = 0; i < size(v); ++i) adj[v[i].s].push_back(v[i ^ 1].s); } { V<int> ord{0}; // indices of posts we encounter if we walk around // the fence starting from the first post while (true) { for (int x : adj[ord.back()]) { if (size(ord) > 1 && end(ord)[-2] == x) continue; ord.push_back(x); break; } if (ord.back() == 0) break; } ord.pop_back(); assert(size(ord) == P); tot_along = {0}; // distance of each post along the fence for (int i = 1; i <= P; ++i) tot_along.push_back( tot_along.back() + dist(posts.at(ord.at(i - 1)), posts.at(ord.at(i % P)))); index_in_ord.resize(P, -1); for (int i = 0; i < P; ++i) index_in_ord.at(ord[i]) = i; } V<int> cum(P + 1); // difference array auto add = [&](int l, int r) { ++cum.at(l), --cum.at(r + 1); }; // add to range in difference array while (N--) { pi f1, f2; cin >> f1.f >> f1.s >> f2.f >> f2.s; auto p1 = get_pos(f1), p2 = get_pos(f2); // position of each cow along the fence if (p1.val() > p2.val()) swap(p1, p2); const ll perim = tot_along.back(); assert(2 * (p2.val() - p1.val()) != perim); if (2 * (p2.val() - p1.val()) > perim) { add(p2.round_up(), P - 1); add(0, p1.round_down()); } else { add(p1.round_up(), p2.round_down()); } } for (int i = 1; i < P; ++i) cum.at(i) += cum.at(i - 1); // prefix sums for (int i = 0; i < P; ++i) cout << cum.at(index_in_ord.at(i)) << "\n"; }

Richard Qi's Python code (note that the positions of the fence posts are determined offline rather than online, thus avoiding the use of binary search):

from collections import defaultdict N, P = (int(x) for x in input().split()) posts = [] for i in range(P): x, y = (int(x) for x in input().split()) posts.append((x, y)) start_ends = [] for i in range(N): x1, y1, x2, y2 = (int(x) for x in input().split()) start_ends.append(((x1, y1), (x2, y2))) query_poses = [] for a, b in start_ends: query_poses.append(a) query_poses.append(b) orig_posts = posts.copy() posts = sorted(posts) query_poses = sorted(query_poses) # list of fences in order: (post a, post b) # want to map query position --> fence index, distance along that fence # for a certain x: look at all query positions with that x, posts with that x # we get: query position --> pair of posts & distance and also this post is linked to this vertical fence # query position --> pair of posts & distance and also this post is linked to this horizontal fence posts_at_x = defaultdict(list) posts_at_y = defaultdict(list) for idx, post in enumerate(posts): posts_at_x[post[0]].append(post) posts_at_y[post[1]].append(post) queries_at_x = defaultdict(list) queries_at_y = defaultdict(list) for query_pos in query_poses: queries_at_x[query_pos[0]].append(query_pos) queries_at_y[query_pos[1]].append(query_pos) vert_fence = dict() on_fence = dict() for x, x_posts in posts_at_x.items(): assert len(x_posts) % 2 == 0 post_index = 0 for i in range(0, len(x_posts), 2): vert_fence[x_posts[i]] = vert_fence[x_posts[i + 1]] = ( x_posts[i], x_posts[i + 1], ) for query in queries_at_x.get(x, []): while post_index + 2 < len(x_posts) and x_posts[post_index + 1][1] < query[1]: post_index += 2 if ( x_posts[post_index][1] <= query[1] and query[1] <= x_posts[post_index + 1][1] ): # vertical fence pos fence = (x_posts[post_index], x_posts[post_index + 1]) on_fence[query] = fence horz_fence = dict() for y, y_posts in posts_at_y.items(): assert len(y_posts) % 2 == 0 post_index = 0 for i in range(0, len(y_posts), 2): horz_fence[y_posts[i]] = horz_fence[y_posts[i + 1]] = ( y_posts[i], y_posts[i + 1], ) for query in queries_at_y.get(y, []): while post_index + 2 < len(y_posts) and y_posts[post_index + 1][0] < query[0]: post_index += 2 if ( y_posts[post_index][0] <= query[0] and query[0] <= y_posts[post_index + 1][0] ): fence = (y_posts[post_index], y_posts[post_index + 1]) on_fence[query] = fence posts = [tuple(posts_at_x.values())[0][0]] def getOther(fence, post): if post == fence[0]: return fence[1] return fence[0] for i in range(1, P): if i % 2 == 1: # horizontal fence posts.append(getOther(horz_fence[posts[-1]], posts[-1])) else: posts.append(getOther(vert_fence[posts[-1]], posts[-1])) directed_fence_to_ind = dict() for i in range(P): directed_fence_to_ind[(posts[i], posts[(i + 1) % P])] = i post_to_ind = dict() for i in range(len(posts)): post_to_ind[posts[i]] = i for post in on_fence.keys(): if on_fence[post] not in directed_fence_to_ind: on_fence[post] = on_fence[post][1], on_fence[post][0] assert on_fence[post] in directed_fence_to_ind tot_dist = 0 dist_to = [0] * P def getDist(tup_a, tup_b): return abs(tup_b[0] - tup_a[0]) + abs(tup_b[1] - tup_a[1]) for i in range(P): dist_to[i] = tot_dist tot_dist += getDist(posts[i], posts[(i + 1) % P]) def get_dist_along(query): fence = on_fence[query] ind = post_to_ind[fence[0]] return dist_to[ind] + getDist(fence[0], query) ans = [0] * P for start, end in start_ends: start_fence = on_fence[start] end_fence = on_fence[end] assert start_fence in directed_fence_to_ind and end_fence in directed_fence_to_ind start_dist = get_dist_along(start) end_dist = get_dist_along(end) if start_dist > end_dist: start, end = end, start start_dist, end_dist = end_dist, start_dist start_fence, end_fence = end_fence, start_fence if end_dist - start_dist > tot_dist - (end_dist - start_dist): start, end = end, start start_fence, end_fence = end_fence, start_fence if start_fence == end_fence and start not in start_fence and end not in end_fence: continue if start == start_fence[0]: start_ind = post_to_ind[start_fence[0]] else: start_ind = post_to_ind[start_fence[1]] if end == end_fence[1]: end_ind = post_to_ind[end_fence[1]] else: end_ind = post_to_ind[end_fence[0]] ans[start_ind] += 1 if end_ind + 1 < P: ans[end_ind + 1] -= 1 if start_ind > end_ind: ans[0] += 1 cur = start_ind for i in range(1, P): ans[i] += ans[i - 1] new_index = dict() for i in range(len(posts)): new_index[posts[i]] = i for post in orig_posts: print(ans[new_index[post]])