Find value of sum of a set of rows in a submatrix

Revision en3, by f2lk6wf90d, 2018-02-01 20:58:23

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 \leq n, m \leq 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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English f2lk6wf90d 2018-02-02 21:17:53 2 Tiny change: 'ot exceed $i$.' -> 'ot exceed i.'
en5 English f2lk6wf90d 2018-02-01 21:20:47 54 Tiny change: 'q k \leq i.$' -> 'q k \leq i$, and all the indices in the query do not exceed $i$.'
en4 English f2lk6wf90d 2018-02-01 21:01:31 1 Tiny change: 'ype 1. \n1 \leq n, ' -> 'ype 1. \n$1 \leq n, '
en3 English f2lk6wf90d 2018-02-01 20:58:23 2 Tiny change: '-th time, 1 \leq k \leq i.' -> '-th time, $1 \leq k \leq i.$'
en2 English f2lk6wf90d 2018-02-01 20:58:13 94
en1 English f2lk6wf90d 2018-02-01 20:44:32 718 Initial revision (published)