[POI2015] POD Problem Solving
preamble
Title Link:Logan (name)。
brief outline of the topic
lengths\(n\) of a string of necklaces, each bead is\(k\) One of the colors. No.\(i\) with the first\(i-1, i+1\) The beads are adjacent to each other and the first\(n\) with the first\(1\) The stones are also adjacent to each other. Make two cuts to break the necklace into two chains. Require that beads of each color can appear in only one of the chains. Find the number of solutions (ensuring that at least one exists), and the minimum of the absolute value of the difference between the lengths of the two segments cut.
Title Analysis
As far as I know, this question has been done as follows:
- Line Tree + Incremental Method + Maximum / Bisection
- Hash + Double Pointer
- Partitioning + Dual Pointers
Write a problem statement to summarize and deepen your impression.
methodologies\(1\): Line Tree + Incremental Method + Maximum / Bisection
Consider this separately for each color. For a color that divides the ring into segments, we have to cut must intercept a part of a segment, otherwise it would cross a position and not be legal. The violent idea is to enumerate an endpoint, consider it separately for each color, and mark the legal positions. It ends up being marked\(k\) The secondary position is the legal position.
Optimization is also simple; for two adjacent locations, not much needs to be changed. Consider the incremental method, putting the endpoints\(i - 2 \sim i - 1\) move to\(i - 1 \sim i\)It's just that it's not a good idea.\(i - 1\) This position corresponds to the color\(col_{i - 1}\) Making an impact. We take the last occurrence of\(col_{i - 1}\) position to the\(i - 2 \sim i - 1\) diminish\(1\)Then put the\(i - 1 \sim i\) to the next occurrence plus\(1\), and the update is complete.
It's very much a line tree. Put the edge weights right first, i.e., use the\(i\) The value at this position represents the\(i - 1 \sim i\) This edge, modified into an interval plus. The first problem, i.e., the number of schemes is to find the interval maximum and the interval maximum number, is simple.
For the second question, in order to make the answer as small as possible, i.e. to make one of the paragraphs as close as possible to the\(\cfrac{n}{2}\)Let's find the location.\(p\)This is when the sequence is\(p\) respond in singing\(i\) is divided into three parts, and for each part find the closest occurrence of the interval's maximum value\(p\) position, it is easy to find out that it is the leftmost or rightmost position, calculate the distance, and take an answer on the\(\min\) can be done. Note that the maximum value of that segment must also be satisfied to contribute to the answer. Of course, it is also possible to bisect the leftmost or rightmost position on the line segment tree.
Also, note that some colors may only appear once in the sequence, and we won't make them illegal no matter how we slice them, so it's just a matter of special adjudication when implementing. As well as the slightly more tedious processing on the ring.
Time Complexity:\(\Theta(n \log n)\), the bottleneck is in the lineage tree, but passing away large constants, to kaka constant.
methodologies\(2\): hash + double pointer
If we analyze the problem further, it is easy to see that the ring is a cover, and we only need to find an interval in which, for each color, either all of them appear or none of them appear, and then the interception must be legal. This is because for half of the order, each color may also appear in all of them or not appear at all.
We can devise a hash function that is equivalent for every color that occurs all the time and none of the time.
hash: If a certain color appears\(c\) times, allowing the former\(c - 1\) The weights of the occurrences are set to random numbers, and the last bit is set to the previous\(c - 1\) The dissimilarity or sum of the weights of the bits. In this way, if there is an interval that completely contains or completely does not contain all the positions, for this one color, the dissimilarity and sum are both\(0\). Of course, for every color dissimilarity and sum in an interval is\(0\) This is a legal interval. Hashing, well, doesn't need to take into account the effect of different colors on each other. So the problem becomes counting how many intervals are different or sum to\(0\). Getting a prefixed dissimilar sum becomes an interval formed by taking any position between all positions where the prefixed dissimilar sum is equal. If a particular full-suffix sum appears\(x\) times, then the number of programs increases\(\cfrac{x(x - 1)}{2}\). The second issue, which is the closest\(\cfrac{n}{2}\) of the two positions, sorting and double-pointering is sufficient.
and hash: Design a hash function\(F(x)\), for a situation we define its weights as\(\sum \limits _ {i = 1} ^ {k} yzh[i] \cdot F(cnt[i])\)which\(yzh[i]\) is the random weight corresponding to each color.\(cnt[i]\) color coding\(i\) The number of times this situation has arisen.\(F(x)\) shall satisfy the requirements for\(x = 0\) and $x = $ color\(i\) The total number of occurrences in the entire sequence returns the same value for the other\(x\) Just return a random value. Wouldn't it then be the same as the heterogeneous hash subsequent processing?
Time Complexity:\(\Theta(n \log n)\), bottlenecks in sort of, but pretty quick.
methodologies\(3\): partition + double pointer
Let's first consider the simplified model. For colors that contain each other, such as\(\texttt{A} \cdots \texttt{B} \cdots \texttt{A} \cdots \texttt{B}\)We have to satisfy both the need to put in a period of\(\texttt{A}\) in it, and also to satisfy the need to put in a paragraph\(\texttt{B}\) In, then, the synthesis.\(\texttt{A}\) cap (a poem)\(\texttt{B}\) is no different, so why not merge them? It was found that with the simplified model, one color would only appear in one segment of another color.
Might want to consider a color\(\texttt{A}\)It appears in sequences that are shaped like\(\texttt{A} \cdots \texttt{A} \cdots \texttt{A}\) It might as well be recorded as\(f(\texttt{A})\)Then the segment we pick must be in the neighboring segment of the\(\texttt{A} \cdots \texttt{A}\) center. We consider each paragraph separately.
Each segment is shaped like\(\texttt{A} f(\texttt{B}) f(\texttt{C}) \cdots f(\texttt{K}) \texttt{A}\) of the problem. Clearly divided into subproblems, recursively solving each of the\(f(\texttt{B} \cdots \texttt{K})\), the next step is to consider only that the selected interval is complete with a number of consecutive subsections, such as\(f(\texttt{B})\)，\(f(\texttt{B}) f(\texttt{C})\) And so on. set up\(f(\texttt{B}) f(\texttt{C}) \cdots f(\texttt{K})\) there are\(k\) sub-problems. Then for the current contribution to the number of programs in the\(k + 1\) Two of the points are selected, where the consecutive segments formed are the selected segments, and the number of programs is\(\cfrac{(k + 1) k}{2}\)The second problem is the same as the previous one. The second problem is solved in the same way as before, with a double pointer.
The partitioning part is well taken care of, so let's talk about how to mess with pre-processing merged colors. It's not a bad idea to set\(nxt_i\) Indicates the next occurrence of\(i\) The position of the color at this location, or if not then the\(0\). Then for two colors that intersect, such a paragraph:\(j \cdots i \cdots nxt_j \cdots nxt_i\)That is to say, for\(i\)，\(\exists j \in [1, i - 1] \land nxt_j \in (i, nxt_i)\). For the previous condition, we sweep over from left to right for the current\(i\)I'm just going to consider the ones that have been swept up before.\(j\). For the latter condition, first consider a\(nxt\) A monotonic stack that is incremented from top to bottom, each time by first putting the\(nxt_j \leq i\) pops off the stack, and for the remaining elements, and the\(< nxt_i\) of each merge a bit, but the time complexity would be false. If we want to guarantee the time complexity, i.e., that each element is only added once and popped out once, we have to pop it off when we access it.
insofar as\(i\) subsequent\(k\)If\(i\) cap (a poem)\(k\) satisfy the crossover, then there is nothing wrong with doing so. But if there is\(nxt_k \leq nxt_i\) and there is a popped off\(j\)fulfillment\(nxt_k > nxt_j\), then a problem occurs, as can be seen in the figure below.
Of course, there can be more than two similar red-green relationships that can continue to be set. The result of our merge with the above monotonic stack is shown below.
It was found that, after merging, if there was still a crossing of the above legacy cases, it would cross over two adjacent segments of the same color after processing. Whereas before processing the legacy case is crossing the last occurrence of a certain color. So just process it again with the same algorithm.
As for the merging of colors, just use the concatenation set.
At this point, we have completed the solution of this problem. Time complexity\(\Theta(n \alpha (k))\). The bottleneck lies in the parallel check set.
coding
All are given detailed notes for your reference.
methodologies\(1\): Line Tree + Incremental Method + Maximum / Bisection
Having written only the most valuable version ofcodingYou can run.very slow。
methodologies\(2\): hash + double pointer
hash
coding，\(528\) ms。
and hash
coding，\(1.43\) seconds。
methodologies\(3\): partition + double pointer
beoptimal solutiontalent\(200\) milliseconds or so.
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 1 << 25;
char buf[MAX], *p = buf;
#define isdigit(x) ('0' <= x && x <= '9')
#define getchar() *p++
#define check(x) ans = min(ans, abs(n - ((x) << 1)))
inline void read(int &x) {
char ch = 0; x = 0;
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar());
}
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int n, k, val[N], ans = inf;
long long cnt;
int fa[N], rk[N];
int get(int x) { return fa[x] == x ? x : fa[x] = get(fa[x]); }
void merge(int a, int b) {
if ((a = get(a)) == (b = get(b))) return;
if (rk[a] < rk[b]) swap(a, b);
fa[b] = a;
if (rk[a] == rk[b]) ++rk[a];
}
// union (symbol ∪) (set theory)
int fir[N], lst[N], nxt[N], pre[N];
inline int trans(int x) { return x ^ n ? x + 1 : 1; } // x Next position
inline int snart(int x) { return x ^ 1 ? x - 1 : n; } // x Previous position
inline int dis(int x, int y) { return x - y + 1; } // y ~ x Such a distance.
void solve(int x) {
for (int i = trans(x); i != nxt[x]; i = trans(pre[i])) // i It's the first place this color appears.，pre[i] That's the last position.
for (int j = i; nxt[j] != i; j = nxt[j]) // Resolve each section of this color by partitioning it
solve(j);
int cnt = 0;
for (int i = trans(x), j = i; i != nxt[x]; ++cnt, i = trans(pre[i])) { // Double pointer to find proximity n/2 enhancement program
while (j != nxt[x] && dis(pre[i], j) > n >> 1) j = trans(pre[j]);
check(dis(pre[i], j));
check(dis(pre[i], nxt[snart(j)]));
}
::cnt += 1ll * cnt * (cnt + 1);
}
int stack[N], top;
inline void init() {
memset(lst, 0, sizeof (int) * (k + 1)), top = 0;
for (int i = 1; i <= n; ++i) nxt[i] = 0, nxt[lst[val[i]]] = i, lst[val[i]] = i;
for (int i = 1; i <= n; ++i) if (nxt[i]) {
while (top && nxt[stack[top]] <= i) --top;
while (top && nxt[stack[top]] <= nxt[i]) merge(val[i], val[stack[top--]]);
stack[++top] = i;
} // monotonic stack operation
for (int i = 1; i <= n; ++i) val[i] = get(val[i]); // Set directly to the merged color
}
signed main() {
fread(buf, 1, MAX, stdin);
read(n), read(k);
for (int i = 1; i <= n; ++i) read(val[i]);
for (int i = 1; i <= k; ++i) fa[i] = i;
init(), init(); // Pretreatment twice
memset(lst, 0, sizeof (int) * (k + 1));
for (int i = 1; i <= n; ++i) {
if (!fir[val[i]]) fir[val[i]] = i;
else nxt[lst[val[i]]] = i;
lst[val[i]] = i;
}
for (int i = 1; i <= n; ++i) {
if (!nxt[i]) nxt[i] = fir[val[i]];
pre[nxt[i]] = i;
} // Deal with predecessors and successors
int i = 1; do solve(i), i = nxt[i]; while (i != 1); // outermost call
printf("%lld %d", cnt >> 1, ans);
return 0;
}
postscript
I hope this article will help you familiarize yourself with each method. I also hope that I don't send this kind of question in the future ah!
This article is from Blogland and is written by:XuYueming, reproduced with a link to the original article:/XuYueming/p/18337390