Znzryb's Blog
0%

Posted on Edited on

题目大意

这篇笔记对应的是「set 自定义 cmp 排序」：讲的是在 C++ 里如何为 set（以及类似容器）自定义比较器 cmp，从而改变元素的排序规则（例如从大到小排序），以及与默认比较方式的区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <set>
#include <iterator>
using namespace std;
int p[7]={0,4,3,2,1};
struct cmp{
	bool operator()(int a,int b){
		if(a!=b) return p[a]<p[b];
	}
};
set<int,cmp > g; // 一般来说像set，priority_queue都是传入cmp，less<int> 这样的结构体
int main(){
	g.insert(1);g.insert(2);g.insert(3);g.insert(4);
	for(set<int>::iterator it=g.begin();it!=g.end();it++)
		cout<<*it<<endl;
	set<int>::iterator it=g.end();
	advance(it,-1);
	cout<<"back: "<<*it<<endl;
	g.clear();
	cout<<g.empty()<<endl;
}
1
2
3
4
5
6
4
3
2
1
back: 1
1

优先队列的比较符号是反的，解释详情见

https://www.nowcoder.com/discuss/353157988535967744

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <queue>
using namespace std;
struct cmp {
	bool operator() (pair<int, int> a,  pair<int, int> b)  {
		// 如果第二个元素不同，则按照第二个元素比较
		if (a.second != b.second)
			return a.second > b.second;  // 如果想要最小堆，这里使用 >
	}
};
int a[]={1,2,4,1,492,412,3};

1
2
3
4
5
6
1 1
1 2
1 3
2 6
3 9
1 1 2 3 4 412 492

Posted on Edited on

Wine 如何打开devcpp
wine “/Users/zzy/.wine/drive_c/Program Files (x86)/Dev-Cpp/devcpp.exe”

Posted on Edited on

题目大意

维护一个动态可重集合 M，需要支持以下操作：

  1. 插入一个数 x。

  2. 删除一个数 x（若有多个相同值，只删除一个）。

  3. 查询集合中严格小于 x 的元素个数，并将结果加 1 输出。

  4. 查询集合按从小到大排序后，第 x 小的数。

  5. 查询 x 的前驱：小于 x 且最大的数（不保证 x 在集合中，但保证答案存在）。

  6. 查询 x 的后继：大于 x 且最小的数（不保证 x 在集合中，但保证答案存在）。

P3224 [HNOI2012] 永无乡

主要是发现此题寻找第k大的连通块需要平衡二叉树，不学不行，故来学习。

参考博客

https://writings.sh/post/fhq-treap

其他OJ

https://loj.ac/p/104

参考视频

https://www.bilibili.com/video/BV1ft411E7JW/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675

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
#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
const ll MAXN=static_cast<ll>(1e5+10);
int cnt,root;

struct Node {
    int l,r;
    int val;
    int key;
    int size; // size
}fhq[MAXN];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int newnode(int val) {
    fhq[++cnt].val=val;
    fhq[cnt].key=rng();
    fhq[cnt].size=1;
    return cnt;
}

inline void update(int now) {
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}

