Chenfan Blog

Do cool things that matter.

0%

VIJOS P1081 野生动物园 SBT、划分树模板

Posted on Edited on In

野生动物园

描述

cjBBteam拥有一个很大的野生动物园。这个动物园坐落在一个狭长的山谷内，这个区域从南到北被划分成N个区域，每个区域都饲养着一头狮子。这些狮子从北到南编号为1,2,3,…,N。每头狮子都有一个觅食能力值Ai，Ai越小觅食能力越强。饲养员cmdButtons决定对狮子进行M次投喂，每次投喂都选择一个区间[I,J]，从中选取觅食能力值第K强的狮子进行投喂。值得注意的是，cmdButtons不愿意对某些区域进行过多的投喂，他认为这样有悖公平。因此cmdButtons的投喂区间是互不包含的。你的任务就是算出每次投喂后，食物被哪头狮子吃掉了。

输入格式

输入第一行有两个数N和M。此后一行有N个数，从南到北描述狮子的觅食能力值。此后M行，每行描述一次投喂。第t+2的三个数I,J,K表示在第t次投喂中，cmdButtons选择了区间[I,J]内觅食能力值第K强的狮子进行投喂。

输出格式

输出有M行，每行一个整数。第i行的整数表示在第i次投喂中吃到食物的狮子的觅食能力值。

样例输入

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

样例输出

3
2

分析

解法一、平衡树

由题目给出的区间互相不包含可以得出，若将每次询问的区间按照起始区域进行排序，那一定是一段接一段，只有可能是两种情况：

下一段的左端与上一段的右端不相交或者相交。

这两种情况都是前面的数据与后面的数据互不影响，因此将区间排序之后，对于每一个区间，删除掉前面多余的，插入后面不够的，使平衡树中仅留下该区间中的数据，然后直接找第k小即可。

SBT可解。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : VIJOS1081
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 100010

int sons[MAXN][2];
int size[MAXN],data[MAXN];
int sbt=0,sbttail=0;

void rotate(int &t,int w) //rotate(&node,0/1)
{
    int k=sons[t][1-w];
    if (!k) return ;
    sons[t][1-w]=sons[k][w];
    sons[k][w]=t;
    size[k]=size[t];
    size[t]=size[sons[t][0]]+size[sons[t][1]]+1;
    t=k;
}

void maintain(int& t,bool flag) //maintain(&node,flag)
{
    if (!t) return ;
    if (!flag)
        if (size[sons[sons[t][0]][0]]>size[sons[t][1]]) rotate(t,1);
        else if (size[sons[sons[t][0]][1]]>size[sons[t][1]]) 
        {
            rotate(sons[t][0],0);
            rotate(t,1);
        } else return ;
    else
        if (size[sons[sons[t][1]][1]]>size[sons[t][0]]) rotate(t,0);
        else if (size[sons[sons[t][1]][0]]>size[sons[t][0]])
        {
            rotate(sons[t][1],1);
            rotate(t,0);
        } else return ;
    
    maintain(sons[t][0],false);
    maintain(sons[t][1],true);
    maintain(t,false);
    maintain(t,true);
}

void insert(int& t,int v) //insert(&root,0,value)
{
    if (!t)
    {
        sbttail++;
        data[sbttail]=v;
        size[sbttail]=1;
        sons[sbttail][0]=0;
        sons[sbttail][1]=0;
        t=sbttail;
    } else 
    {
        size[t]++;
        if (v<data[t]) insert(sons[t][0],v);
        else insert(sons[t][1],v);
        maintain(t,v>=data[t]);
    }
}

int del(int& t,int v) //del(&root,key)
{
    size[t]--;
    if (v==data[t]||(v<data[t]&&sons[t][0]==0)||(v>data[t]&&sons[t][1]==0))
    {
        int ret=data[t];
        if (sons[t][0]==0||sons[t][1]==0) t=sons[t][1]+sons[t][0];
        else data[t]=del(sons[t][0],data[t]+1);
        return ret;
    } else
    if (v<data[t]) return del(sons[t][0],v);
    else return del(sons[t][1],v);
}

