Solution of round #180 Div 1 Problem E -- Mystic carvings

For any three lines, they can intersect in one of the following 5 ways:

The problem is asking for the number of Type 2 or Type 5. Some of these configs are easy to count (e.g. Type 1), some are not. To count the number of Type 1, we can exhaust the middle line with index *i*, and count the number of lines on the right of the middle line (let it be *x*_{i}) and on the left of the middle line (let it be *y*_{i}), then the number of Type 1 with that middle line is given by *x*_{i}*y*_{i}. There are several methods to calculate *x*_{i} efficiently. One of them is to process the endpoints in counter clockwise order (let the current endpoint be *k*), and use a segment tree or binary indexed tree to keep track of the number of lines (*a*_{i}, *b*_{i}), *a*_{i} < *b*_{i} with *l* ≤ *a*_{i} < *b*_{i} ≤ *k* for different *l*. Let *j* be the line with *b*_{j} = *k*, then to find the number of lines with *a*_{j} < *a*_{i} < *b*_{i} < *b*_{j}, we just need to query the count at *a*_{j}, then update the binary indexed tree by adding one to the position *a*_{j}. In the actual implementation, we need to consider that the endpoints are wrapped circularly as well.

Unfortunately, Type 2 and Type 5 are the difficult ones. But we are only asked to find the total number of Type 2 and Type 5, which is (number of triples of lines) — (number of Type 1, 3 and 4). The problem then reduces to finding the total number of Type 3 and 4 (namely "We cannot give a 囧 without an XD and a HA"). Note that Type 3 and 4 shares a characteristic that two of the lines (the X in Type 3, and the two vertical lines in Type 4) has exactly one intersection with one of the other two lines. Therefore we can find the number of Type 3 and 4 by iterating through the lines, then count the number of lines on the right (*x*_{i}), on the left (*y*_{i}), and intersecting the considered line (*z*_{i} = *n* - 1 - *x*_{i} - *y*_{i}), and give the number of Type 3 and 4 as the sum of *z*_{i}(*x*_{i} + *y*_{i}). After removing double counting, we can get the answer.

I can't load the image in this Blog .