Hello everyone, I came up with this problem and I can't figure a solution out. I don't know if it has appeared before.
You are given a matrix of size n × m. Answer two types of queries:
- 1 k i1 i2 ... ik: Set the active set to {i1, i2, ..., ik}.
- 2 x: What is the value of ai1, x + ai2, x + ... + aik, x, where i1, i2, ..., ik are the current elements in the active set?
There are less than n queries of type 1, and less than m queries of type 2 between a pair of queries of type 1.
1 ≤ n, m ≤ 2000, however solutions with any reasonable complexity are welcome.
Also, if a query of type 1 appears for the i-th time, 1 ≤ k ≤ i, and all the indices in the query do not exceed i.
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 09:44:46 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).
Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).
Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).
Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).
What are the constrains on total number of queries (q)? And I think there should be a constrain on
. If there isn't, then this sum can go up to O(qn), and your program won't even be able to take input in time limit.
Then you can split the queries into two parts,
call this light query, and 
call this large query. And you can see that you can't have more than 
large queries.
You can solve light queries by brute force, and take special measures (some pre-calculation) to solve heavy queries. It will lead you to a solution with complexity something like
overall.
You can solve this problem — 348C - Subset Sums, similar problem with same idea. Here you have update query too.
The constraint on
can be easily derived from the problem statement. Yes, the solution for that problem can be used to solve this one too, however all queries in this problem are obviously light, so the complexity (assuming n = m) is O(n3).
Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).
Your problem is essentially matrix multiplication.
Let A be the m × n matrix with (A)i, j = aj, i. For an update let u be a column vector of length n where
. The answer to a query x after this update is (A·u)x. If we know the updates in advance, we can let U = (u1 u2 ... un) and compute A·U to precompute all the answers. This can be done in 
(for m = n).
Since the input does not restrict A and U other than U being boolean and we can always query all values of x, a solution to your problem can be used to compute the boolean matrix product A·U, so your problem has a lower bound of Ω(nω).