It's a double-dip!
It feels like the biggest mistake this time was not reading T2. (The essential reason is still too much time wasted)
Race time is recorded in thegossipparticle placed after each item in a list of examples
[accoder contest link] (http://47.92.197.167:5283/contest/546）
02 Representation
Tang Poetry Title!The people who take the High Precision test are\(**\), output depth-first search solution. High Precision Multiplication 2. High Precision Reduction.
substring of a substring
The official questionnaire is poorly writtenPut it down.Ratio (used form a nominal expression)Yummy problem solving：
Meaning:\(ans_{l,r-1}\) cap (a poem)\(ans_{l+1,r}\) Includes duplicates\(ans_{l+1,r-1}\)So we used\(ans_{l,r-1} + ans_{l+1,r}-ans_{l+1,r-1}\) to transfer to get\(ans_{l,r}\) to avoid repetition, and don't forget to add the string at the end\(s[l,r]\) Himself.
magic spell
trie tree
Ideas for unofficial problem solving: (CTH (Giant's Race Time Thoughts, Better Understood)
One trie tree is constructed for each of the orthogonal and inverted orders, which are denoted as\(tr1,tr2\), then the number of all prefixes is\(tr1\) The number of nodes of the suffix is the number of\(tr2\) The number of nodes in the
But direct multiplication will obviously have duplicates, for example, two strings: abc and cd, prefix abc and suffix d can be spelled out as a string abcd, the same prefix ab and suffix cd can be spelled out as abcd, there are duplicates, consider how to subtract the duplicates.
When would there be such a duplication? It was found that if we have a situation where the last character of a prefix and the first character of a suffix are the same, it causes 1 duplication because (this prefix with the last character deleted plus this suffix) and (this prefix plus this suffix with the first character deleted) can be spelled as the same string.
note, however, that, the prefix and suffix that we are looking for that would cause duplication cannot be only one character (so that after deleting one character it becomes an empty string, but the question requires it not to be empty).
So for each of the 26 letters of the alphabet, we write down the number of characters that are the last character of their prefixes\(cntQ_{letter}\) and Number of first characters as a suffix\(cntH_{letter}\), ensuring that these prefixes and suffixes are two or more characters.
Then the answer is to multiply the number of nodes in the two trees minus\(\sum _{i=26 letters} cntQ_i\times cntH_i\)。
displayed formula
I scored 45 partial points in the last 50 minutes of the tournament (can't CRT) and thought I was going to be on the limit, but then I read into the pot to bowl RE.
Partially divided:
-
\(15pts\): Violence, every inquiry from\(1~n\) Just do the math once;
-
\(5pts\): Remember the sum of all the numbers when all the signs are the same in each query.\(s\) and the product\(f\)Inquiries\(x\) When the sign is +, the answer is\(x+s\)The answer is.\(x\times f\)Yes ^ The answer is\(x^f\)；
-
\(15 pts\)(but actually have\(25pts\)): for samples without ^, you can simply maintain them in chunks or line trees, if you ask the\(x\) When the sequence can be transformed:\((k_1x+b_1)\times k_2+b_2=k_1k_2x+k_2b_1+b_2\)So.\(k_{new}=k_1k_2,b_{new}=k_2b_1+b_2\)The total amount of each block is preprocessed in chunks.\(K\) and total\(B\) It's just as well to re-traverse the entire block when updating the\(K,B\) The query calculates all the blocks once to get the total\(k_total\) cap (a poem)\(b_total\)Substitute\(x\) Calculations.
Positive solution:
data point partitioning
The first three points are modulo too large but the data range is small for direct violence.
The other points are for particularly small moduli, and it is straightforward to maintain all points in the line tree\(x=[0,mod-1]\) The time complexity of the answer obtained when entering that point is roughly\(O(qn\log n mod)\)。
If the modulus is large but is a composite number, split the modulus into several smaller mutually prime numbers as modulus, maintain each modulus as above, and finally merge them by CRT.
End
Oh yes, CTH big brother no matter lecturing or adjusting questions are great, people are also very enthusiastic, what giant data structure ah, more than 5k code ah, are welcome to come to the CTH adjust the pinch!