标签归档:SparseTable

Codeforces 803G. Periodic RMQ Problem(动态开点线段树+ST表)

You are given an array a consisting of positive integers and q queries to this array. There are two types of queries:

  • 1 l r x — for each index i such that l ≤ i ≤ r set ai = x.
  • 2 l r — find the minimum among such ai that l ≤ i ≤ r.

We decided that this problem is too easy. So the array a is given in a compressed form: there is an array b consisting of n elements and a number k in the input, and before all queries a is equal to the concatenation of k arrays b (so the size of a is n·k).

Input

The first line contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 104).

The second line contains n integers — elements of the array b (1 ≤ bi ≤ 109).

The third line contains one integer q (1 ≤ q ≤ 105).

Then q lines follow, each representing a query. Each query is given either as 1 l r x — set all elements in the segment from l till r(including borders) to x (1 ≤ l ≤ r ≤ n·k, 1 ≤ x ≤ 109) or as 2 l r — find the minimum among all elements in the segment from l till r(1 ≤ l ≤ r ≤ n·k).

Output

For each query of type 2 print the answer to this query — the minimum on the corresponding segment.

Examples
input

output

input

output

题意:给出一个长度为\(n\)的序列,复制\(k\)次,形成一个长度为\(n*k\)序列。有\(q\)种操作,两种操作:1.区间赋值 2.询问区间最小值。\(1 \leq n \leq 100000, 1 \leq k \leq 1000, 1 \leq q \leq 100000\)

因为序列太长了,可能达到\(1e9\)的长度,但是操作数只有\(1e5\)的规模,所以考虑动态开点线段树。也就是每操作到一个新的区间我再去开出点,这样每次操作我假设把左右儿子都开出来,最多增加\(2*log(n*k)\)个节点,那么我内存池只要开到\(q*2*log(n*k)\)就可以了。

线段树维护一个区间最小值就可以了吧,考虑怎么得到一个节点的我们可以用ST表来确定出来一开始区间的最小值。然后有set懒标记就下放当前新的节点上。

然后发现我可能不打会算内存啊,开成了\(q*log(n*k)\)了。。。。。

 

SPOJ BGSHOOT – Shoot and kill(差分+ST表)

The problem is about Mr.BG who is a great hunter. Today he has gone to a dense forest for hunting and killing animals.

Sadly, he has only one bullet in his gun. He wants to kill as many animals as possible with only one bullet.

He has already known the information of duration availability of all animals of the forest.

So, he is planning to shoot at a time so that he could kill maximum animal.

Input

Input begins with an integer N denoting total numbers of animals.

Next N lines contains the duration of availability of animal denoting by X (Starting time) and Y (Ending time) .

Then, there will be Q, denoting the total numbers of queries to be answer.

Each query giving two integer L and R, L denoting the time hunter will come to forest and begins shooting

and R denoting last time upto which he will stay at forest for hunting.

Output

For each query output an integer denoting maximum numbers of animals he could kill by shooting at a time during L and R (inclusive).

Constraints:

1<=N,Q<=100000

1<=X,Y,L,R<=1000000000

Example

mdzz。。。。

一开始还写了单点更新的线段树,再一想不就是维护个差分序列,改改改,然后写了个只有查询的线段树,再一想这还写什么线段树啊,直接ST表好了。然后一直WA ,死于数组开小。。。。。人傻手残。。。得离散化一下。。。

 

BZOJ 1067: [SCOI2007]降雨量(ST表)

Description

  我们常常会说这样的话:“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年,且对于任意
Y<Z<X,Z年的降雨量严格小于X年。例如2002,2003,2004和2005年的降雨量分别为4920,5901,2832和3890,
则可以说“2005年是自2003年以来最多的”,但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未
知,有的说法是可能正确也可以不正确的。

Input

  输入仅一行包含一个正整数n,为已知的数据。以下n行每行两个整数yi和ri,为年份和降雨量,按照年份从小
到大排列,即yi<yi+1。下一行包含一个正整数m,为询问的次数。以下m行每行包含两个数Y和X,即询问“X年是
自Y年以来降雨量最多的。”这句话是必真、必假还是“有可能”。

Output

  对于每一个询问,输出true,false或者maybe。

Sample Input

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

Sample Output

false
true
false
maybe
false

HINT

100%的数据满足:1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9

一个分类大讨论加上ST表维护区间最大值就可以了。。。

如果是真话的要求是十分严格的,必须要X和Y已知而且已知X到Y的任意一年的信息,而且num[Y]>=num[X],num[X]还得大于Y+1~X-1中的任意一年。