Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

02/21
10:17
可持久化数据结构 数据结构

BZOJ 3166 [Heoi2013]Alo 可持久化trie

Description

Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG , 如名字所见,到处充满了数学的谜题。 现在你拥有n颗宝石,每颗宝石有一个能量密度,记为ai,这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设为 ai, ai+1, …, a j,则融合而成的宝石的能量密度为这些宝石中能量密度的次大值 与其他任意一颗宝石的能量密度按位异或的值,即,设该段宝石能量密度次大值 为k,则生成的宝石的能量密度为max{k xor ap | ap ≠ k , i ≤ p ≤ j}。 现在你需要知道你怎么选取需要融合的宝石,才能使生成的宝石能量密度最大。

Input

第一行,一个整数 n,表示宝石个数。 第二行, n个整数,分别表示a1至an,表示每颗宝石的能量密度,保证对于i ≠ j有 ai ≠ aj。

Output

输出一行一个整数,表示最大能生成的宝石能量密度。

Sample Input

5

9 2 1 4 7

Sample Output

14

HINT

【样例解释】

选择区间[1,5],最大值为 7 xor 9。

对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9

Source

加强型数据By Hta

Solution

窝真是太弱了……看了 黄学长的题解 才会做……

大体思路就是:

按照权值从大到小,把每个数的位置插入到set中去。

对于当前的数字x,在set中查询它的前驱的前驱,以及后继的后继,x的可行区间就为[前驱的前驱+1,x]和[x,后继的后继-1]。(为什么?这样的话,x在这两个区间内都是次大值)

然后就可以合并为一个区间啦,在可持久化trie中查询即可。

 

02/20
10:42
可持久化数据结构 数据结构

BZOJ 4546 codechef XRQRS 可持久化trie

Description

给定一个初始时为空的整数序列(元素由1开始标号)以及一些询问: 类型1:在数组后面就加入数字x。 类型2:在区间L…R中找到y,最大化(x xor y)。 类型3:删除数组最后K个元素。 类型4:在区间L…R中,统计小于等于x的元素个数。 类型5:在区间L…R中,找到第k小的数。

Input

输入数据第一行为一个整数q,表示询问个数,接下来q行,每行一条询问 对应题目描述。 类型1的询问格式为“1 x”。 类型2的询问格式为“2 L R x”。 类型3的询问格式为“3 k”。 类型4的询问格式为“4 L R x”。 类型5的询问格式为“5 L R k”。

Output

对于每个2、4、5询问输出一行对应答案

Sample Input

10

1 8

5 1 1 1

1 2

2 2 2 7

2 2 2 7

1 1

4 2 2 2

2 1 2 3

4 1 3 5

1 6

Sample Output

8

2

2

1

8

2

HINT

令N表示每次询问前数组中元素的个数

1<=L<=R<=N

1<=x<=500,000

对于第三类询问 1<=k<=N

对于第五类询问 k<=R-L+1

1<=N<=500,000

Source

 

Solution

可持久化trie,写法和主席树差不多,注意数组大小。

 

02/19
15:16
可持久化数据结构 数据结构

BZOJ 3261 最大异或和 可持久化trie

Description

给定一个非负整数序列 {a},初始长度为 N。
有 M个操作,有以下两种操作类型:

1 、A x:添加操作,表示在序列末尾添加一个数 x,序列的长度 N+1。 2 、Q l r x:询问操作,你需要找到一个位置 p,满足 l<=p<=r,使得:

a[p] xor a[p+1] xor ... xor a[N] xor x 最大,输出最大是多少。

Input

第一行包含两个整数 N ,M,含义如问题描述所示。
第二行包含 N个非负整数,表示初始的序列 A 。

接下来 M行,每行描述一个操作,格式如题面所述。

Output

假设询问操作有 T个,则输出应该有 T行,每行一个整数表示询问的答案。

Sample Input

5 5

2 6 4 3 6

A 1

Q 3 5 4

A 4

Q 5 7 0

Q 3 6 6

对于测试点 1-2,N,M<=5 。

对于测试点 3-7,N,M<=80000 。

对于测试点 8-10,N,M<=300000。

其中测试点 1, 3, 5, 7, 9保证没有修改操作。

对于 100%的数据,0<=a[i]<=10^7。

Sample Output

4

5

6

HINT

对于 100% 的数据, 0<=a[i]<=10^7 。

Source

 

Solution

