### Div.2 A — Cursed Query

You should make a sequence *s*_{1}, *s*_{2}, ..., *s*_{n} such that *s*_{i} = *a*_{1} + *a*_{2} + ... + *a*_{i} and use a binary search to find the first element that is greater than *t* % *s*_{n} (or `upper_bound`

function in C++ ).

Source code : Here

### Div.2 B — Troynacci Query

First of all, compute sequence *f* (0-based), then consider we have a sequence *p* (also 0-based) (partial sum), initially all members are 0.

For each query, if *l* < *r*, then do :

```
p[l] = (p[l] + f[0]) % mod;
p[l+1] = (p[l+1] + f[1]) % mod;
p[l+1] = (1LL * p[l+1] + mod - 1LL * ((1LL * b * f[0]) % mod)) % mod;
p[r + 1] = (1LL * p[r+1] + mod - f[r - l + 1]) % mod;
p[r + 2] = (1LL * p[r+2] + mod - 1LL * ((1LL * a * f[r-l]) % mod)) % mod;
```

otherwise, do this :

```
p[l] = (p[l] + f[0])%mod;
p[r+1] = (1LL * p[r+1] + mod - ((1LL * b * f[0])%mod))%mod;
p[r+2] = (1LL * p[r+2] + mod - 1LL * ((1LL * a * f[0])%mod))%mod;
```

An the just run this : for every *i*, staring from 0, *p*_{i} + = *a* × *p*_{i - 2} + *b* × *p*_{i - 1} and *a*_{i} + = *p*_{i} .

Source code : Here

### A — LCM Query

If we have an array *x*_{1}, *x*_{2}, ..., *x*_{m} and for each *i*, 1 ≤ *x*_{i} ≤ 60, the number of different element in the array *y*_{1}, *y*_{2}, ..., *y*_{m} such that *y*_{j} = *lcm*(*x*_{1}, *x*_{2}, ..., *x*_{j}), is at most *log*(60!) .Because *y*_{1} ≤ *y*_{2} ≤ *y*_{3} ≤ ... ≤ *y*_{m} and if *y*_{i} < *y*_{i + 1}, then *y*_{i} ≤ 2 × *y*_{i + 1}, and *y*_{m} ≤ 60! .

Actually, it is even less, like 25.

So for each *i*, you can find all these members for array *a*_{i}, *a*_{i + 1}, ..., *a*_{n} using at most 25 binary searches and save them in an array.

And if *x* = *p*_{1}^{b1} × ... × *p*_{k}^{bk} such that all *p*_{i}s are prime an *k* = the number of primes less than 60, then we assign sequence *b* to *x*. Using this, you can easily see that if *x* = *p*_{1}^{b1} × ... × *p*_{k}^{bk} and *y* = *p*_{1}^{c1} × ... × *p*_{k}^{ck}, *lcm*(*x*, *y*) = *p*_{1}^{max(b1, c1)} × ... × *p*_{k}^{max(bk, ck)}. And for check if a number is less than another one using this sequence *b*, you can use *log* function and the fact that *log*(*x*) = *log*(*p*_{1}^{b1}) + ... + *log*(*p*_{k}^{bk}), so if *log*(*x*) < *log*(*y*) then, *x* < *y*, and this is how to calculate the minimum value.

By the way, you can calculate *lcm*(*a*_{l}, *a*_{l + 1}, ..., *a*_{r}) in *O*(25) using Sparce Table.

Source code : Here

### B — ShortestPath Query

Consider, for each vertex *v* an each color *c* that there is at least one edge entering *v* with color *c*, we have the length of the shortest path from *s* to *v* such that it's last edge has color *c* (we call this *d*_{v, c}). So, with this, you can make a graph with states (*v*, *c*) and run a Dijkstra on it and it's easy update.

But this will get TLE.

If you think about that, you don't need all states (*v*, *c*), among all these states, we just need the first two states with minimum value of *d* (for each vertex *v*).

Source code : Here

### C — Subrect Query

First of all, let's solve the 1-D version :

we have two sequences *a*_{1}, *a*_{2}, ..., *a*_{n} and *b*_{1}, *b*_{2}, ..., *b*_{n} and for each *i*, we know that *b*_{i} ≤ *a*_{i}. Our goal is to calculate the number of pairs (*l*, *r*) in *O*(*n*) such that 1 ≤ *l* ≤ *r* ≤ *n* and *max*(*a*_{l}, *a*_{l + 1}, ..., *a*_{r}) - *min*(*b*_{l}, *b*_{l + 1}, ..., *b*_{r}) ≤ *k* .

We use two double ended queues (deques) for this propose :

