月度归档:2016年09月

SPOJ GSS4&&hdu 4027 Can you answer these queries IV(线段树区间开方)

You are given a sequence A of N(N <= 100,000) positive integers. There sum will be less than 1018. On this sequence you have to apply M (M <= 100,000) operations:

(A) For given x,y, for each elements between the x-th and the y-th ones (inclusively, counting from 1), modify it to its positive square root (rounded down to the nearest integer).

(B) For given x,y, query the sum of all the elements between the x-th and the y-th ones (inclusively, counting from 1) in the sequence.

Input

Multiple test cases, please proceed them one by one. Input terminates by EOF.

For each test case:

The first line contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in the form “i x y”.i=0 denotes the modify operation, i=1 denotes the query operation.

Output

For each test case:

Output the case number (counting from 1) in the first line of output. Then for each query, print an integer as the problem required.

Print an blank line after each test case.

See the sample output for more details.

Example

线段树处理区间开方。首先因为题目中数字最多才2^64,也就是最多开方7次就会变成1,那么在进行开方的话是毫无意义的。那么我们可以用一个数组表示当前区间到底是不是全部为1,如果是的话,那么我们就不用再继续往下更新区间了。然后因为我们每次更新都是对区间中的每个数开方,所以每个数最多开方7次,就不用再做任何开方的操作了。所以复杂度大概就是O(7*n)这个样子了。

 

poj 2528 Mayor’s posters(线段树成段更新+离散化)

Description

The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:

  • Every candidate can place exactly one poster on the wall.
  • All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
  • The wall is divided into segments and the width of each segment is one byte.
  • Each poster must completely cover a contiguous number of wall segments.

They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are placed given the information about posters’ size, their place and order of placement on the electoral wall.

Input

The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers l i and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= l i <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered l i, l i+1 ,… , ri.

Output

For each input data set print the number of visible posters after all the posters are placed.

The picture below illustrates the case of the sample input.

Sample Input

Sample Output


题目中li的范围达到了1e7直接开这个范围的线段树肯定T还可能爆空间。但是n才10000,所以可以离散化一下。

但是需要注意的是,这道题目的离散化需要特殊的技巧(因为这个WA了很多次)。因为这道题目上的端点值是一个单位区间再加上端点。举个栗子,当我们把1-10,1-4,5-10按照顺序染色后,画图很容易看出答案是2.但是如果不加处理直接去重答案会是3.那么我们可以把相邻两个数之间差大于1的数加入一个靠左边的数+1的数来处理这种情况。因为这样相当于把段线段树转化成了熟悉的点线段树。。。

 

hdu 3530 Subsequence(单调队列)

Description

There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.

Input

There are multiple test cases.
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].
Proceed to the end of file.

Output

For each test case, print the length of the subsequence on a single line.

Sample Input

Sample Output


维护两个单调队列,分别存到当前i的最大值和最小值。用一个bg变量表示当前区间的起点。当队首的两值差大于k,就需要我们舍弃两个单调队列中更靠前的那个位置(这样可以保证队列的长度求得是最长),并且更新bg。如果队首两值差大于等于M就可以更新答案。