| Problem description | | Progress |
Темы:
sqrt decomposition
Given an array a of length n (\(1 <= n <= 2 \cdot 10^6\)< /span>, \(1 <= a_i <= 10^9\)). Also given m (\(1 <= m <= 500\)) queries like l, r (\(1 <= l <= r <= n\)).
For each query, print the sum of numbers between l and r inclusive. Elements are numbered starting with 1 to n.
Examples
| # |
Input |
Output |
| 1 |
4
1 2 3 4
2
1 4
1 1
|
10
1 |
| 2 |
5
5 5 5 5 5
1
5 5
|
5 |
| |
![]()
|
|
Темы:
Segment tree, RSQ, RMQ
sqrt decomposition
Implement a data structure to efficiently calculate the maxima of consecutive array elements.
Input
The first line contains one natural number N (\(1 <= N <= 100000\)) — the number of numbers in the array. The second line contains N numbers from 1 to 100000 — array elements. The third line contains one natural number K (\(1 <= K <= 30000\)) &mdash ; the number of requests to calculate the maximum. In the following K lines, enter two numbers each — the numbers of the left and right elements of the array segment (it is assumed that the elements of the array are numbered from one).
Imprint
For each query, print the value of the maximum element in the specified range of the array. Output the numbers in one line separated by a space.
Examples
| # |
Input |
Output |
| 1 |
5
2 2 2 1 5
2
23
25 |
2 5 |
| |
![]()
|
|
Темы:
sqrt decomposition
Given an array a of length n (\(1 <= n <= 2 \cdot 10^6\)< /span>, \(1 <= a_i <= 10^9\)). Also given m (\(1 <= m <= 500\)) queries like t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).
If \(t = 0\), then the query should display the sum of numbers in the segment from l to r inclusive. If \(t = 1\), then element number l is set to r. Elements are numbered from 1 to n.
Examples
| # |
Input |
Output |
| 1 |
5
1 2 3 4 5
4
0 1 2
1 1 5
0 1 2
0 1 1
|
3
7
5 |
| |
![]()
|
|
Темы:
sqrt decomposition
Given a matrix a of size \(n \cdot n\) (\(1 <= n <= 1000\), \(1 <= a_i <= 10^9\)). Also given are m (\(1 <= m <= 1000\)) queries of the form x1< /sub>, y1, x2, y2 (\(1 <= x_1 <= n\), \(1 <= y_1 <= n\), \(x_1 <= x_2 <= n\), \(y_1 <= y_2 <= n\)).
For each query, output the maximum element in the submatrix with edge coordinates x1, y1 and x2, y< sub>2.
Examples
| # |
Input |
Output |
| 1 |
4
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
1
1 1 3 4
|
6 |
| |
![]()
|
|
Темы:
sqrt decomposition
Given an array a of length n (\(1 <= n <= 2 \ cdot 10^6\), \(1 <= a_i <= 10^9\)). Also given m (\(1 <= m <= 500\)) queries like *, l, r, k (\(1 <= l <= r < = n\), \(0 <= k <10\)) and queries like ?, i (\(1 <= i <= n\)).
In the first case, you need to multiply the numbers in the segment from l to r inclusive by k.
In the second case, print the number at position i.
Elements are numbered from 1 to n.
Examples
| # |
Input |
Output |
| 1 |
5
1 1 1 1 1
3
? 3
* 2 3 9
? 3
|
1
9 |
| |
![]()
|
|
Темы:
sqrt decomposition
Given an array a of length n (\(1 <= n <= 10^ 6\), \(1 <= a_i <= 10^9\)). Also given m (\(1 <= m <= 500\)) queries like +, l, r, k (\(1 < ;= l <= r <= n\), \(-10^9 <= k <= 10^9\) ) and queries like ?, l, r, k ( \(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\) ).
In the first case, you need to add to the numbers in the segment from l to r inclusive, the number k.
In the second case, you need to print 1 if there is a number k on the segment from l to r inclusive, otherwise print 0.
Elements are numbered from 1 to n.
It is guaranteed that after any request, any element of the a array lies within the range of \(-10^9\) up to \(10^9\) inclusive.
Examples
| # |
Input |
Output |
| 1 |
5
1 2 1 1 3
3
|
0
1 |
| |
![]()
|
|
Темы:
Segment tree, RSQ, RMQ
sqrt decomposition
hash
Suffix array
Dynamic programming
hash
Let's say that the sequence of strings t1 , ..., tk is a journey of length k if for all i > 1 ti< /sub> is a substring of ti - 1 of strictly less length. For example, { ab , b } is a journey, and { ab , c } or { a , a } — no.
Define a string traversal s as a traversal t1 , ..., tk , all of whose strings can be nested in s such that there are (possibly empty) strings u1 , ..., uk + 1 such that s = u1t1 u2 t2 ... uk tk uk +&thinsp ;1 . For example, { ab , b } is a string travel for abb , but not for bab , since the corresponding substrings are from right to left.
Let's call the length of the journey the number of lines of which it consists. Determine the maximum possible travel length along the given string s .
Input
The first line contains an integer n ( 1 ≤ n ≤ 500 000 ) — length of string s .
The second line contains the string s , consisting of n lowercase English letters.
Imprint
Print one number — the longest travel length in string s .
Note
In the first example, the longest string traversal is { abcd , bc , c } .
In the second example, { bb , b } would be appropriate.
Examples
| # |
Input |
Output |
| 1 |
7
abcdbcc |
3 |
| 2 |
4
bbcb |
2 |
| |
![]()
|