Given a sequence A of N pairwise-distinct integers. There are Q queries L R K, asking for the k-th element in the increasing-sorted subsequence A[L], A[L+1], ...., A[R-1], A[R]. The original sequence never changes.

• 1 ≤ N, Q ≤ 10^5

• |Ai| ≤ 10^9, 1 ≤ i ≤ N

• 1 ≤ L ≤ R ≤ N

• 1 ≤ K ≤ R-L+1

Example:

Input:

7 (N)

2 1 5 4 3 6 8 (sequence A)

4 (Q)

1 2 2 (L R K)

3 7 4

4 6 2

5 5 1

Output:

2

6

4

3

Could somebody please tell me how to use Heavy Light Decomposition (I'm also fascinated with any other way) to solve these two problems:

• QTREE4

• QTREE5

Thank you so much in advance!

I don't know what kind of technique required for this problem. Could anyone please point it out? Thank you so much in advance!

There are several rooms in a company. In each room, there are some employers and some employees, and there is no one who's both an employer and an employee.

One person can be in many rooms, but two people cannot be in the same two rooms. -----> Edit: One person can only be in one room.

In a room, every employer gives work to their employees, but the employers do not give work to each other. The efficiency of a room is determined by the "relationship" in that room.

Example: If there are 2 employers and 3 employees in a room, that room's efficiency will be 6 (= 2 * 3).

The company's efficiency is the total efficiency of all rooms.

Write a program to organize the company such that these conditions are met:

1. The company has at least 1 room.

2. The company's efficiency is exactly E.

3. The number of people in the company (let's say N) is minimum.

4. If there are more than 1 solution to get all the first 3 conditions satisfied, find the solution that has the minimum number of employers (let's say S).

5. If there are more than 1 solution to get all the first 4 conditions satisfied, find the solution that has the minimum number of rooms (let's say K).

Example:

Input:

7 (E)

Output:

7 3 2 (N S K)

Explanation:

There are 3 employers (A1, A2, A3) and 4 employees (B1, B2, B3, B4). They can be put into 2 rooms:

• A1 A2 B1 B2 B3 (Efficiency = 2 * 3 = 6)

• A3 B4 (Efficiency = 1 * 1 = 1)

The total efficiency is 6 + 1 = 7.

Constraints:

• 1 <= E <= 10,000

Link to the problem: LEM7

I've heard that the following problem belongs to a Russian programming contest. Does anyone know where it is or how to solve it?

An arithmetic sequence is a sequence of numbers a[1], a[2],... a[N] such that a[i + 1] — a[i] is equal for all 0 ≤ i < N. Given a sequence of N positive integers and M queries [x, y], write a program answer each query whether the consecutive numbers from position x to y form an arithmetic sequence (they could not originally be in increasing order).

Example:

Input:

5 3 (N M)

1 3 2 5 4 (N positive integers)

1 5 (x y)

2 4 (x y)

4 5 (x y)

Output:

YES

NO

YES

Explain:

• The sequence 1 3 2 5 4 forms an arithmetic sequence, which is 1 2 3 4 5.

• The sequence 3 2 5 does not form an arithmetic sequence.

• The sequence 5 4 also forms an arithmetic sequence, which is 4 5.

Constraints:

• 40% test: N, M <= 1,000 .

• 30% test: N <= 1,000 and M <= 10^6 .

• 30% test: N <= 10^5 and M <= 10^5.

• a[i] <= 10^9

Could anyone please tell me how we can perform the Lazy Propagation technique on the 2D Segment Tree? Suppose we're solving this problem: http://www.spoj.com/problems/MATSUM/ with an additional operation:

"SET x1 y1 x2 y2 num" — Find the rectangle from (x1, y1) to (x2, y2) and set all of its cells' values to num.

I think it would be timeout if we don't use the Lazy Propagation technique here.

Thank you so much in advance!

Is there anyone who's gonna translate this book into English? The book contains so many interesting and basic understanding algorithms as well as data structures in Competitive Programming area. That would be very great if it could come out to worldwide readers.

Hi everyone,

This is one of the problems used in our National Olympiad in Informatics, and it has remained unsolved since 2005. Your help would be really appreciated! So here it is:

Given a sequence of N elements a[1], a[2], ..., a[N] and a positive number K. A partition is defined to include several consecutive elements in the original sequence. Write a program that splits the given sequence into k partitions such that the maximum sum among those partitions is minimized. Write out the desired sum.

Constraints:

• 1 ≤ k ≤ n ≤ 15000

• |ai| ≤ 30000

Example:

Input

9 4 (N and K)

1 1 1 3 2 2 1 3 1 (a[1], a[2], ..., a[N]

Output

5

Explain:

We can divide the original sequence into 4 partitions:

(1, 1, 1)

(3, 2)

(2, 1)

(3, 1)

The maximum sum among the partitions above is 5 (= 3 + 2), and it is the best minimum sum we can achieve while splitting the sequence into 4 partitions.

Could someone please help me to know how to use Splay Tree / Treaps / Link-cut Tree to do this problem? I tried to google it, but nothing helpful was found. Thanks a lot in advance!

Does anyone know how to solve this problem?

http://www.spoj.com/problems/LQDNUMS/

Or at least please give me the references for it. Thanks a lot in advance.

Let function S(X) equal sum of X's digits.

For ex: S(357) = 3 + 5 + 7 = 15

Given M and N (0 < M, N <= 10^12). Find the minimum number K such that:

• a1 + a2 + ... + aK = N

• S(a1) + S(a2) + ... + S(aK) = M

(a1, a2, ..., aK are arbitrary integers <= N)

Example:

Input (M and N)

1 100

Output (K, if K doesn't exist, print -1)

1

Source: http://vn.spoj.com/problems/A2DIGIT/

Does anyone have any idea for this problem?

Hi everyone,

I'm struggling with this problem, and I don't have any idea to do it yet. Does anyone know how to solve it?

A positive integer is called a lucky number when the sum of some of its digits equals the sum of its remaining digits. 561743, for example, is a lucky number because 5 + 1 + 4 + 3 = 6 + 7. However, we are about to count the number of unlucky numbers with the length of N and their digits are in the range [0, K], and they could start with a bunch of '0'.

Input: N K Output: The number of unlucky numbers

Example 1:

Input

1 5

Output

5

Example 2:

Input

4 3

Output

164