Educational things (part 1)

general
,
1

Soon the Feb long challenge starts, and I decided to share the most amazing things for me in this blog:

**1.**Min_25’s blog: https://min-25.hatenablog.com the ideas are of high-level there
**2.**The k-th ordered statistics queries with an update of the next type:
l r x y

  For i=l..r
    
       If a[i] == x
    
          a[i] = y
        
    
    a[i], y <= N

**3.**My problem idea:

Given a permutation of length N and Q queries to it:

  1. Swap(p[x], p[y])
  2. Tell how many pairs of elements between l and r have differs with the value equals to K

NOTES-

Problem 1. K is the same for all queries

Problem 2. K is different for each query
11 Likes
2

Constraints, please? Although it’s meant for discussion.
But as of now, I know O(Q*N) soln :stuck_out_tongue:

1 Like
3

Let’s have 3e5 everywhere

1 Like
4

Bump.

Random Quote -
“We are all born ignorant, but one must work hard to remain stupid.” ~ Benjamin Franklin

3 Likes
5

The complexity of the solution for the second problem O((N + Q) sqrt(N))

1 Like
6

So far… The solution for the second problem is SQRT-decomposition :slight_smile:

Let’s split our array into \sqrt{N} blocks, each of the length \sqrt{N}. And for each block let’s store own sqrt-decomposition. Do you see how the queries and updates can be processed?

7

The third problem:

Let’s notice that all elements are unique, what it gives us

Subproblem 1:

K is fixed, the answer is no more than N, we can store the values = 1 in the points (X, Y), where |p[x] - p[y]| = K. Do you see how to do updates and queries in quick O(log^2) time?
Consider the summation on sub-matrix [L..R, L..R]

Subproblem 2:

Imagine we solve the problem without updates, then if we somehow know all the elements in the range l..r then we can find the answer by (set \& (set < < k)).count() if you’re familiar with C++ bitset. We can find the set with the Mo’s algorithm, don’t forget that there is boosted Mo’s algorithm with Hilbert order.

And updates can be handled with Mo’s algorithm with updates:

So, the total complexity is O(Q (N^(2/3) + N/64)), I haven’t seen such complexities before :slight_smile:

Feel free to ask questions, I can add links to the algorithms I mentioned. Also, to explain the things more clearly.

8

I’m stupid :slight_smile:

@whzzt suggested simple O(Q sqrt(N) + Q N / 64) solution for the third problem.

Let’s store the bitsets of all elements on the prefixes, i.e. the set of first \sqrt{n} elements, the first 2*\sqrt{n} elements and so on.

When you need to answer the query, just take 2 bitsets, operate with not more than 2*\sqrt{n} elements. Fir the update we should go with updating all of the prefix bitsets.

So, query is K*(the \ size \ of \ block)+N/64, and update is N/K,

We can find the optimal K:

K+N/64 \approx N/K

Better to choose K \approx 64-sqrt{N}