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* *i*_{1} *i*_{2} ... *i*_{k}: Set the *active* set to {*i*_{1}, *i*_{2}, ..., *i*_{k}}.

- 2 *x*: What is the value of *a*_{i1, x} + *a*_{i2, x} + ... + *a*_{ik, x}, where *i*_{1}, *i*_{2}, ..., *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 ≤ *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.

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 toO(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) isO(n^{3}).Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).Your problem is essentially matrix multiplication.

Let

Abe them×nmatrix with (A)_{i, j}=a_{j, i}. For an update letube a column vector of lengthnwhere . The answer to a queryxafter this update is (A·u)_{x}. If we know the updates in advance, we can letU= (u_{1}u_{2}...u_{n}) and computeA·Uto precompute all the answers. This can be done in (form=n).Since the input does not restrict

AandUother thanUbeing boolean and we can always query all values ofx, a solution to your problem can be used to compute the boolean matrix productA·U, so your problem has a lower bound of Ω(n^{ω}).