可持久化trie……写法和主席树差不多。

首先定义一个bi为前i个数字的异或和,询问max(b[n]^x^b[p]) l ≤ p ≤ r。

把b数组插入到trie中,查询的时候很容易想到贪心的做法。

在数组前放一个0,会更好处理

 

02/1
19:52
数据结构 线段树

GSS3 - Can you answer these queries III 线段树-最大连续子段和

You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations: modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

Input

The first line of input 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 following form: 0 x y: modify Ax into y (|y|<=10000). 1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

Output

For each query, print an integer as the problem required.

Example

Input:
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3

Output:
6
4
-3

 

还是最大连续子段和,只是加了修改操作,同GSS1

 

01/25
11:31
数据结构 线段树

SPOJ GSS1 - Can you answer these queries I 线段树-最大连续子段和

You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows: Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }. Given M queries, your program must output the results of these queries.

Input

The first line of the input file contains the integer N. In the second line, N numbers follow. The third line contains the integer M. M lines follow, where line i contains 2 numbers xi and yi.

Output

Your program should output the results of the M queries, one query per line.

Example

Input:
3
-1 2 3
1
1 2
Output:
2

题意:给定一个序列,每次询问一个区间的最大连续子段和。

线段树,维护左起最大连续子段和,右起最大连续子段和,最大连续子段和,以及区间和。

在询问时,一共有三种情况: Ⅰ 最大连续子段和在左区间,直接递归查询 Ⅱ 最大连续子段和在右区间,同上 Ⅲ 最大连续子段和跨越左右区间,那么,对左区间最大连续子段和,右区间最大连续子段和,和左区间右起最大连续子段和 右区间左起最大连续子段和的和 取max即可

 

01/10
10:43
数据结构 树套树 线段树

BZOJ 3110 [Zjoi2013]K大数查询 树套树

Description

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

Input

第一行N,M 接下来M行,每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5

1 1 2 1

1 1 2 2

2 1 1 2

2 1 1 1

2 1 2 3

Sample Output

1

2

1

HINT

【样例说明】

第一个操作 后位置 1 的数只有 1 , 位置 2 的数也只有 1 。 第二个操作 后位置 1

的数有 1 、 2 ,位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是

1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3

大的数是 1 。‍

N,M<=50000,N,M<=50000

a<=b<=N

1操作中abs(c)<=N

2操作中c<=Maxlongint

Source

Solution

树套树,外层权值线段树、内层区间线段树。 原本想写区间线段树套权值线段树的,可是发现修改不会,好像要标记永久化……然而蒟蒻不会。

询问的时候,采用类似二分的方式,查询[ 1,mid ] ([ mid + 1, n ])有多少在询问的区间内,如果<排名,就往右(左),否则往左(右)。 听说这题根本就没有负数?233

 

01/6
18:11
图论 数据结构 树链剖分 线段树

BZOJ 1036 [ZJOI2008]树的统计Count 树链剖分

Description

一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成 一些操作: I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意:从点u到点v的路径上的节点包括u和v本身

Input

输入的第一行为一个整数n,表示节点的个数。接下来n – 1行,每行2个整数a和b,表示节点a和节点b之间有 一条边相连。接下来n行,每行一个整数,第i行的整数wi表示节点i的权值。接下来1行,为一个整数q,表示操作 的总数。接下来q行,每行一个操作,以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 对于100%的数据,保证1<=n<=30000,0<=q<=200000;中途操作中保证每个节点的权值w在-30000到30000之间。

Output

对于每个“QMAX”或者“QSUM”的操作,每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

HINT

 

Source

 

树链剖分……剖完之后线段树维护。

 

12/24
16:31
主席树 数据结构

BZOJ 2588 Spoj 10628. Count on a tree 主席树|倍增lca

Description

给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案,初始为0,即第一个询问的u是明文。

Input

第一行两个整数N,M。 第二行有N个整数,其中第i个整数表示点i的权值。 后面N-1行每行两个整数(x,y),表示点x到点y有一条边。 最后M行每行两个整数(u,v,k),表示一组询问。

Output

M行,表示每个询问的答案。

Sample Input

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2

Sample Output

2
8
9
105
7

HINT

HINT:
N,M<=100000 暴力自重。。。

Source

鸣谢seter