// 分裂之后左子树全部是比val值<=的，右子树全部是比y>=的
//                         左子树    右子树
void split(int now,int val,int &x,int &y) {
    if(!now) x=y=0;
    else {
        if(fhq[now].val<=val) {
            x=now;
            // 继续分裂右子树，因为左树<=val，无需再进行分裂，右树还需要继续分裂
            split(fhq[now].r,val,fhq[now].r,y);
        }else {
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        update(now);
    }
}

int merge(int x,int y) {
    if(!x||!y) return x+y;
    // 按照二叉堆的性质，y一定再x的下面（大根堆）
    if(fhq[x].key>fhq[y].key) {
        // 按照二叉搜索树，x<y,y在x的右边，综上，y在x的右下
        fhq[x].r=merge(fhq[x].r,y);
        update(x);
        return x;
    }else {
        // 按照二叉堆的性质，x一定在y的下面（大根堆）
        fhq[y].l=merge(x,fhq[y].l);
        update(y);
        return y;
    }
}

int x,y,z;

inline void ins(int val) {
    // 按值分裂，将树分为x，y
    split(root,val,x,y);
    // 合并树x，树y，新节点val
    root=merge(merge(x,newnode(val)),y);
}

inline void del(int val) {
    split(root,val,x,z);
    // 此时y树上所有值全部等于val
    split(x,val-1,x,y);
    // 不要y树的根节点，也就是把他的左子树和右子树合并
    y=merge(fhq[y].l,fhq[y].r);
    root=merge(merge(x,y),z);
}

inline void getrank(int val) {
    split(root,val-1,x,y);
    cout<<fhq[x].size+1<<endl;
    root=merge(x,y);
}

inline void getnum(int rank) {
    int now=root;
    while(now) {
        if(fhq[fhq[now].l].size+1==rank)
            break;
        // 当前节点rank比较大，要找的点在左子树上，令当前节点为左子树
        else if(fhq[fhq[now].l].size>=rank)
            now=fhq[now].l;
        else {
            rank-=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    cout<<fhq[now].val<<endl;
}

inline void pre(int val) {
    split(root,val-1,x,y);
    // 前驱就是分裂出来的x树上最右边的点
    int now=x;
    // 不断向右走直到没有点了
    while (fhq[now].r) {
        now=fhq[now].r;
    }
    cout<<fhq[now].val<<endl;
    root=merge(x,y);
}

inline void nxt(int val) {
    split(root,val,x,y);
    int now=y;
    while (fhq[now].l)
        now=fhq[now].l;
    cout<<fhq[now].val<<endl;
    root=merge(x,y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) {
        int opt,xopt;
        cin>>opt>>xopt;
        switch (opt) {
            case 1:
                ins(xopt);
                break;
            case 2:
                del(xopt);
                break;
            case 3:
                getrank(xopt);
                break;
            case 4:
                getnum(xopt);
                break;
            case 5:
                pre(xopt);
                break;
            case 6:
                nxt(xopt);
                break;
        }
    }
}
// AC https://www.luogu.com.cn/record/190721203

Posted on Edited on

题目大意

有 nn 座岛（编号 1simn1sim n），每座岛有一个“重要度排名” pip_i（是 1∼n1\sim n 的一个排列，数值越小表示越重要）。初始有 m 座桥形成无向图，之后还会有 q 次操作：

  • B x y：在岛 x 与 y 之间新建一座桥。

  • Q x k：在当前与岛 x 连通的所有岛中，找出“重要度排名第 kk 小”的岛，输出该岛编号；若不存在则输出 −1-1。

思路讲解

这是此题的退化版（<10）

AC代码

心路历程（WA，TLE，MLE……）

40pts，TLE，不用平衡树stl的set合并太慢了。

Posted on Edited on

题目大意

给定一个有 N 个点、初始没有边的无向图，按顺序处理 Q 个操作：

  • 操作 1：在 u 与 v 之间新增一条边。

  • 操作 2：询问与点 v 连通的所有点中，点编号第 k 大的是多少；如果连通块大小不足 k，输出 -1。（题目保证 kle10k le 10）

这题总体上来说还是不难的，就是用并查集维护连通块，再用set维护第k大的点

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
//  https://atcoder.jp/contests/abc372/tasks/abc372_e
#include <iostream>
#include <vector>
#include <set>
#include <iterator>
using namespace std;
const int maxn=2e5+10;
int n,q,op,u,v,k,fa[maxn];  // fa is disjointed set to upd connected components
// vector <int> g[maxn];
set <int,greater<int> > g[maxn];
int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
        return fa[x];
    }else{
        return x;
    }
}
void unionn(int i,int j){
    int i_fa=find(i);
    int j_fa=find(j);
    fa[j_fa]=i_fa;
    g[i_fa].insert(g[j_fa].begin(),g[j_fa].end());
    while(g[i_fa].size()>10) {
        set<int>::iterator it=g[i_fa].end();
        advance(it,-1);
        g[i_fa].erase(it);
    }
		
}
inline void query1(){
    // g[u].push_back(v);
    // g[v].push_back(u);
    unionn(u,v);
}
inline void query2(){
    int v_fa=find(v),cnt=0;bool isBreak=false;
    for(set<int>::iterator it=g[v_fa].begin();it!=g[v_fa].end();it++){
        cnt+=1;
        if(cnt==k){
            cout<<*it<<endl;isBreak=true;break;
        }
    }
    if(!isBreak)
        cout<<-1<<endl;
}
//void out(){
//	for(int i=1;i<=n;i++){
//		for(set<int>::iterator it=g[i].begin();it!=g[i].end();it++)
//			cout<<*it<<" ";
//		cout<<endl;
//	}
//}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) fa[i]=i,g[i].insert(i);  //initialize disjointed set.
    for(int _=1;_<=q;_++){
        cin>>op;
        if(op==1)
            cin>>u>>v,query1();
        else
            cin>>v>>k,query2();
    }
    //cout<<endl<<"set:"<<endl;
    //out();
    //cin>>n;
}
// AC*39 TLE*32 https://atcoder.jp/contests/abc372/submissions/58388612
// AC https://atcoder.jp/contests/abc372/submissions/58389524
// AC https://www.luogu.com.cn/record/179882194