```
let mx, mn be two empty deques
l = 1
ans = 0
for r = 1 to n
while !mx.empty() and a[mx.back()] <= a[r]
mx.pop_back()
while !mn.empty() and b[mn.back()] >= b[r]
mn.pop_back()
mx.push_back(r)
mn.push_back(r)
while a[mx.front()] - b[mn.front()] > k
l ++
if mx.front() < l
mx.pop_front()
if mn.front() < l
mn.pop_front()
ans += r - l + 1
```

In this code, for each *r* we are finding the largest valid *l*, and by the way *a*[*mx*.*front*()] = *max*(*a*_{l}, *a*_{l + 1}, ..., *a*_{r}) and *b*[*mn*.*front*()] = *min*(*b*_{l}, *b*_{l + 1}, ..., *b*_{r}) .

Now let's get back to the original problem.

For each pair (*i*, *j*) such that 1 ≤ *i* ≤ *j* ≤ *m*, build arrays *a*_{1}, *a*_{2}, ..., *a*_{n} and *b*_{1}, *b*_{2}, ..., *b*_{n} such that *a*_{k} = *max*(*a*_{k, i}, ..., *a*_{k, j}) and *b*_{k} = *min*(*a*_{k, i}, ..., *a*_{k, j}) and then run the code above.

Except that C++ deque is too slow,so you should write one.

Source code : Here

### D — TROY Query

For each row or column, it's not important how many times we run the operation on it, the only thing matters, is that it's odd or even.

So, assign a boolian to each row and each column, such that row number *i*'s boolian is *r*_{i} and column *j*'s boolian is *c*_{j}.

The other things are like 2-sat, except that the graph in this problem will be undirected.

For each query, if *a*_{x, y} = *b*_{x, y} so we know that so add an edge between *r*_{x} and *c*_{y} and one between ¬*r*_{x} and ¬*c*_{y}.

Otherwise, add an edge between ¬*r*_{x} and *c*_{y} and one between ¬*c*_{y} and *r*_{x} .

You can use a disjoint set with array or vector and in each step, check if a boolian like *x* and ¬*x* are in the same component, print "No" for the rest of the queries (Because when the answer to a query is No, the answer to the next queries will be also No).

Source code : Here

The other approach is to use binary search on the last step with answer "Yes" and check using a normal 2-sat (directed graph.)

Source code for this approach : Here

### E — Palindrome Query

Use Robin-Carp. Let's consider that *h*_{i} ≡ *s*_{1} × *p*^{0} + *s*_{2} × *p*^{1} + ... + *s*_{i} × *p*^{i - 1}(*mod* *m*) .

For a query of type 2 or 3, just use a simple binary search.

For a modify query, if *y* = *x* - *s*_{p}, you should add *y* × *p*^{0} to *h*_{p}, *y* × *p*^{1} to *h*_{p + 1} and so on. You can do all these using a segment tree or fenwick (BIT).

Source code : Here

### F — Tree Query

Use divide and conquer on the tree (centroid decomposition) and answer queries offline.

For conquer, imagine root is *r*. Run dfs on *r* and for each vertex, push it's distance to *r* in the vector *e*. Then sort *e* and for each vertex *v* in subtree of *r* and query *o* such that it's asking about *v* and number *l*, do this : `ans[o] += the number of members of e like p such that p + d(r,v) <= l`

(using binary search).

But here, we counted some vertices for some queries more than once.

Then for each neighbor of *r* do this separately:

Run dfs on it's subtree and for each vertex, push it's distance to *r* in the vector *z*. Then sort *z* and for each vertex *v* in this subtree and query *o* such that it's asking about *v* and number *l*, do this : `ans[o] -= the number of members of z like p such that p + d(r,v) <= l`

(using binary search).

Source code : Here

thank for nice problem :)

Really nice editorial and thanks for adding source codes :D

nice solution for problem B Div 2 :)

these problem isn't nice these are very nice :)

thanks !

Well...In problem C,I have't realized the Array can be so long...T_T

const int N = 404;int mn[N][N]N

I finished it by rmq.May be use rmq query the biggest and smallest is better .

Thanks for solutions,and thanks for problem's tags before the solutions.(I solve all problems by tags and tags Allows me to be more independent thinking!) Nice problems and nice solutions! :D

Why can't i see the solutions of other contestants? I'm new.

Because this is a GYM contest. GYM submissions are not visible until you solve the problem.

Can you please explain problem B Troynacci Query more?

I can not understand.

Read this (partial sum) before that.

I have read this and understood but cannot find the logic of the solution of problem B. Can you explain more? :|

Same, please someone explain Div2 B.

In div2 A testcase 13 when I define

`maxn 100000+10`

it gets WA but`maxn 100000+100`

gets AC How come??Just a fun question, does the "Khikulish" sentence in Div2 problem A mean anything?

Khikulandis a very useful name for countries in problems of INOI (Iran Olympiad in Informatics).Problem A — LCM Query, could anyone explain first part of solution:

