frank_expert's blog

By frank_expert, history, 3 months ago, In English,

Multiple cases are the features of ICPC, but not in Codeforces. Problem D[problem:1223D] is a good example to know the importance of the bound, which can save a lot of time by refreshing the exact number of elements we want.

Here is my solution. 62164071 In this solution I just use a simple way to find out the left bound index and right bound index of each number.* Then remove the repeated numbers and sort it in increasing order. Since we know numbers we do not move must show continuously, so we can use dp to find out the longest continuous subarray which meets the right bound index of smaller number < left bound index of bigger number (no crosssection).

Maybe I feel little confused about the tutorial of D. I do not like this explanation :"Let's consider all integers occurring in sequence a in descending order s1,s2,…,st (si−1>si for each i from 2 to t). If maxInd(si)<minInd(si+1) then dpi=dpi+1+1, otherwise dpi=1" . It seems to make things complicated. Why need to make s array in decreasing order? Actually I am not accustomed to thinking like this. And I don't know whether the statement "If maxInd(si)<minInd(si+1) then dpi=dpi+1+1, otherwise dpi=1" is right or not. I just sort it in increasing order and feel easy to implement dp.

The thing I want to talk about is the bound of multiple cases. "It is guaranteed that the sum of all n does not exceed 3*1e5." This statement guarantees n * q <=3*1e5. And (1≤ai≤n) is important since we will only declare "vector l(n + 1, -1), r(n + 1, -1);" but not "vector l(300000, -1), r(300000, -1)" or memset, both will cause a long time when q is big but n is small.

Hope to have more discussion of the other way of solving D without sorting.

*better way I think should be like this: for (int i = 0; i < n; i++){ if (l[a[i]] == -1){ l[a[i]] = i; v.emplace_back(a[i]); } r[a[i]] = i; }

Read more »

  • Vote: I like it
  • -17
  • Vote: I do not like it