Uva 1479 - Graph and Queries

ACM

国庆快乐~~~(^__^) 嘻嘻……

题目链接

题目链接

题意

题解

  • 题目共有三种操作：query表示查询x节点的第k大的值;delete表示删除编号为x的边所连接的两点的关系;change表示改变x节点的权值为value。

  • 若正向的模拟，那么删除边的操作比较的难以实现。因为treap不能实现分裂的操作。而splay是能够实现合并与分裂的操作，但是是第k大的，不能删除任意两点间的

  • 此时想到的是完全反过来的逆过程：我们最开始得到的图是删除了所有应该删去的边的图。query的操作不改变;delete的操作变成了add_edge的操作；change的操作变成了将值变成原来的值的操作。

此题的坑点

  • 又一次的栽在了读入的操作上，注意数字和字母间的读入操作加个getchar()或者空格（Uva太垃圾了，一直显示的是RE，害的我调了三天。。。）
  • 数组大小的，防止越界
  • 在插入操作的时候不要使用结构体里面的cmp函数。因为可能插入相同的值

AC代码

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4+10;
const int maxm = 6e5+10;
const int maxc = 5e5+10;
struct Node{
    Node* ch[2];
    int value;//保存的是节点的值
    int rank_value;//用随机函数生成名次，从而使时间复杂度保持O(logn)
    int s;//增加这个size属性，从而实现从联通的块中寻找第K大的数
    Node(int value):value(value){
        ch[0] = ch[1] = NULL;
        rank_value = rand();
        s = 1;
    }
    int cmp(int x){
        if(x == value) return -1;
        return x<value?0:1;
    }
    void maintain(){
       s = 1;
       if(ch[0] != NULL) s+=ch[0]->s;
       if(ch[1] != NULL) s+=ch[1]->s;
    }
};
//旋转的操作，使子节点旋转到根部
//rt代表根节点，d表示旋转的类型,d=0表示左旋,d=1表示右旋
//若使右孩子旋到根节点，则左旋；
//若使左孩子旋到根节点，则右旋；
void rotate(Node* &rt, int d){
    Node* k = rt->ch[d^1];
    rt->ch[d^1] = k->ch[d];
    k->ch[d] = rt;
    rt->maintain();
    k->maintain();
    rt = k;
}
void insert(Node* &rt, int value){
    if(rt == NULL) rt = new Node(value);
    else{
        int d = rt->value<value?1:0;//这里不能使用cmp函数，因为插入的值可能相等！！！
        insert(rt->ch[d], value);
        //举一个例子便于理解：
        //若右孩子的rank大于根节点的rank,由于不满足名次树的性质，
        //则要将右孩子旋转到根节点，进行左旋。
        if(rt->ch[d]->rank_value>rt->rank_value){
            rotate(rt, d^1);
        }
    }
    rt->maintain();
}
void remove(Node* &rt, int value){
    int d = rt->cmp(value);
    Node * temp = rt;
    //若找到了要删除的节点，都是转换成该节点只有一个孩子
    //若该节点有两个孩子，则将rank较大的孩子进行旋转，旋转到根部
    //最后转换成只有一个孩子进行删除。
    if(d == -1){
        if(rt->ch[0] == NULL) rt = rt->ch[1], delete temp;
        else if(rt->ch[1] == NULL) rt = rt->ch[0], delete temp;
        else{
            int d2 = (rt->ch[0]->rank_value<rt->ch[1]->rank_value)?1:0;
            rotate(rt, d2);
            remove(rt->ch[d2], value);
        }
    }
    //若没有找到孩子的话，则递归的继续向下寻找。
    else{
        remove(rt->ch[d], value);
    }
    if(rt != NULL) rt->maintain();
}
struct Command{
    char type;
    int x, p;
}command[maxc];
Node* root[maxn];
int n, m, weight[maxn], from[maxm], to[maxm];
int fa[maxn];
//用并查集实现连通的团的查询和修改
int findset(int x){
    return fa[x] == x? x:fa[x] = findset(fa[x]);
}
//找到一个连通块第K大的值
int kth(Node* rt, int k){
    if(k<=0||rt->s<k||rt == NULL) return 0;
    int k1;
    if(rt->ch[1]!=NULL){
        k1 = rt->ch[1]->s;
    }
    else k1 = 0;
    if(k1+1 == k) return rt->value;
    else if(k<=k1) return kth(rt->ch[1], k);
    else return kth(rt->ch[0], k-k1-1);
}
//两个块的合并
void mergeto(Node* &sc, Node* &dst){
    if(sc->ch[0]!=NULL) mergeto(sc->ch[0], dst);
    if(sc->ch[1]!=NULL) mergeto(sc->ch[1], dst);
    insert(dst, sc->value);
    delete sc;
    sc = NULL;
}
//初始化root的集合，使每个节点都是一个单独的块
void init_tree(Node* &rt){
    if(rt->ch[0] != NULL) init_tree(rt->ch[0]);
    if(rt->ch[1] != NULL) init_tree(rt->ch[1]);
    delete rt;
    rt = NULL;
}
void add_edge(int edge_index){
    int u = from[edge_index];
    int v = to[edge_index];
    u = findset(u);
    v = findset(v);
    if(u != v){
        if(root[u]->s<root[v]->s){
            fa[u] = v;
            mergeto(root[u], root[v]);
        }
        else{
            fa[v] = u;
            mergeto(root[v], root[u]);
        }
    }
}
//改变点的权重
void change(int x, int value){
    int u = findset(x);
    remove(root[u], weight[x]);
    insert(root[u], value);
    weight[x] = value;
}
int query_cnt;
long long query_tot;
void query(int x, int k){
    query_cnt++;
    query_tot += kth(root[findset(x)], k);
}
bool removed[maxm];
int main()
{
    int kase = 0;
    while(scanf("%d %d", &n, &m) == 2&&n){
        for(int i=1; i<=n; i++) scanf("%d", &weight[i]);
        for(int i=1; i<=m; i++) scanf("%d %d", &from[i], &to[i]);
        int c = 0;
        memset(removed, 0, sizeof(removed));
        while(true){
            char type;
            int x, p;
            getchar();
            scanf("%c", &type);
            if(type == 'E') break;
            else if(type == 'C') {
                scanf("%d%d", &x, &p);
                int temp = p;
                p = weight[x];
                weight[x] = temp;
            }
            else if(type == 'D'){
                scanf("%d", &x);
                removed[x] = true;
            }
            else if(type == 'Q'){
                scanf("%d%d", &x, &p);
            }
            command[c++] = Command{type, x, p};
        }
        for(int i=1; i<=n; i++){
            fa[i] = i;
            if(root[i] != NULL) init_tree(root[i]);
            root[i] = new Node(weight[i]);
        }
        for(int i=1; i<=m; i++){
            //cout<<233<<endl;
            if(!removed[i]) add_edge(i);
        }
        //cout<<root[1]<<endl;
        query_cnt = query_tot = 0;
        for(int i=c-1; i>=0; i--){
            //cout<<command[i].x<<" "<<command[i].p<<endl;
            if(command[i].type == 'C') change(command[i].x, command[i].p);
            if(command[i].type == 'Q') query(command[i].x, command[i].p);
            if(command[i].type == 'D') add_edge(command[i].x);
            //cout<<query_cnt<<" "<<query_tot<<endl;
        }
        printf("Case %d: %.6lf\n", ++kase, query_tot*1.0/query_cnt);
    }
    return 0;
}