"If we have an array x1, x2, ..., xm and for each i, 1 ≤ xi ≤ 60, the number of different element in the array y1, y2, ..., ym such that yj = lcm(x1, x2, ..., xj), is at most log(60!) .Because y1 ≤ y2 ≤ y3 ≤ ... ≤ ym and if yi < yi + 1, then yi ≤ 2 × yi + 1, and ym ≤ 60! .

Actually, it is even less, like 25.

So for each i, you can find all these members for array ai, ai + 1, ..., an using at most 25 binary searches and save them in an array."

Having sparse table, how do you quickly calculate mininum lcm of intervals of length x(x=1..n)?

Plz Anyone explain me solution for problem B.I also tried to understand partial sums from given link,but i could not.Plz help.

Problem F :

It can also be solved by answering the queries online (using centroid decomposition). We decompose the given tree and for each node in the centroid tree , we maintain the following two vectors :

ans[u] = sorted vector of d(x,u) for all x in the subtree of u in centroid tree, where d(x,u) represents the distance between node x and u in the original tree.

cntbn[u] = sorted vector of d(x,par[u]) for all x in the subtree of u in centroid tree, where d(x,par[u]) represents the distance between node x and par[u] in the original tree. (par[u] is the parent of node u in centroid tree).

Since, there are at-most logN levels in centroid tree, and at each level we are storing O(N) values of ans/cntbn, total memory required would be O(NlogN). Also, these vectors can easily be build in O(NlogN) or O(Nlog^2N) time by moving up node u (for all u) in centroid tree and adding the corresponding values in all the ancestors of u.

Given this information, each query would now reduce to

http://codeforces.com/gym/100570/submission/12316350

First of Thank you for the blog, Baba!

this problem is so elegant to be solved using Centroid decomposition, that I cannot keep myself from appretiating.

All the submissions for this prob are hidden. So I am posting my solution here for convenience.

If anyone is not using windows and want to see what is going on use -DWIN32 as a flag and if someone on windows wants to remove all the excess messages -DWIN32 flag while compiling.

In the code of the Problem F, can you please tell me why you have written

`w-h[u]`

in line 70 and 71?reason : we only calculate the node which one not connected further when we remove centroid.

Can you please prove problem B solution.

An explanation for the first approach: when you get a query {l, r}, you need the following change:

Suppose you keep an array

`p[]`

, initially all zero, and do this:And now if you apply the recursion

`p[i] += a*p[i-2] + b*p[i-1]`

for all i, you get the corresponding update. I'll try to show this too:See that once you start applying the recursion on array p[], this is the result:

now that you have successfully got

`p[l] and p[l+1]`

as`f[1] and f[2]`

respectively, you'll get f[i] correctly up to p[r] because of the formula you are applying constantly.Beware, you don't want these values to affect further. Hence we need to keep some values at p[r+1] and p[r+2] already so that their net values after this recursion turns out to be zero, if we do this correctly, no further effects will be observed starting from p[r+3], since previous 2 values will be 0 then.

This is why we've got (3) and (4):

Hence, once you make the changes (1), (2), (3), and (4) to array p[], you have assured that the corresponding query will be handled as soon as we do the recursive additions in p[].

And hence you may as well do this recursive addition at the very end, to result in

`O(n+q)`

solution.Check it yourself that the author has provided exactly these 4 updates for each query {l, r}.

Thank you so much!

Thank you very much. Finally I can understand the solution.

He was waiting for 9 months to get this reply from you. Thanks for making his long desired wish true :P

xD. I read the problem long time ago. But I din't read the editorial before. It help me a lot. (Sorry for my poor English)

Can someone explain problem LCM QUERY of div 1 A I am facing difficulty in understanding these lines of editorial

If we have an array x1, x2, ..., xm and for each i, 1 ≤ xi ≤ 60, the number of different element in the array y1, y2, ..., ym such that yj = lcm(x1, x2, ..., xj), is at most log(60!) .Because y1 ≤ y2 ≤ y3 ≤ ... ≤ ym and if yi < yi + 1, then yi ≤ 2 × yi + 1, and ym ≤ 60! .Actually, it is even less, like 25Thanks!

Nice editorial, really helped me, like the sources codes that you've added.

Can someone explain why we add MOD value in the middle of expression when the answer is asked to be mod? Isn't it enough to just calculate all values and take their mod?

In

cpp%(**modular division**) operator may return negative values, whereas we don't want any negative values here. So, to ensure the remainder we get after using%operator is non-negative, we add mod to the expression.output: -1

In python there is no such issue, and we also get a non-negative result on using the % operator.

I was trying to solve B.Shortest path Query but I'm getting WA. the tryoic path means that no consecutive edges should have same color that's it, right? please help me!

In editorial TROY Query,

Because when the answer to a query is No, the answer to the next queries will be also No. Can someone explain me why?