int select(int t,int k)
{
    if (k==size[sons[t][0]]+1) return t;
    if (k<=size[sons[t][0]]) return select(sons[t][0],k);
    else return select(sons[t][1],k-1-size[sons[t][0]]);
}

typedef struct nod
{
    int i,l,r,k;
} node;
node d[50010];

bool op(node a,node b)
{
    if (a.l==b.l) return a.r<b.r;
    else return a.l<b.l;
}

int a[MAXN];

typedef struct nod1
{
    int i,ans;
} node1;
node1 out[50010];

bool op1(node1 a,node1 b)
{
    return a.i<b.i;
}

int main()
{
    freopen("1.txt","r",stdin);

    sbt=0,sbttail=0;
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=m;i++) 
    {
        scanf("%d%d%d",&d[i].l,&d[i].r,&d[i].k);
        d[i].i=i;
    }
    sort(&d[1],&d[m+1],op);
    
    int l=0,r=0;
    for (int i=1;i<=m;i++)
    {
        if (r<d[i].l)
        {
            sbt=0;
            sbttail=0;
            for (int j=d[i].l;j<=d[i].r;j++) insert(sbt,a[j]);
        } else 
        {
            for (int j=l;j<d[i].l;j++) del(sbt,a[j]);
            for (int j=r+1;j<=d[i].r;j++) insert(sbt,a[j]);
        }
        l=d[i].l;
        r=d[i].r;
        int temp=select(sbt,d[i].k);
        
        out[i].i=d[i].i;
        out[i].ans=data[temp];
    }

    sort(&out[1],&out[m+1],op1);
    for (int i=1;i<=m;i++) printf("%d\n",out[i].ans);

    return 0;
}

解法二、划分树

划分树是一种类似快排的数据结构，可以快速在O（logn）的时间内直接求出某个区间内的k值。

然后本题就是……一棵裸的划分树，直接套即可

。。。。。。最后的结果是，不知道为什么比SBT要慢很多，直观的感觉上划分树没有多余的删除操作，应该会快很多的

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
/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : VIJOS1081_SortTree
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 100010

int a[MAXN],dp[20][MAXN],tree[20][MAXN];

void maketree(int c,int l,int r)
{
    int mid=(l+r)/2,ls=l,rs=mid+1,num=0;

    for (int i=mid;i>=l&&a[i]==a[mid];i--) num++;
    for (int i=l;i<=r;i++)
    {
        if (i==l) dp[c][i]=0;
        else dp[c][i]=dp[c][i-1];

        if (tree[c][i]<a[mid])
        {
            dp[c][i]++;
            tree[c+1][ls]=tree[c][i];
            ls++;
        } else 
        if (tree[c][i]>a[mid])
        {
            tree[c+1][rs]=tree[c][i];
            rs++;
        } else 
        {
            if (num)
            {
                num--;
                dp[c][i]++;
                tree[c+1][ls]=tree[c][i];
                ls++;
            } else 
            {
                tree[c+1][rs]=tree[c][i];
                rs++;
            }
        }
    }

    if (l==r) return ;
    maketree(c+1,l,mid);
    maketree(c+1,mid+1,r);
}

int query(int c,int l,int r,int ql,int qr,int k)
{
    if (l==r) return tree[c][l];
    int s,ss,mid=(l+r)/2;

    if (l==ql)
    {
        s=0;
        ss=dp[c][qr];
    } else 
    {
        s=dp[c][ql-1];
        ss=dp[c][qr]-s;
    }
    if (k<=ss) return query(c+1,l,mid,l+s,l+s+ss-1,k);
    else return query(c+1,mid+1,r,mid-l+1+ql-s,mid-l+1+qr-s-ss,k-ss);
}

int main()
{
    //freopen("1.in","r",stdin);
    //freopen("zoo8.in","r",stdin);
    //freopen("1.out","w",stdout);

    int n,m;
    scanf("%d%d",&n,&m);

    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        tree[0][i]=a[i];
    }
    sort(&a[1],&a[n+1]);

    maketree(0,1,n);

    for (int i=1;i<=m;i++)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",query(0,1,n,l,r,k));
    }

    return 0;
}
Related Posts