### [problem:588A]Div.2 A (Author: [user:Haghani,2015-10-01]) ↵
↵
Idea is a simple greedy, buy needed meat for $i-th$ day when it's cheapest among days $1, 2, ..., n$.↵
↵
So, the pseudo code below will work:↵
↵
↵
~~~~~↵
ans = 0↵
price = infinity↵
for i = 1 to n↵
price = min(price, p[i])↵
ans += price * a[i]↵
~~~~~↵
↵
↵
↵
Time complexity: $\mathcal O(n)$↵
↵
[C++ Code](http://ideone.com/fa7rF5) by [user:PrinceOfPersia,2015-10-15]↵
↵
[Python Code](http://ideone.com/Sh0hPp) by [user:Haghani,2015-10-15]↵
↵
[Python Code](http://ideone.com/5J6Rew) by [user:Zlobober,2015-10-15]↵
↵
###[problem:588B]Div.2 B (Author: [user:PrinceOfPersia,2015-10-01])↵
↵
Find all prime divisors of $n$. Assume they are $p_1, p_2, ..., p_k$ (in $\mathcal O(\sqrt n)$). If answer is $a$, then we know that for each $1 \leq i \leq k$, obviously $a$ is not divisible by $p_i^2$ (and all greater powers of $p_i$). So $a \leq p_1 \times p_2 \times ... \times p_k$. And we know that $p_1 \times p_2 \times ... \times p_k$ is itself lovely. So,answer is $p_1 \times p_2 \times ... \times p_k$↵
↵
↵
↵
↵
Time complexity: $\mathcal O(\sqrt n)$↵
↵
[C++ Code](http://ideone.com/5vLYwi) by [user:PrinceOfPersia,2015-10-15]↵
↵
[Python Code](http://ideone.com/Wh2Mrw) by [user:Haghani,2015-10-15]↵
↵
[Python Code](http://ideone.com/1Ca7lj) by [user:Zlobober,2015-10-15]↵
↵
###[problem:587A]A (Author: [user:PrinceOfPersia,2015-10-01])↵
↵
Problem is: you have to find the minimum number of $k$, such there is a sequence $a_1, a_2, ..., a_k$ with condition $2^{a_1} + 2^{a_2} + ... + 2^{a_k} = S = 2^{w_1} + 2^{w^2} + ... + 2^{w_2}$. Obviously, minimum value of $k$ is the number of set bits in binary representation of $S$ (proof is easy, you can prove it as a practice :P).↵
↵
↵
↵
↵
↵
Our only problem is how to count the number of set bits in binary representation of $S$? Building the binary representation of $S$ as an array in $\mathcal O(n + max(a_i))$ is easy: ↵
↵
↵
~~~~~↵
MAXN = 1000000 + log(1000000)↵
bit[0..MAXN] = {} // all equal to zero↵
ans = 0↵
for i = 1 to n↵
bit[w[i]] ++ // of course after this, some bits maybe greater than 1, we'll fix them below↵
for i = 0 to MAXN - 1↵
bit[i + 1] += bit[i]/2 // floor(bit[i]/2)↵
bit[i] %= 2 // bit[i] = bit[i] modulo 2↵
ans += bit[i] // if bit[i] = 0, then answer doesn't change, otherwise it'll increase by 1↵
~~~~~↵
↵
Time complexity: $\mathcal O(n + max(a_i))$↵
↵
[C++ Code](http://ideone.com/90m1nM) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/UT3GoJ) by [user:Haghani,2015-10-15]↵
↵
↵
###[problem:587B]B (Author: [user:PrinceOfPersia,2015-10-01])↵
↵
If we fix $x$ and $b_{i_x}\ mod\ n$, then problem will be solved (because we can then multiply it by the number of valid distinct values of $\lfloor \frac{i_x}{n} \rfloor$).↵
↵
For the problem above, let $dp[i][j]$ be the number of valid subsequences of $b$ where $x = j$ and $\lfloor \frac{i_1}{n} \rfloor = 0$ and $\lfloor \frac{i_x}{n} \rfloor = i$. Of course, for every $i$, $dp[i][1] = 1$. For calculating value of $dp[i][j]$:↵
↵
$dp[i][j] = \sum \limits_{0 \leq k \leq n-1, a_k \leq a_i} dp[k][j-1]$↵
↵
For this purpose, we can sort the array $a$ and use two pointer:↵
↵
if $p_0, p_1,... p_{n-1}$ is a permutation of $0,...,n-1$ where for each $0 \leq t < n-1$, $a_{p_t} \leq a_{p_{t+1}}$:↵
↵
↵
~~~~~↵
for i = 0 to n-1↵
dp[i][1] = 1↵
for j = 2 to k↵
pointer = 0↵
sum = 0↵
for i = 0 to n-1↵
while pointer < n and a[p[pointer]] <= a[i]↵
sum = (sum + dp[p[pointer ++]][j - 1]) % MOD↵
dp[i][j] = sum↵
~~~~~↵
↵
↵
↵
↵
↵
Now, if $c = \lceil \frac{l}{n} \rceil$ and $x = l - 1\ mod\ n$, then answer equals to $\sum \limits_{i=0}^{x} \sum \limits_{j=1}^{min(c, k)} dp[i][j] \times (c - j + 1) \sum \limits_{i=x + 1}^{n-1} \sum \limits_{j=1}^{min(c - 1, k)} dp[i][j] \times (c - j)$ (there are $c - j + 1$ valid different values of $\lfloor \frac{i_x}{n} \rfloor$ for the first group and $c-j$ for the second group).↵
↵
↵
Time complexity: $\mathcal O(nk)$↵
↵
[C++ Code](http://ideone.com/7QJJHJ) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/WNYKEz) by [user:Haghani,2015-10-15]↵
↵
[Java Code](http://ideone.com/hCsaDO) by [user:Zlobober,2015-10-15]↵
↵
###[problem:587C]C (Author: [user:PrinceOfPersia,2015-10-01])↵
↵
Solution is something like the fourth LCA approach discussed [here](http://codeforces.me/blog/entry/16221).↵
↵
For each $1 \leq i \leq n$ and $0 \leq j \leq lg(n)$, store the minimum 10 people in the path from city (vertex) $i$ to its $2^j -th$ parent in an array.↵
↵
Now everything is needed is: how to merge the array of two paths? You can keep the these 10 values in the array in increasing order and for merging, use `merge` function which will work in $\mathcal O(20)$. And then delete the extra values (more than 10).↵
↵
And do the same as described in the article for a query (just like the preprocess part).↵
↵
↵
↵
Time complexity: $\mathcal O((n + q)a. lg(n))$↵
↵
[C++ Code](http://ideone.com/Rbr9TJ) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/1NqglU) by [user:Haghani,2015-10-15]↵
↵
[Java Code](http://ideone.com/pzVUMC) by [user:Zlobober,2015-10-15]↵
↵
###[problem:587D]D (Author: [user:PrinceOfPersia,2015-10-01])↵
↵
Run binary search on the answer ($t$). For checking if answer is less than or equal to $x$ (`check(x)`):↵
↵
First of all delete all edges with destructing time greater than $x$. Now, if there is more than one pair of edges with the same color connected to a vertex(because we can delete at most one of them), answer is "No".↵
↵
Use 2-Sat. Consider a literal for each edge $e$ ($x_e$). If $x_e = TRUE$, it means it should be destructed and it shouldn't otherwise. There are some conditions:↵
↵
1. For each vertex $v$, if there is one (exactly one) pair of edges like $i$ and $j$ with the same color connected to $v$, then we should have the clause $x_i \vee x_j$.↵
↵
2. For each vertex $v$, if the edges connected to it are $e_1, e_2, ..., e_k$, we should make sure that there is no pair $(i, j)$ where $1 \leq i < j \leq k$ and $x_{e_1} = x_{e_2} = True$. The naive approach is to add a clause $\urcorner x_{e_i} \vee \urcorner x_{e_j}$ for each pair. But it's not efficient.↵
↵
↵
↵
The efficient way tho satisfy the second condition is to use prefix or: adding $k$ new literals $p_1, p_2, ..., p_k$ and for each $j \leq i$, make sure $x_{e_j} \Rightarrow p_i$. To make sure about this, we can add two clauses for each $p_i$: $\urcorner x_{e_i} \vee p_i$ and $\urcorner p_{i-1} \vee p_i$ (the second one is only for $i > 1$).↵
↵
And the only thing left is to make sure $\urcorner p_i \vee \urcorner x_{e_{i + 1}}$ (there are no two `TRUE` edges).↵
↵
This way the number of literals and clauses are $\mathcal O(n + m)$. ↵
↵
So, after binary search is over, we should run `check(t)` to get a sample matching.↵
↵
↵
Time complexity: $\mathcal O((n + m) lg(m))$ (but slow, because of the constant factor)↵
↵
[C++ Code](http://ideone.com/KGepK0) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/LvFDOX) by [user:Haghani,2015-10-15]↵
↵
[Java Code](http://ideone.com/bx3QJ8) by [user:Zlobober,2015-10-15]↵
↵
↵
↵
###[problem:587E]E (Authors: [user:PrinceOfPersia,2015-10-01] and [user:Haghani,2015-10-01])↵
↵
↵
↵
**Lemma #1:** If numbers $b_1, b_2, ..., b_k$ are $k$ Kheshtaks of $a_1, ..., a_n$, then $b_1 \oplus b_2 \oplus ... \oplus b_k$ is a Kheshtak of $a_1, ..., a_n$.↵
↵
**Proof:** For each $1 \leq i \leq k$, consider $mask_i$ is a binary bitmask of length $n$ and its $j-th$ bit shows a subsequence of $a_1, ..., a_n$ (subset) with xor equal to $b_i$.↵
↵
So, xor of elements subsequence(subset) of $a_1, ..., a_n$ with bitmask equal to $mask_1 \oplus mask_2 \oplus ... \oplus mask_k$ equals to $b_1 \oplus b_2 \oplus ... \oplus b_k$. So, it's a Kheshtak of this sequence.↵
↵
From this lemma, we can get another results: If all numbers $b_1, b_2, ..., b_k$ are $k$ Kheshtaks of $a_1, ..., a_n$, then every Kheshtak of $b_1, b_2, ..., b_k$ is a Kheshtak of $a_1, ..., a_n$↵
↵
**Lemma #2:** Score of sequence $a_1, a_2, ..., a_n$ is equal to the score of sequence $a_1, a_1 \oplus a_2, a_2 \oplus a_3, ..., a_{n-1} \oplus a_n$.↵
↵
**Proof:** If we show the second sequence by $b_1, b_2, ..., b_n$, then for each $1 \leq i \leq n$:↵
↵
- $b_i$ = $a_{i-1} \oplus a_i$↵
- $a_i$ = $b_1 \oplus b_2 \oplus ... \oplus b_i$↵
↵
$\Longrightarrow$ each element from sequence $b$ is a Kheshtak of sequence $a$ and vise versa. So, due to the result of Lemma #1, each Kheshtak of sequence $b$ is a Kheshtak of sequence $a$ and vise versa. So: ↵
↵
- $score(b_1, ..., b_n) \leq score(a_1, ..., a_n)$↵
- $score(a_1, ..., a_n) \leq score(b_1, ..., b_n)$↵
↵
$\Longrightarrow$ $score(a_1, ..., a_n) = score(b_1, ..., b_n)$↵
↵
↵
↵
↵
Back to original problem: denote another array $b_2, ..., b_n$ where $b_i = a_{i-1} \oplus a_i$. Let's solve these two problems:↵
↵
1- We have array $a_1, ..., a_n$ and $q$ queries of two types:↵
↵
1. $upd(l, r, k)$: Given numbers $l, r$ and $k$, for each $l \leq i \leq r$, perform $a_i = a_i \oplus k$↵
2. $ask(i):$ Given number $i$, return the value of $a_i$.↵
↵
This problem can be solved easily with a simple segment tree using lazy propagation.↵
↵
2- We have array $b_2, ..., b_n$ and queries of two types:↵
↵
1. $modify(p, k)$: Perform $b_p = k$.↵
2. $basis(l, r)$: Find and return the basis vector of $b_l , b_{l+1}, ..., b_r$ (using Gaussian Elimination, its size it at most 32).↵
↵
This problem can be solved by a segment tree where in each node we have the basis of the substring of that node (node $[l, r)$ has the basis of sequence $b_l ,..., b_{r-1}$).↵
↵
This way we can insert to a basis vector $v$:↵
↵
↵
~~~~~↵
insert(x, v)↵
for a in v↵
if a & -a & x↵
x ^= a↵
if !x↵
return↵
for a in v↵
if x & -x & a↵
a ^= x↵
v.push(x)↵
~~~~~↵
↵
But size of $v$ will always be less than or equal to 32. For merging two nodes (of segment tree), we can insert the elements of one in another one.↵
↵
For handling queries of two types, we act like this:↵
↵
Type one: Call functions: $upd(l, r, k)$, $modify(l, b_l \oplus k)$ and $modify(r + 1, b_{r+1} \oplus k)$.↵
↵
Type two: Let $b = basis(l + 1, r)$. Call $insert(a_l, b)$. And then print $2^{b.size()}$ as the answer.↵
↵
Time complexity: $\mathcal O(n lg(n) \times 32^2)$ = $\mathcal O(n lg(n) lg^2(max(a_1,...,a_n)))$↵
↵
[C++ Code](http://ideone.com/GnOXuG) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/WnPXQ4) by [user:Haghani,2015-10-15]↵
↵
[Java Code](http://ideone.com/XNsXoa) by [user:Zlobober,2015-10-15]↵
↵
↵
###[problem:587F]F (Author: [user:PrinceOfPersia,2015-10-01])↵
↵
Use Aho-Corasick. Assume first of all we build the trie of our strings (function `t`). If $t(v, c) \ne -1$ it means that there is an edge in the trie outgoing from vertex $v$ written $c$ on it.↵
↵
So, for building Aho-Corasick, consider $f(v)$ = the vertex we go into, in case of failure ($t(v, c) = -1$). i.e the deepest vertex ($u$), that $v \ne u$ and the path from root to $u$ is a suffix of path from root to $v$. No we can build an automaton (Aho-Corasick), function $g$. For each i, do this (in the automaton):↵
↵
↵
~~~~~↵
cur = root↵
for c in s[i]↵
cur = g(cur, c)↵
And then push i in q[cur] (q is a vector, also we do this for cur = root).↵
↵
end[cur].push(i) // end is also a vector, consisting of the indices of strings ending in vertex cur (state cur in automaton)↵
last[i] = cur // last[i] is the final state we get to from searching string s[i] in automaton g↵
~~~~~↵
↵
Assume $cnt(v, i)$ is the number of occurrences of number $i$ in $q[v]$. Also, denote $count(v, i) = \sum_{u\ in\ subtree\ of\ v} cnt(u, i)$.↵
↵
Build another tree. In this tree, for each $i$ that is not root of the trie, let $par[i] = f(i)$ (the vertex we go in the trie, in case of failure) and call it C-Tree.↵
↵
So now, problem is on a tree. Operations are : Each query gives numbers $l, r, k$ and you have to find the number $\sum \limits_{i=l}^{r} count(last[i], k)$.↵
↵
↵
↵
↵
↵
Act offline. If $N = 10^5$, then:↵
↵
**1.** For each $i$ such that $s[i].size() > \sqrt N$, collect queries (like struct) in a vector of queries $query[i]$, then run `dfs` on the C-Tree and using a partial sum answer to all queries with $k = i$. There are at most $\sqrt n$ of these numbers, so it can be done in $\mathcal O(N \sqrt N)$. After doing these, erase $i$ from all $q[1], q[1], ..., q[N]$.↵
↵
Code (in `dfs`) would be like this(on C-Tree):↵
↵
↵
~~~~~↵
partial_sum[n] = {}; // all 0↵
dfs(v, i){↵
cnt = 0;↵
for x in q[v]↵
if(x == i)↵
++ cnt;↵
for u in childern[v]↵
cnt += dfs(u);↵
for x in end[v]↵
partial_sum[x] += cnt;↵
return cnt;↵
}↵
calc(i){↵
dfs(root, i);↵
for i = 2 to n↵
partial_sum[i] += partial_sum[i-1]↵
for query u in query[i]↵
u.ans = partial_sum[u.r] - partial_sum[u.l - 1]↵
}↵
~~~~~↵
↵
And we should just run `calc(i)` for each of them.↵
↵
**2.** For each $i$ such that $s[i].size() \leq \sqrt N$, collect queries (like struct) in a vector of queries $query[i]$. (each element of this vector have three integers in it: $l, r$ and $ans$).↵
↵
Consider this problem:↵
↵
We have an array a of length $N$(initially all element equal to 0) and some queries of two types:↵
↵
1. $increase(i, val)$: increase $a[i]$ by $val$↵
2. $sum(i)$: tell the value of $a[1] + a[2] + ... + a[i]$↵
↵
We know that number of queries of the first type is $\mathcal O(N)$ and from the second type is $\mathcal O(N \sqrt N)$. Using Sqrt decomposition, we can solve this problem in $\mathcal O(N \sqrt N)$:↵
↵
↵
~~~~~↵
K = sqrt(N)↵
tot[K] = {}, a[N] = {} // this code is 0-based↵
increase(i, val)↵
while i < N and i % K > 0↵
a[i ++] += val↵
while i < K↵
tot[i/K] += val↵
i += K↵
sum(i)↵
return a[i] + tot[i/K]↵
~~~~~↵
↵
Back to our problem now.↵
↵
Then, just run `dfs` once on this C-Tree and act like this:↵
↵
↵
~~~~~↵
dfs(vertex v):↵
for i in end[v]↵
increase(i, 1)↵
for i in q[v]↵
for query u in query[i]↵
u.ans += sum(u.r) - sum(u.l - 1)↵
for u in children[v]↵
dfs(u)↵
for i in end[v]↵
increase(i, -1)↵
~~~~~↵
↵
↵
Then answer to a query $q$ is $q.ans$.↵
↵
↵
↵
Time complexity: $\mathcal O(N \sqrt N)$↵
↵
[C++ Code](http://ideone.com/kIQjcI) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/3QyBHv) by [user:Haghani,2015-10-15]↵
↵
[Java Code](http://ideone.com/f9ul21) by [user:Zlobober,2015-10-15]↵
↵
↵
Idea is a simple greedy, buy needed meat for $i-th$ day when it's cheapest among days $1, 2, ..., n$.↵
↵
So, the pseudo code below will work:↵
↵
↵
~~~~~↵
ans = 0↵
price = infinity↵
for i = 1 to n↵
price = min(price, p[i])↵
ans += price * a[i]↵
~~~~~↵
↵
↵
↵
Time complexity: $\mathcal O(n)$↵
↵
[C++ Code](http://ideone.com/fa7rF5) by [user:PrinceOfPersia,2015-10-15]↵
↵
[Python Code](http://ideone.com/Sh0hPp) by [user:Haghani,2015-10-15]↵
↵
[Python Code](http://ideone.com/5J6Rew) by [user:Zlobober,2015-10-15]↵
↵
###
↵
Find all prime divisors of $n$. Assume they are $p_1, p_2, ..., p_k$ (in $\mathcal O(\sqrt n)$). If answer is $a$, then we know that for each $1 \leq i \leq k$, obviously $a$ is not divisible by $p_i^2$ (and all greater powers of $p_i$). So $a \leq p_1 \times p_2 \times ... \times p_k$. And we know that $p_1 \times p_2 \times ... \times p_k$ is itself lovely. So,answer is $p_1 \times p_2 \times ... \times p_k$↵
↵
↵
↵
↵
Time complexity: $\mathcal O(\sqrt n)$↵
↵
[C++ Code](http://ideone.com/5vLYwi) by [user:PrinceOfPersia,2015-10-15]↵
↵
[Python Code](http://ideone.com/Wh2Mrw) by [user:Haghani,2015-10-15]↵
↵
[Python Code](http://ideone.com/1Ca7lj) by [user:Zlobober,2015-10-15]↵
↵
###
↵
Problem is: you have to find the minimum number of $k$, such there is a sequence $a_1, a_2, ..., a_k$ with condition $2^{a_1} + 2^{a_2} + ... + 2^{a_k} = S = 2^{w_1} + 2^{w^2} + ... + 2^{w_2}$. Obviously, minimum value of $k$ is the number of set bits in binary representation of $S$ (proof is easy, you can prove it as a practice :P).↵
↵
↵
↵
↵
↵
Our only problem is how to count the number of set bits in binary representation of $S$? Building the binary representation of $S$ as an array in $\mathcal O(n + max(a_i))$ is easy: ↵
↵
↵
~~~~~↵
MAXN = 1000000 + log(1000000)↵
bit[0..MAXN] = {} // all equal to zero↵
ans = 0↵
for i = 1 to n↵
bit[w[i]] ++ // of course after this, some bits maybe greater than 1, we'll fix them below↵
for i = 0 to MAXN - 1↵
bit[i + 1] += bit[i]/2 // floor(bit[i]/2)↵
bit[i] %= 2 // bit[i] = bit[i] modulo 2↵
ans += bit[i] // if bit[i] = 0, then answer doesn't change, otherwise it'll increase by 1↵
~~~~~↵
↵
Time complexity: $\mathcal O(n + max(a_i))$↵
↵
[C++ Code](http://ideone.com/90m1nM) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/UT3GoJ) by [user:Haghani,2015-10-15]↵
↵
↵
###
↵
If we fix $x$ and $b_{i_x}\ mod\ n$, then problem will be solved (because we can then multiply it by the number of valid distinct values of $\lfloor \frac{i_x}{n} \rfloor$).↵
↵
For the problem above, let $dp[i][j]$ be the number of valid subsequences of $b$ where $x = j$ and $\lfloor \frac{i_1}{n} \rfloor = 0$ and $\lfloor \frac{i_x}{n} \rfloor = i$. Of course, for every $i$, $dp[i][1] = 1$. For calculating value of $dp[i][j]$:↵
↵
$dp[i][j] = \sum \limits_{0 \leq k \leq n-1, a_k \leq a_i} dp[k][j-1]$↵
↵
For this purpose, we can sort the array $a$ and use two pointer:↵
↵
if $p_0, p_1,... p_{n-1}$ is a permutation of $0,...,n-1$ where for each $0 \leq t < n-1$, $a_{p_t} \leq a_{p_{t+1}}$:↵
↵
↵
~~~~~↵
for i = 0 to n-1↵
dp[i][1] = 1↵
for j = 2 to k↵
pointer = 0↵
sum = 0↵
for i = 0 to n-1↵
while pointer < n and a[p[pointer]] <= a[i]↵
sum = (sum + dp[p[pointer ++]][j - 1]) % MOD↵
dp[i][j] = sum↵
~~~~~↵
↵
↵
↵
↵
↵
Now, if $c = \lceil \frac{l}{n} \rceil$ and $x = l - 1\ mod\ n$, then answer equals to $\sum \limits_{i=0}^{x} \sum \limits_{j=1}^{min(c, k)} dp[i][j] \times (c - j + 1) \sum \limits_{i=x + 1}^{n-1} \sum \limits_{j=1}^{min(c - 1, k)} dp[i][j] \times (c - j)$ (there are $c - j + 1$ valid different values of $\lfloor \frac{i_x}{n} \rfloor$ for the first group and $c-j$ for the second group).↵
↵
↵
Time complexity: $\mathcal O(nk)$↵
↵
[C++ Code](http://ideone.com/7QJJHJ) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/WNYKEz) by [user:Haghani,2015-10-15]↵
↵
[Java Code](http://ideone.com/hCsaDO) by [user:Zlobober,2015-10-15]↵
↵
###
↵
Solution is something like the fourth LCA approach discussed [here](http://codeforces.me/blog/entry/16221).↵
↵
For each $1 \leq i \leq n$ and $0 \leq j \leq lg(n)$, store the minimum 10 people in the path from city (vertex) $i$ to its $2^j -th$ parent in an array.↵
↵
Now everything is needed is: how to merge the array of two paths? You can keep the these 10 values in the array in increasing order and for merging, use `merge` function which will work in $\mathcal O(20)$. And then delete the extra values (more than 10).↵
↵
And do the same as described in the article for a query (just like the preprocess part).↵
↵
↵
↵
Time complexity: $\mathcal O((n + q)a. lg(n))$↵
↵
[C++ Code](http://ideone.com/Rbr9TJ) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/1NqglU) by [user:Haghani,2015-10-15]↵
↵
[Java Code](http://ideone.com/pzVUMC) by [user:Zlobober,2015-10-15]↵
↵
###
↵
Run binary search on the answer ($t$). For checking if answer is less than or equal to $x$ (`check(x)`):↵
↵
First of all delete all edges with destructing time greater than $x$. Now, if there is more than one pair of edges with the same color connected to a vertex(because we can delete at most one of them), answer is "No".↵
↵
Use 2-Sat. Consider a literal for each edge $e$ ($x_e$). If $x_e = TRUE$, it means it should be destructed and it shouldn't otherwise. There are some conditions:↵
↵
1. For each vertex $v$, if there is one (exactly one) pair of edges like $i$ and $j$ with the same color connected to $v$, then we should have the clause $x_i \vee x_j$.↵
↵
2. For each vertex $v$, if the edges connected to it are $e_1, e_2, ..., e_k$, we should make sure that there is no pair $(i, j)$ where $1 \leq i < j \leq k$ and $x_{e_1} = x_{e_2} = True$. The naive approach is to add a clause $\urcorner x_{e_i} \vee \urcorner x_{e_j}$ for each pair. But it's not efficient.↵
↵
↵
↵
The efficient way tho satisfy the second condition is to use prefix or: adding $k$ new literals $p_1, p_2, ..., p_k$ and for each $j \leq i$, make sure $x_{e_j} \Rightarrow p_i$. To make sure about this, we can add two clauses for each $p_i$: $\urcorner x_{e_i} \vee p_i$ and $\urcorner p_{i-1} \vee p_i$ (the second one is only for $i > 1$).↵
↵
And the only thing left is to make sure $\urcorner p_i \vee \urcorner x_{e_{i + 1}}$ (there are no two `TRUE` edges).↵
↵
This way the number of literals and clauses are $\mathcal O(n + m)$. ↵
↵
So, after binary search is over, we should run `check(t)` to get a sample matching.↵
↵
↵
Time complexity: $\mathcal O((n + m) lg(m))$ (but slow, because of the constant factor)↵
↵
[C++ Code](http://ideone.com/KGepK0) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/LvFDOX) by [user:Haghani,2015-10-15]↵
↵
[Java Code](http://ideone.com/bx3QJ8) by [user:Zlobober,2015-10-15]↵
↵
↵
↵
###
↵
↵
↵
**Lemma #1:** If numbers $b_1, b_2, ..., b_k$ are $k$ Kheshtaks of $a_1, ..., a_n$, then $b_1 \oplus b_2 \oplus ... \oplus b_k$ is a Kheshtak of $a_1, ..., a_n$.↵
↵
**Proof:** For each $1 \leq i \leq k$, consider $mask_i$ is a binary bitmask of length $n$ and its $j-th$ bit shows a subsequence of $a_1, ..., a_n$ (subset) with xor equal to $b_i$.↵
↵
So, xor of elements subsequence(subset) of $a_1, ..., a_n$ with bitmask equal to $mask_1 \oplus mask_2 \oplus ... \oplus mask_k$ equals to $b_1 \oplus b_2 \oplus ... \oplus b_k$. So, it's a Kheshtak of this sequence.↵
↵
From this lemma, we can get another results: If all numbers $b_1, b_2, ..., b_k$ are $k$ Kheshtaks of $a_1, ..., a_n$, then every Kheshtak of $b_1, b_2, ..., b_k$ is a Kheshtak of $a_1, ..., a_n$↵
↵
**Lemma #2:** Score of sequence $a_1, a_2, ..., a_n$ is equal to the score of sequence $a_1, a_1 \oplus a_2, a_2 \oplus a_3, ..., a_{n-1} \oplus a_n$.↵
↵
**Proof:** If we show the second sequence by $b_1, b_2, ..., b_n$, then for each $1 \leq i \leq n$:↵
↵
- $b_i$ = $a_{i-1} \oplus a_i$↵
- $a_i$ = $b_1 \oplus b_2 \oplus ... \oplus b_i$↵
↵
$\Longrightarrow$ each element from sequence $b$ is a Kheshtak of sequence $a$ and vise versa. So, due to the result of Lemma #1, each Kheshtak of sequence $b$ is a Kheshtak of sequence $a$ and vise versa. So: ↵
↵
- $score(b_1, ..., b_n) \leq score(a_1, ..., a_n)$↵
- $score(a_1, ..., a_n) \leq score(b_1, ..., b_n)$↵
↵
$\Longrightarrow$ $score(a_1, ..., a_n) = score(b_1, ..., b_n)$↵
↵
↵
↵
↵
Back to original problem: denote another array $b_2, ..., b_n$ where $b_i = a_{i-1} \oplus a_i$. Let's solve these two problems:↵
↵
1- We have array $a_1, ..., a_n$ and $q$ queries of two types:↵
↵
1. $upd(l, r, k)$: Given numbers $l, r$ and $k$, for each $l \leq i \leq r$, perform $a_i = a_i \oplus k$↵
2. $ask(i):$ Given number $i$, return the value of $a_i$.↵
↵
This problem can be solved easily with a simple segment tree using lazy propagation.↵
↵
2- We have array $b_2, ..., b_n$ and queries of two types:↵
↵
1. $modify(p, k)$: Perform $b_p = k$.↵
2. $basis(l, r)$: Find and return the basis vector of $b_l , b_{l+1}, ..., b_r$ (using Gaussian Elimination, its size it at most 32).↵
↵
This problem can be solved by a segment tree where in each node we have the basis of the substring of that node (node $[l, r)$ has the basis of sequence $b_l ,..., b_{r-1}$).↵
↵
This way we can insert to a basis vector $v$:↵
↵
↵
~~~~~↵
insert(x, v)↵
for a in v↵
if a & -a & x↵
x ^= a↵
if !x↵
return↵
for a in v↵
if x & -x & a↵
a ^= x↵
v.push(x)↵
~~~~~↵
↵
But size of $v$ will always be less than or equal to 32. For merging two nodes (of segment tree), we can insert the elements of one in another one.↵
↵
For handling queries of two types, we act like this:↵
↵
Type one: Call functions: $upd(l, r, k)$, $modify(l, b_l \oplus k)$ and $modify(r + 1, b_{r+1} \oplus k)$.↵
↵
Type two: Let $b = basis(l + 1, r)$. Call $insert(a_l, b)$. And then print $2^{b.size()}$ as the answer.↵
↵
Time complexity: $\mathcal O(n lg(n) \times 32^2)$ = $\mathcal O(n lg(n) lg^2(max(a_1,...,a_n)))$↵
↵
[C++ Code](http://ideone.com/GnOXuG) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/WnPXQ4) by [user:Haghani,2015-10-15]↵
↵
[Java Code](http://ideone.com/XNsXoa) by [user:Zlobober,2015-10-15]↵
↵
↵
###
↵
Use Aho-Corasick. Assume first of all we build the trie of our strings (function `t`). If $t(v, c) \ne -1$ it means that there is an edge in the trie outgoing from vertex $v$ written $c$ on it.↵
↵
So, for building Aho-Corasick, consider $f(v)$ = the vertex we go into, in case of failure ($t(v, c) = -1$). i.e the deepest vertex ($u$), that $v \ne u$ and the path from root to $u$ is a suffix of path from root to $v$. No we can build an automaton (Aho-Corasick), function $g$. For each i, do this (in the automaton):↵
↵
↵
~~~~~↵
cur = root↵
for c in s[i]↵
cur = g(cur, c)↵
And then push i in q[cur] (q is a vector, also we do this for cur = root).↵
↵
end[cur].push(i) // end is also a vector, consisting of the indices of strings ending in vertex cur (state cur in automaton)↵
last[i] = cur // last[i] is the final state we get to from searching string s[i] in automaton g↵
~~~~~↵
↵
Assume $cnt(v, i)$ is the number of occurrences of number $i$ in $q[v]$. Also, denote $count(v, i) = \sum_{u\ in\ subtree\ of\ v} cnt(u, i)$.↵
↵
Build another tree. In this tree, for each $i$ that is not root of the trie, let $par[i] = f(i)$ (the vertex we go in the trie, in case of failure) and call it C-Tree.↵
↵
So now, problem is on a tree. Operations are : Each query gives numbers $l, r, k$ and you have to find the number $\sum \limits_{i=l}^{r} count(last[i], k)$.↵
↵
↵
↵
↵
↵
Act offline. If $N = 10^5$, then:↵
↵
**1.** For each $i$ such that $s[i].size() > \sqrt N$, collect queries (like struct) in a vector of queries $query[i]$, then run `dfs` on the C-Tree and using a partial sum answer to all queries with $k = i$. There are at most $\sqrt n$ of these numbers, so it can be done in $\mathcal O(N \sqrt N)$. After doing these, erase $i$ from all $q[1], q[1], ..., q[N]$.↵
↵
Code (in `dfs`) would be like this(on C-Tree):↵
↵
↵
~~~~~↵
partial_sum[n] = {}; // all 0↵
dfs(v, i){↵
cnt = 0;↵
for x in q[v]↵
if(x == i)↵
++ cnt;↵
for u in childern[v]↵
cnt += dfs(u);↵
for x in end[v]↵
partial_sum[x] += cnt;↵
return cnt;↵
}↵
calc(i){↵
dfs(root, i);↵
for i = 2 to n↵
partial_sum[i] += partial_sum[i-1]↵
for query u in query[i]↵
u.ans = partial_sum[u.r] - partial_sum[u.l - 1]↵
}↵
~~~~~↵
↵
And we should just run `calc(i)` for each of them.↵
↵
**2.** For each $i$ such that $s[i].size() \leq \sqrt N$, collect queries (like struct) in a vector of queries $query[i]$. (each element of this vector have three integers in it: $l, r$ and $ans$).↵
↵
Consider this problem:↵
↵
We have an array a of length $N$(initially all element equal to 0) and some queries of two types:↵
↵
1. $increase(i, val)$: increase $a[i]$ by $val$↵
2. $sum(i)$: tell the value of $a[1] + a[2] + ... + a[i]$↵
↵
We know that number of queries of the first type is $\mathcal O(N)$ and from the second type is $\mathcal O(N \sqrt N)$. Using Sqrt decomposition, we can solve this problem in $\mathcal O(N \sqrt N)$:↵
↵
↵
~~~~~↵
K = sqrt(N)↵
tot[K] = {}, a[N] = {} // this code is 0-based↵
increase(i, val)↵
while i < N and i % K > 0↵
a[i ++] += val↵
while i < K↵
tot[i/K] += val↵
i += K↵
sum(i)↵
return a[i] + tot[i/K]↵
~~~~~↵
↵
Back to our problem now.↵
↵
Then, just run `dfs` once on this C-Tree and act like this:↵
↵
↵
~~~~~↵
dfs(vertex v):↵
for i in end[v]↵
increase(i, 1)↵
for i in q[v]↵
for query u in query[i]↵
u.ans += sum(u.r) - sum(u.l - 1)↵
for u in children[v]↵
dfs(u)↵
for i in end[v]↵
increase(i, -1)↵
~~~~~↵
↵
↵
Then answer to a query $q$ is $q.ans$.↵
↵
↵
↵
Time complexity: $\mathcal O(N \sqrt N)$↵
↵
[C++ Code](http://ideone.com/kIQjcI) by [user:PrinceOfPersia,2015-10-15]↵
↵
[C++ Code](http://ideone.com/3QyBHv) by [user:Haghani,2015-10-15]↵
↵
[Java Code](http://ideone.com/f9ul21) by [user:Zlobober,2015-10-15]↵
↵
