[7.21-26] code source - [square count] [dictionary order minimum] [Z-type matrix]

#607. Square count

The question ： From sequence $M$ Choose from the numbers in order $N(n\le 10^6)$ A different number , Make this $N$ The dictionary order of the number is the smallest .

Answer key ：( Multiple traversal ) Code source daily question Div1 Square count

Ideas ： If the point is right $(i,j)$ Satisfy $a_i^2+a_j$ Is the perfect square , that $a_j=(x+a_i)\times (x-a_i)$ . We can enumerate $a_j$ Factor pair of , Then you can get the one that meets the conditions $a_i$ How much is the .

Here we need to use the similar optimization in the previous article . The method of sifting the factors of a number ：

1. Violent root enumeration , Time complexity $O(0\sim \sqrt{n})$
2. Ehrlich sieve optimization , Enumerate the multiples of each number , Then the number must be a factor of multiple , You can get a factor pair . Time complexity $O(n\times \log n\sim \log n)$

This problem uses the second optimization . However, if the code is implemented, there is no need to store factor pairs .

    rep(i, 1, 1000000){
    
        for(int j = i; j <= 1000000; j += i){
    
        	if(j / i - i < 0) continue;
            // (i, j / i)  That is, a pair of factor pairs 
        }
    }

AC Code ：http://oj.daimayuan.top/submission/301674

---

#608. Dictionary order is the smallest

The question ： From sequence $M$ Choose from the numbers in order $N$ A different number , Make this $N$ The dictionary order of the number is the smallest .$(n,m\le 10^6,1\le a_i\le N)$ , Data assurance $[1,N]$ Each number in the range occurs at least once .

Answer key ：( Monotonic stack ) Code source daily question Div1 Dictionary order is the smallest

Ideas ： And the last one div2 The greedy thinking of the question is very similar . First of all, we should approach the minimum lexicographic order , That is to say $[1,N]$ Original arrangement . So we maintain a stack , Sweep backward , Pop up all numbers larger than the new ones at the end of the stack , Put the new number in . This can greedily move closer to the smallest dictionary order . But our decision may have problems , If there is no element equal to the number to pop up , There will be no solution . therefore , Preprocess whether there is a number after each number , If there are several, the current number can pop up ; Otherwise, it cannot pop up , Because it will cause no solution .

AC Code ：http://oj.daimayuan.top/submission/292414

---

#614. “Z” Type matrix

The question ： Ask how many submatrixes of a matrix satisfy the matrix shape z .

Answer key ：( offline / Tree array ) Code source daily question Div1“Z” Type matrix

Ideas ： The endpoint of the enumeration matrix is $O(n^4)$ Of . How to optimize ？ We solve on the diagonal . For each diagonal , Every point above has a left line 、 Right line , We sweep diagonals from top right to bottom left , In the process of scanning, maintain according to the length of the left line , Save to the tree array . Because every left-hand line has a life cycle , We mark the end time of each left line . For the right line , What can match the current right-hand line must be the left-hand line that is still alive with a length less than or equal to the right-hand line , Just query the tree array .

AC Code ：http://oj.daimayuan.top/submission/301109