Loi_Vampire's Blog

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

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

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

无回复 197 views

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外面……

View Code
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int SZ = 1e5 + 10;
 
struct Edge
{
    int f, t;
}es[SZ * 2];
struct SGT
{
    int l, r, cnt;
}tree[SZ * 40];
int n, m, lsh[SZ], first[SZ * 2], nxt[SZ * 2], num[SZ], tot = 1, cnt, len;
int fa[SZ], jump[SZ][25], depth[SZ], rt[SZ], Tcnt;
bool vis[SZ];
 
void read(int &num)
{
    num = 0;
    char c = getchar(); int f = 1;
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while('0' <= c && c <= '9'){num = num * 10 + (c - '0'); c = getchar();}
    num *= f;
}
 
void build(int f, int t)
{
    es[++tot] = (Edge){f, t}; nxt[tot] = first[f]; first[f] = tot;
    es[++tot] = (Edge){t, f}; nxt[tot] = first[t]; first[t] = tot;
}
 
void insert(int l, int r, int x, int &y, int v)
{
    y = ++Tcnt;
    tree[y] = tree[x];
    tree[y].cnt++;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(v <= mid) insert(l, mid, tree[x].l, tree[y].l, v);
    else insert(mid + 1, r, tree[x].r, tree[y].r, v);
}
 
void dfs(int u)
{
    insert(1, n, rt[fa[u]], rt[u], num[u]);
    for(int j = 1; j <= 20; j++)
        jump[u][j] = jump[jump[u][j - 1]][j - 1];
    vis[u] = 1;
    for(int i = first[u]; i; i = nxt[i])
    {
        int v = es[i].t;
        if(vis[v]) continue;
        fa[v] = jump[v][0] = u;
        depth[v] = depth[u] + 1;
        dfs(v);
    }
}
 
int get_lca(int u, int v)
{
    if(depth[u] < depth[v]) swap(u, v);
    int t = depth[u] - depth[v];
    for(int i = 0; i <= 20; i++)
        if(t & (1 << i))
            u = jump[u][i];
    for(int i = 20; i >= 0; i--)
        if(jump[u][i] != jump[v][i])
            u = jump[u][i], v = jump[v][i];
    return u == v ? u : fa[u];
}
 
int ask(int l, int r, int x, int y, int z, int F, int k)
{
    if(l == r) return l;
    int mid = (l + r) >> 1;
    int tmp = tree[tree[x].l].cnt + tree[tree[y].l].cnt - tree[tree[z].l].cnt - tree[tree[F].l].cnt;
    if(tmp >= k) return ask(l, mid, tree[x].l, tree[y].l, tree[z].l, tree[F].l,  k);
    else return ask(mid + 1, r, tree[x].r, tree[y].r, tree[z].r, tree[F].r, k - tmp);
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &num[i]), lsh[i] = num[i];
    sort(lsh + 1, lsh + 1 + n);
    len = unique(lsh + 1, lsh + 1 + n) - lsh - 1;
    for(int i = 1; i <= n; i++)
        num[i] = lower_bound(lsh + 1, lsh + 1 + len, num[i]) - lsh;
    int u, v;
    for(int i = 1; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        build(u, v);
    }
    depth[1] = 1;
    dfs(1);
    int k, lastans = 0;
    while(m--)
    {
        scanf("%d%d%d", &u, &v, &k);
        u ^= lastans;
        int lca = get_lca(u, v);
        printf("%d", lastans = lsh[ask(1, n, rt[u], rt[v], rt[lca], rt[fa[lca]], k)]);
        if(m) puts("");
    }
    return 0;
}

 

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

BZOJ 3524 [Poi2014]Couriers 主席树

无回复 159 views

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

主席树。

View Code
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstdio>
using namespace std;
const int SZ = 1e6 + 10;
 
struct SGT
{
    int l, r, cnt;
}tree[SZ * 10];
int rt[SZ], Tcnt;
 
void read(int &num)
{
    num = 0;
    char c = getchar(); int f = 1;
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while('0' <= c && c <= '9'){num = num * 10 + (c - '0'); c = getchar();}
    num *= f;
}
 
void insert(int l, int r, int x, int &y, int v)
{
    y= ++Tcnt;
    tree[y] = tree[x];
    tree[y].cnt++;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(v <= mid) insert(l, mid, tree[x].l, tree[y].l, v);
    else insert(mid + 1, r, tree[x].r, tree[y].r, v);
}
 
int ask(int l, int r, int x, int y, int k)
{
    while(l != r)
    {
        if(tree[y].cnt - tree[x].cnt <= k) return 0;
        int mid = (l + r) >> 1;
        if(tree[tree[y].l].cnt - tree[tree[x].l].cnt > k)
        {
            x = tree[x].l; y = tree[y].l; r = mid;
        }
        else if(tree[tree[y].r].cnt - tree[tree[x].r].cnt > k)
        {
            x = tree[x].r; y = tree[y].r; l = mid + 1;
        }
        else return 0;
    }
    return l;
}
 
int main()
{
    int n, m;
    read(n), read(m);
    int  value;
    for(int i = 1; i <= n; i++)
    {
        read(value);
        insert(1, n, rt[i - 1], rt[i], value);
    }
    int l, r;
    while(m--)
    {
        read(l), read(r);
        printf("%d\n", ask(1, n, rt[l - 1], rt[r], (r - l + 1) / 2));
    }
    return 0;
}

 

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

POJ 2104 K-th Number 主席树

无回复 253 views

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。所以，每次建树，只需要建更改了的那一部分，其他的指向之前的即可。

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

一般需要离散化。

View Code
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int SZ = 5e6 + 10;
 
struct SGT
{
    int l, r, cnt;
}tree[SZ];
int lsh[SZ], rt[SZ], num[SZ], Tcnt, cnt;
 
void insert(int l, int r, int x, int &y, int value)
{
    y = ++Tcnt;
    tree[y] = tree[x];
    tree[y].cnt++;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(value <= mid) insert(l, mid, tree[x].l, tree[y].l, value);
    else insert(mid + 1, r, tree[x].r, tree[y].r, value);
}
 
int ask(int l, int r, int x, int y, int k)
{
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(tree[tree[y].l].cnt - tree[tree[x].l].cnt >= k)
        return ask(l, mid, tree[x].l, tree[y].l, k);
    else return ask(mid + 1, r, tree[x].r, tree[y].r, k - (tree[tree[y].l].cnt - tree[tree[x].l].cnt));
}
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &num[i]);
        lsh[++cnt] = num[i];
    }    
    sort(lsh + 1, lsh + 1 + cnt);
    int len = unique(lsh + 1, lsh + 1 + cnt) - lsh - 1;
    for(int i = 1; i <= n; i++)
    {
        num[i] = lower_bound(lsh + 1, lsh + 1 + len, num[i]) - lsh;
        insert(1, len, rt[i - 1], rt[i], num[i]);
    }
    int l, r, k;
    while(m--)
    {
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", lsh[ask(1, len, rt[l - 1], rt[r], k)]);
    }
    return 0;
}