You are given an array of numbers( N ) (a[i]<= 10^6 && N<= 10^5 ) And 10^5 Queries. In each query You will be given.
X L R.
You have to find the how many numbers are there between L to R such that ( ( a[i] & X )== X ) . Thanks in Advance
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 12:35:52 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by khatribiru (previous revision, new revision, compare).
Suppose L = 1 and R = N for all queries. We can precalculate all answers using standart DP approach in
.
Now we want to choose some number B and divide the array to
parts of size B. For all prefixes of length kB (for integer k) we will use DP approach and store all the answers. Now we can answer one query in O(B) time (sqrt-decomposition like).
Total complexity:
. We will choose 
thus getting 
.
Not sure if it is good enough but better than O(QN).
Sorry, But Please explain the Dp solution for L=1 and R=N.
Suppose we have array A of length 2n. We want to calculate array B such that
.
We will calculate DP[k][mask] = ΣsubmaskA[submask] where the first k bits in submask is subset of those bits in mask and other m - k are equal to bits in mask. Then DP[0][mask] = A[mask] and DP[m][mask] = B[mask].
Now how to calculate this DP:
if k-th bit in mask is 0 then DP[k][mask] = DP[k - 1][mask]
if k-th bit in mask is 1 then DP[k][mask] = DP[k - 1][mask] + DP[k - 1][mask - 2k]
It is O(n2n) or
if C = 2n.
Vai, can you please share the source of the problem? The problem seems interesting :)