Well, counting down again, just signed a T2, 100 pts.
T1 I saved the same color, each color to find out enumeration to choose which two seats are not legal matrix of the upper left and lower right, if found the matrix of the lower left and upper right are also the same, then this matrix is indeed not legal, subtracted, but judgment of the lower left and upper right when the writing is too fast (the last fifteen minutes before starting to play this violence) less judgment and the current color is the same or not, hung up 80 pts,!
In total, I hit these two questions a hang a whole lot.
Push Down Ramblings (the password is as big as the dish)./YuenYouth/p/18438103
multi-colored
A glance is very sign ah, but will not. Thought it would be nice to reverse the process to find the number of matrices where all four points are the same, but how do I find it?
Positive solution:
Obviously the answer is really the total number of matrices minus the number of matrices with all four vertices the same.
For the number of matrices with all four vertices the same, you can enumerate the rows where the top and bottom edges of the matrix are located, and then enumerate the rows and columns, and for each color open a bucket to store these two rows and columns in the position of the number of positions of this color, and the statistical answer is good.
Staggered travel
Signed and signed!
Positive solution:
A city in a zone\([l,r]\) Inside is crowded, in fact it is in the first\(l\) Creating a new crowded city
The obvious answer is to ask\([s,t]\) The product of the number of cities that can be visited on each day of the interval.
nevertheless, it was found that\(t\) The data range of the\(10^9\)It's hard not to.\(T\) (negative prefix)\(RE\), but then found that the number of modifications was\(10^6\) That is to say, the contribution to the answer is the same between every two neighboring modification intervals, then we can sequentially enumerate the modification positions fast, and calculate the contribution to the answer between modification intervals by the speed power.
line segment tree
The interval dp, which is not thought to be (
found\(f_{i,j}\) means that the line segment tree leaves only\([i,j]\) intervals, asking for the number of intervals used.
work out\(s_{i,j}\) denotes the inclusion interval\([i,j]\) The number of queries that enumerate the\([i,j]\) cut-off point (math.)\(k\)There are transfers:\(f_{i,j}<-f_{i,k}+f_{k+1,j}-s_{i,j}\)。
insofar as\(s_{i,j}\)For each query interval, the simple tolerance\([l,r]\) have sb do sths_{l,r}++and then tolerate the transfer.\(s_{i,j}=s_{i,j}+s_{i-1,j}+s_{i,j+1}-s_{i-1,j+1}\)Interval\([i,j]\) will be determined by the left interval\([i-1,j]\) and Right Interval\([i,j+1]\) Transferred from and subtracted from duplicate intervals\([i-1,j+1]\) 。
quantum tunnelling problem