treap

介绍

treap有键值(value)和优先级(rank_value)的树，又称为名次树。

成员函数及功能

属性：

1
2
3
4
5
6
struct Node{
    Node* ch[2];
    int value;
    int rank_value;
    int s;
}

void rotate(Node* &rt, int d)
功能：将一个子节点翻转到根部

void insert(Node* &rt, int value)
功能：将一个值插入到树中

void remove(Node* &rt, int value)
功能：将特定的值从树中删除

bool find(Node* &rt, int value)
功能：查询一个值是否在树中

int kth(Node* rt, int k)
功能：查询第k大的数字

int rank(Node* rt, int value)
功能：查询value数值是第几小的，与kth()功能差不多

模板代码：

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
// Rank Tree
// Rujia Liu
// 输入格式：
// m     操作有m个
// 1 x   插入元素x
// 2 x   删除元素x。如果成功，输入1，否则输出0
// 3 k   输出第k小元素。k=1为最小元素
// 4 x   输出值x的“名次”，即比x小的结点个数加1
#include<cstdlib>
struct Node {
  Node *ch[2]; // 左右子树
  int r; // 随机优先级
  int v; // 值
  int s; // 结点总数
  Node(int v = 0):v(v) { ch[0] = ch[1] = NULL; r = rand(); s = 1; }
  int cmp(int x) const {
    if (x == v) return -1;
    return x < v ? 0 : 1;
  }
  void maintain() {
    s = 1;
    if(ch[0] != NULL) s += ch[0]->s;
    if(ch[1] != NULL) s += ch[1]->s;
  }
};
void rotate(Node* &o, int d) {
  Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; 
  o->maintain(); k->maintain(); o = k;
}
void insert(Node* &o, int x) {
  if(o == NULL) o = new Node(x);
  else {
    int d = (x < o->v ? 0 : 1); // 不要用cmp函数，因为可能会有相同结点
    insert(o->ch[d], x);
    if(o->ch[d]->r > o->r) rotate(o, d^1);
  }
  o->maintain();
}
Node* find(Node* o, int x) {
  if(o == NULL) return NULL;
  if(x == o->v) return o;
  return x < o->v ? find(o->ch[0], x) : find(o->ch[1], x);
}
// 要确保结点存在
void remove(Node* &o, int x) {
  int d = o->cmp(x);
  int ret = 0;
  if(d == -1) {
    Node* u = o;
    if(o->ch[0] != NULL && o->ch[1] != NULL) {
      int d2 = (o->ch[0]->r > o->ch[1]->r ? 1 : 0);
      rotate(o, d2); remove(o->ch[d2], x);
    } else {
      if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0];
      delete u;
    }
  } else
    remove(o->ch[d], x);
  if(o != NULL) o->maintain();
}
int kth(Node* o, int k) {
  if(o == NULL || k <= 0 || k > o->s) return 0;
  int s = (o->ch[0] == NULL ? 0 : o->ch[0]->s);
  if(k == s+1) return o->v;
  else if(k <= s) return kth(o->ch[0], k);
  else return kth(o->ch[1], k-s-1);
}
// 在以o为根的子树中，值比x小的结点总数加1
//与kth是相对的
int rank(Node* o, int x) {
  if(o == NULL) return 1;
  if(x <= o->v) return rank(o->ch[0], x);
  return rank(o->ch[1], x) + (o->ch[0] == NULL ? 0 : o->ch[0]->s) + 1;
}
#include<cstdio>
const int INF = 1000000000;
int main() {
  int m, c, v;
  Node* root = new Node(INF);
  while(scanf("%d", &m) == 1) {
    while(m--) {
      scanf("%d%d", &c, &v);
      if(c == 1) insert(root, v);
      else if(c == 2) {
        Node* o = find(root, v);
        printf("%d\n", o == NULL ? 0 : 1);
        if(o != NULL) remove(root, v);
      }
      else if(c == 3) printf("%d\n", kth(root, v));
      else if(c == 4) printf("%d\n", rank(root, v));
    }
  }
  return 0;
}

