Could someone please help me with this problem? I've been thinking about it for over a week but I still have no idea how to solve it. Thank you

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | ksun48 | 3575 |

4 | Radewoosh | 3562 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3406 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | YouKn0wWho | 201 |

3 | Um_nik | 197 |

4 | Errichto | 181 |

4 | sus | 181 |

6 | awoo | 179 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

8 | SecondThread | 171 |

10 | Ashishgup | 170 |

Square root decomposition / Mo's algorithm is a known method used to solve a large variety of problems in O(N sqrt(N)). However, it is not used all that often by more experience programmers because we can use a BIT or segment tree instead and attain logarithmic time. However, I've recently stumbled upon problem which I only know how to solve using sqrt decomposition.

You are given an array A with N elements (indexing starts from 1). You need to answer M queries of the type: "Given three indices l r k, find the number of elements which appear exactly k times in the subarray A[l], A[l+1], ..., A[r].

Input:

```
11 3
1 2 4 3 2 5 6 4 5 2 1
1 6 2
2 7 3
4 11 1
```

Output:

```
1
0
4
```

I've tried implementing online/offline solutions using persistent segments and binary indexed trees, but to no avail. Is there a O(N logN) or O(N log^2 N) solution for this specific problem?

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/27/2021 17:33:22 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|