day2讲课

清北学堂--刷题班

long long 的输入输出

#ifdef WIN32
#define LL "%I64d"
#else 
#define LL "%lld"
#endif

printf(LL,a);

变量使用

y1
在algorithm库中声明了y1
tm不可

晚上讲课，数据结构

平衡树

线段树不支持插入操作，平衡树支持。

题目：1询问区间和，2插入一个数

线段树不可做

常见的平衡树：treap，sbt,splay,rbt,（替罪羊树，朝鲜树……）

sbt:快，比较好写，功能不太全面，
treap：比sbt慢，比sbt好写
rbt:红黑树，比sbt快，难写（map，set用它实现的）
（上述三种：插入，删除一般的功能可以，nlogn）
splay：特别慢，常数巨大无比，理论nlogn，差不多根n，功能强大

平衡树：一定是二叉树，保证左儿子里面的元素每一个比当前节点小。
中序遍历是排好序的。（先左儿子，根节点，右儿子）
插入：大于根->右，否则相反，
询问：用坐标建树，那么一段区间就是，一个子树和另一个子树的一部分
4
/\
2 5
/\
1 3

1~4:4号节点
2~4:4号到3号
（个人理解）

treap：

treap = tree + heap
tree:左小右大
heap:根大
矛盾

所以：每个节点存两个值：key，value，
value 满足tree，key满足heap，

新开一个节点，key值rand(),保证logn

key值最大的在最上面，并且满足左小右大

操作：
merge(p1,p2)
把以p1p2为根的treap合并成一个treap
p1的所有值小于p2的所有值
split(p,k)
把一个treap拆成两个treap，一个大小为k
把以p为根的前k小的数分解出来，分成两份
插入：p = {1,2,3,4,5}
插入2.33
split(p,2) -> {1,2}{3,4,5}
加入{2.33},merge两次
删除：p = {1,2,3,4,5}
删除2
split -> {1,2}{3,4,5}
split -> {1}{2}{3,4,5}
merge -> {1,3,4,5}

.

实操:
merge(p1,p2) //p1任何一个点小于p2
新根是所有数中key最大的，p1p2中的一个，它们是根，子树中最大的了已经。
1、
p1.key > p2.key
p1 作为根
左儿子不会改变p1.l，
右儿子merge(p1.r,p2);merge返回一个根节点
2、
p1.key < p2.key
p2为根
右儿子不变p2.r
左儿子merge(p1,p2.l)

split(p,k)
三种情况：

k<=p.l.size 前k小的数都在左儿子里
split(p.l,k); 返回p1,p2,使p1包含前k个数，p2包含其他的
所以使p2 = p.l,p1 = 包含前k小的，

k=p.l.size+1 直接返回p和p.l组成的树, and p.r组成的树

k>p.l.size+1
split(p.r, k-p.l.size-1);
返回p和p.l和p1组成的树, and p2组成的树

代码
merge

   int merge(int p1,int p2) {
        if (!p1) return p2; //判断是否为空
        if (!p2) return p1;
        if (z[p1].key<z[p2].key) {
            z[p1].r=merge(z[p1].r,p2);
            return p1;
        }
        else {
            z[p2].l = merge(z[p2].l,p1);
            return p2;
        }
    }

split

pair<int,int> split(int p,int n) {
    if (z[z[p].l].size>=n) {
        if (!z[p].l) return make_pair(0,p);
        else {
            pair<int,int> px=split(z[p].l,n);
            int pl=px.first;
            z[p].l=px.second;
            return make_pair(pl,p);
        }
    }
    else {
        if (z[p].r==0) return make_pair(p,0);
        else {
            pair<int,int> px=split(z[p].r,n-z[z[p].l].size-1);
            z[p].r=px.first;
            int pr=px.second;
            return make_pair(p,pr);
        }
    }
}

练习：线段树的题，忠诚2，

找比小于一个数的数有几个，从而确定split的k
从根开始走，与根比较，小于往左，大于往右，
如果大于当前根rt，往右走，则说明这个数大于所有的rt.l，rt左儿子的所有数，

query_min
代码

int query_min(int p,int v) {
    int ans=0;
    while (p)
        if (z[p].v>=v) p=z[p].l;
        else ans+=z[z[p].l].size+1,p=z[p].r;
    return ans;
}

二分图匹配

树是一个二分图，深度的奇数层和偶数层

二分图匹配，左边和右边最多匹配多少对

算法:匈牙利算法。
贪心的过程，让左边的每个人轮流去请求匹配。
a 1
b 2
c 3
d 4

代码

bool dfs(int now){
    for (int a=1;a<=m;a++)
        if (match[now][a] && !use[a]) {
            use[a]=true;
            if (!result[a] || dfs(result[a])) {
                result[a]=now;
                return true;
            } 
        }
  return false;
}

void xiongyali() {
    int ans=0;
    for (int a=1;a<=n;a++){
        memset(use,false,sizeof(use));
        if (dfs(a)) ans++;
    }
}

二分图的题：ans最大匹配
如果不一定是ans，
ans,n-ans,m-ans,n+m-ans，一定是这里面的一个值，
多造几组数据，试一下
都不是的话，max，n+m-2*ans
原理：最小割最大流的对偶方法