位运算

1.整数n的二进制表示中,第k位是几：n>>k&1

2.lowbit(x):返回x的最后一位1
x=1010   lowbit(x)=10
x=101000 lowbit(x)=1000
lowbit函数的实现方式：
一、x&(x^(x-1))
二、x&-x
求出一个数的二进制中有多少个1：
while(x)  x-=lowbit(x),res++;//每次减去x的最后一位1
lowbit的应用：
关于lowbit运算，最著名的应用应该算是树状数组。但是lowbit的神妙远远
不止树状数组，在很多二进制和位运算的相关题目中，都有lowbit运算的影
子。甚至，在状态压缩DP中，lowbit也扮演着一份不可忽视的角色

3.离散化:https://blog.csdn.net/justidle/article/details/104518292
值域：0——10^9;个数：10^5;把这些序列映射到从0开始的连续的自然数
比如：
a[]:1 3  100 2000 500000映射到：
    0 1  2   3    4
（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
}

区间合并：如果在端点处相交，也算有交集。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

void merge(vector<PII>&nums)
{
    vector<PII> res;

    sort(nums.begin(),nums.end());//先把区间按左端点进行排序

    int st=-2e9,ed=-2e9;
    for(auto num:nums)
        if(ed<num.first)//此区间与当前区间没有交集
          {
              if(st!=-2e9) res.push_back({st,ed});
              st=num.first,ed=num.second;

          }
         else  ed=max(ed,num.second);//此时两个区间有交集

    if(st!=-2e9) res.push_back({st,ed});//防止输入为空
    nums=res;

}