编写代码时要注意的

当实现rotate的时候，心中时刻想着一张图：当将右儿子旋转到根部的时候，要进行左旋的操作。分成三步走就行了。

当实现insert的时候，不断的寻找根部，最后插入了，若rank大于根节点的rank,则进行相应的旋转

当实现delete的时候，若要删除的节点有两个孩子，那么将rank较大的旋转到根部，使之转换成只有一个孩子的情况，然后删除该节点。

总之，心中一定要有一张树的图，进行相应的操作的时候，在心里面进行相应的操作

启发式合并

假设有两棵树T1和T2，节点的数量分别是n1和n2,若n1<n2,显然把T1合并到T2比较的高效，即把T1中的节点一一插入到T2中，时间复杂度为O(\(n_1log(n_2)\))
至于为什么这个名词，请自行百度。

未解决的问题

本文标题:Uva 1479 - Graph and Queries

文章作者:Babydragon

发布时间:2017-10-01, 21:56:26

最后更新:2018-03-23, 13:36:28

原始链接:http://baolintian.github.io/2017/10/01/Uva-1479-Graph-and-Queries/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 题目链接
  2. 2. 题意
  3. 3. 题解
  4. 4. 此题的坑点
  5. 5. AC代码
  6. 6. treap
    1. 6.1. 介绍
    2. 6.2. 成员函数及功能
    3. 6.3. 编写代码时要注意的
  7. 7. 启发式合并
  8. 8. 未解决的问题
{{ live2d() }}