Consider characters of this string are number 0-based from left to right. If |s| is not a multiply of k, then answer is "NO". Otherwise, let . Then answer is "Yes" if and only if for each i that 0 ≤ i < |s|, si = s(i / len) * len + len - 1 - (i%len) where a%b is the remainder of dividing a by b.
Time complexity: .
Consider this problem: We have a binary sequence s and want to find the maximum number of consecutive 1s in it. How to solve this? Easily:
ans = 0 cur = 0 for i = 1 to n: if s[i] == 0 then cur = 0 else cur = cur + 1 ans = max(ans, cur)
Finally, answer to this problem is
ans. For each row r of the table, let ansr be the maximum number of consecutive 1s in it (we know how to calculate it in O(m) right ?). So after each query, update ansi in O(m) and then find max(ans1, ans2, ..., ansn) in O(n).
In this editorial, consider p = m, a = h1, a′ = a1, b = h2 and b′ = a2, x = x1, y = y1, X = x2 and Y = y2.
First of all, find the number of seconds it takes until height of Xaniar becomes a′ (starting from a) and call it q. Please note that q ≤ p and if we don't reach a′ after p seconds, then answer is - 1.
If after q seconds also height of Abol will become equal to b′ then answer if q.
Otherwise, find the height of Abdol after q seconds and call it e.
Then find the number of seconds it takes until height of Xaniar becomes a′ (starting from a′) and call it c. Please note that c ≤ p and if we don't reach a′ after p seconds, then answer is - 1.
if g(x) = Xx + Y, then find f(x) = g(g(...(g(x)))) (c times). It is really easy:
c = 1, d = 0 for i = 1 to c c = (cX) % p d = (dX + Y) % p
f(x) return (cx + d) % p
Actually, if height of Abol is x then, after c seconds it will be f(x).
Then, starting from e, find the minimum number of steps of performing
e = f(e) it takes to reach b′ and call it o. Please note that o ≤ p and if we don't reach b′ after p seconds, then answer is - 1.
Then answer is x + c × o.
For each i, find the largest j that aj < ai and show it by li (if there is no such j, then li = 0).
Also, find the smallest j that aj < ai and show it by ri (if there is no such j, then ri = n + 1).
This can be done in O(n) with a stack. Pseudo code of the first part (second part is also like that) :
stack s // initially empty for i = 1 to n while s is not empty and a[s.top()] >= a[i] do s.pop() if s is empty then l[i] = 0 otherwise l[i] = s.top() s.push(i)
Consider that you are asked to print n integers, ans1, ans2, ..., ansn. Obviously, ans1 ≥ ans2 ≥ ... ≥ ansn.
For each i, we know that ai can be minimum element in groups of size 1, 2, ..., ri - li - 1.
Se we need a data structure for us to do this:
We have array ans1, ans2, ..., ansn and all its elements are initially equal to 0. Also, n queries. Each query gives x, val and want us to perform ans1 = max(ans1, val), ans2 = max(ans2, val), ..., ansx = max(ansx, val). We want the final array.
This can be done in O(n) with a maximum partial sum (keeping maximum instead of sum), read here for more information about partial sum.
Time complexity: .
We define that a number x is good if and only if there is no y > 1 that y2 is a divisor of x.
Also, we define function f(x) as follow:
Consider x = p1a1 × p2a2 × ... × pkak where all pis are prime. Then, f(x) = a1 + a2 + ... + an.
Use simple inclusion. Consider all the primes from 1 to 5 × 105 are p1, p2, ..., pk.
So, after each query, if d(x) is the set of beers like i in the shelf that x is a divisor of ai, then number of pairs with gcd equal to 1 is:
Consider good numbers from 1 to 5 × 105 are b1, b2, ..., bm. The above phrase can be written in some other way: |d(b1)| × ( - 1)f(b1) + |d(b2)| × ( - 1)f(b2) + ... + |d(bm)| × ( - 1)f(bm).
So, for each query if we can find all good numbers that ai is divisible by them in a fast way, we can solve the rest of the problem easily (for each good number x, we can store |d(x)| in an array and just update this array and update the answer).
Since all numbers are less than 2 × 3 × 5 × 7 × 11 × 13 × 17, then there are at most 6 primes divisible buy ai. With a simple preprocesses, we can find their maximum and so easily we can find these (at most 6) primes fast. If their amount is x, then there are exactly 2x good numbers that ai is divisible by them (power of each prime should be either 0 or 1).
So we can perform each query in O(26)
Time complexity: .
Consider a bipartite graph. In each part (we call them first and second part) there are L = 2 × 105 vertices numbered from 1 to L. For each point (x, y) add an edge between vertex number x from the first part and vertex number y from the second part.
In this problem, we want to color edges with two colors so that the difference between the number of blue edges connected to a vertex and the number of red edges connected to it be at most 1.
Doing such thing is always possible.
We prove this and solve the problem at the same time with induction on the number of edges :
If all vertices have even degree, then for each component there is an Eulerian circuit, find it and color the edges alternatively_ with blue and red. Because graph is bipartite, then our circuit is an even walk and so, the difference between the number of blue and red edges connected to a vertex will be 0.
Otherwise, if a vertex like v has odd degree, consider a vertex like u that there is and edge between v and u. Delete this edge and solve the problem for the rest of the edges (with the induction definition) and then add this edge and if the number of red edges connected to u is more than the blue ones, then color this edge with blue, otherwise with red.
You can handle this add/delete edge requests and find odd vertices with a simple
call(i, j) = match(sjinsi) which match(tins) is the number of occurrences of t in s.
Concatenate all strings together in order (an put null character between them) and call it string S. We know that .
Consider N = 5 × 105. Consider Consider for each i, Sxisxi + 1...syi = si (xi + 1 = yi + 2).
Also, for i - th character of S which is not a null character, consider it belongs to swi.
Calculate the suffix array of S in and show it by f1, f2, ..., f|S| (we show each suffix by the index of its beginning).
For each query, we want to know the number of occurrences of sk in Sxl...syr. For this propose, we can use this suffix array.
Consider that we show suffix of S starting from index x by S(x).
Also, for each i < |S|, calculate lcp(S(fi), S(fi + 1)) totally in and show it by lci.
For each query, consider fi = xk, also find minimum number a and maximum number b (using binary search and sparse table on sequence lc) such that a ≤ i ≤ b and min(lca, lca + 1, ..., lci - 1) ≥ |sk| and min(lci, lci + 1, ..., lcb - 1) ≥ |sk|.
Finally answer of this query is the number of elements in wa, wa + 1, ..., wb that are in the interval [l, r].
This wasn't my main approach. My main approach uses aho-corasick and a data structure I invented and named it C-Tree.
If there's any suggestion or error let me know.