树上建主席树就好了呀。每次查询,先倍增求lca, 然后根据 tree[tree[x].l].cnt + tree[tree[y].l].cnt - tree[tree[z].l].cnt - tree[tree[F].l].cnt 决定往左边还是往右边走。

x y 是给定的两点 z是lca F是fa[lca]

犯了一些sb错误,比如 求jump数组的时候放到了dfs外面……

 

12/24
09:26
主席树 数据结构

BZOJ 3524 [Poi2014]Couriers 主席树

Description

给一个长度为n的序列a。1≤a[i]≤n。 m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。

Input

第一行两个数n,m。 第二行n个数,a[i]。 接下来m行,每行两个数l,r,表示询问[l,r]这个区间。

Output

m行,每行对应一个答案。

Sample Input

7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6

Sample Output

1
0
3
0
4

HINT

【数据范围】

n,m≤500000
2016.7.9重设空间,但未重测!

Source

By Dzy

主席树。

 

12/24
08:06
主席树 数据结构 模板

POJ 2104 K-th Number 主席树

Description

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment. That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?" For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Input

The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000). The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given. The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

Output

For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

Sample Input

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Sample Output

5
6
3

Hint

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

Source

Northeastern Europe 2004, Northern Subregion

主席树的模板题。

主席树,即函数式线段树,支持查找历史版本,即可持久化……

如果每个节点都新建一棵线段树的话,会MLE。所以,每次建树,只需要建更改了的那一部分,其他的指向之前的即可。

另:主席树是一种离线数据结构,必须知道所有数字的范围。

一般需要离散化。

 

12/21
21:57
平衡树 数据结构

BZOJ 1251 序列终结者 splay

Description

网上有许多题,就是给定一个序列,要你支持几种操作:A、B、C、D。一看另一道题,又是一个序列 要支持几种操作:D、C、B、A。尤其是我们这里的某人,出模拟试题,居然还出了一道这样的,真是没技术含量……这样 我也出一道题,我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠,没有什么其他的意思。这道题目 就叫序列终结者吧。 【问题描述】 给定一个长度为N的序列,每个序列的元素是一个整数(废话)。要支持以下三种操作: 1. 将[L,R]这个区间内的所有数加上V。 2. 将[L,R]这个区间翻转,比如1 2 3 4变成4 3 2 1。 3. 求[L,R]这个区间中的最大值。 最开始所有元素都是0。

Input

第一行两个整数N,M。M为操作个数。 以下M行,每行最多四个整数,依次为K,L,R,V。K表示是第几种操作,如果不是第1种操作则K后面只有两个数。

Output

对于每个第3种操作,给出正确的回答。

Sample Input

4 4
1 1 3 2
1 2 4 -1
2 1 3
3 2 4

Sample Output

2
【数据范围】 N<=50000,M<=100000。

HINT

 

Source

 

一道splay的题。

首先,为了保证数字在平衡树中保持在序列中的相对位置,在插入的时候,采用类似分治的方法。

对区间进行操作时,将l-1的位置转到根,r+1的位置转到跟的右儿子,则要操作的区间在l-1和r+1之间,打标记即可。

 

12/20
14:27
平衡树 数据结构 树套树 线段树

BZOJ 3196 二逼平衡树 树套树

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作: 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x,且最大的数) 5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数,表示有序序列 下面有m行,opt表示操作标号 若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名 若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数 若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k 若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱 若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围:n,m<=50000 2.序列中每个数的数据范围:[0,1e8]

3.虽然原题没有,但事实上5操作的k可能为负数

Source

 

一道树套树的题,还是比较裸的…然而调了半天,终归还是我太弱啊 TAT

 

12/19
15:04
平衡树 数据结构

BZOJ 3223 文艺平衡树 splay

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n) m表示翻转操作次数 接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

Output

输出一行n个数字,表示原始序列经过m次变换后的结果

Sample Input

5 3
1 3
1 3
1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

Source

平衡树

区间翻转,交换左右儿子即可。

 

12/19
08:38
平衡树 数据结构 模板

BZOJ 3224 普通平衡树 splay

Description

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  1. 插入x数
  2. 删除x数(若有多个相同的数,因只删除一个)
  3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x,且最大的数)
  6. 求x的后继(后继定义为大于x,且最小的数)

Input

第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数,表示对应答案

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

HINT

1.n的数据范围:n<=100000 2.每个数的数据范围:[-1e7,1e7] 数据如下 http://pan.baidu.com/s/1jHMJwO2

Source

平衡树