9.11

[Ryanlyt]

位运算

求n的第k位数字(二进制表示): n >> k & 1（从个位开始看，从0开始）

先把第k位移到最后一位 n >> k 再看个位是几 x & 1

返回n的最后(最右边)一位1(二进制表示)：lowbit(n) = n & -n (= n & (~n + 1))

lowbit是树状数组的一个基本操作 如：x = 1010 lowbit(x) = 10

lowbit的最基本的应用：统计x二进制表示中1的个数，每统计一次去掉一个1

#include <iostream>

using namespace std;

int lowbit(int x){
    return x & -x;
} 

int main(){
    int n;
    cin >> n;
    while(n--){
        int x;
        cin >> x;

        int res = 0;
        while(x) x -= lowbit(x), res++; //每次减去x的最后一位

        cout << res << ' '; 
    }
    return 0;
}

[Ryanlyt]

离散化

使用场景：值域很大，但数的个数少，稀疏（如值域0-1e10，n=1e5） 映射

1. a[]中可能重复元素 先去重（先排序再去重）
2. 如何算出x离散化后的值 二分

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

[Ryanlyt]

区间合并

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}