Find value of sum of a set of rows in a submatrix
Difference between en1 and en2, changed 94 character(s)
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 \times m$. Answer two types of queries:  ↵
- $1$ $k$ $i_1$ $i_2$ $\dots$ $i_k$: Set the _active_ set to ${i_1, i_2, \dots, i_k}$.  ↵
- $2$ $x$: What is the value of $a_{i_1, x} + a_{i_2, x} + \dots + a_{i_k, x}$, where $i_1, i_2, \dots, i_k$ 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 k \leq n, 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 \leq k \leq 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)