位运算

计算机中的数在内存中都是以二进制形式进行存储的，用位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。

位运算的常见技巧

1. 位运算实现乘除

int a=2;
a>>1; -->1
a<<1; -->4

2. 交换两数

void swap(int &a, int &b) 
{
  a ^= b;
  b ^= a;
  a ^= b;
}

3.判断i位是一还是零

(x>>i)&1

4.lowbit操作,返回最后一位1

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

离散化

  离散化，就是当我们只关心数据的大小关系时，用排名代替原数据进行处理的一种预处理方法。离散化本质上是一种哈希，它在保持原序列大小关系的前提下把其映射成正整数。当原数据很大或含有负数、小数时，难以表示为数组下标，一些算法和数据结构（如BIT）无法运作，这时我们就可以考虑将其离散化。 --摘选自:算法学习笔记(19): 离散化

这里是整数保序的离散化，一般来说是给定的区间范围大，但是个数较少，我们可以将这一些数重新映射到一个新的较小区间中，方便我们进行具体的操作

思考步骤

1. 首先我们应该对于要进行离散化的数据进行排序去重
2. 计算离散化后的值-->使用二分
3. 注意离散化后区间的范围大小

具体实现

题目和讲解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N=3e5+10;

typedef pair<int, int> PII;

int n,m;
//前缀和
int a[N], s[N];
// 记录添加操作，和询问操作
vector<PII> add,ask;
// 记录所有坐标
vector<int> all;

// 为每一个坐标进行离散化
int find(int x)
{
    int l=0,r=all.size()-1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(all[mid]>=x) r=mid;
        else l=mid+1;
    }
    return l+1;
}

int main()
{
    cin>>n>>m;    
    
    // 处理插入操作
    for(int i=0;i<n;i++)
    {
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        all.push_back(x);
        
    }
    // 处理查询操作
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        ask.push_back({l,r});
        all.push_back(l);
        all.push_back(r);
        
    }
    //进行排序去重
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());
    
    // 离散化
    for(auto i:add)
    {
        int x=find(i.first);
        a[x]+=i.second;
    }
    
    // 构建前缀和数组
    for (int i = 1; i <= all.size(); i ++ ) s[i] = s[i - 1] + a[i];
    for(auto i:ask)
    {
        int l=find(i.first),r=find(i.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

区间合并

区间合并就是给定数个区间，将可以合并的区间进行合并，问剩下几个区间

思考过程

1. 首先我们对区间按照左端点进行排序
2. 这样的话，两个区间之间只会存在三种情况
3. 一种是前后两个区间没有任何交集，那么就是一个结果，其次是后一个区间被前一个区间所包围，可以直接跳过，最后一种是有交集但没有覆盖，那么就取后面区间的右端

实现

具体题目和讲解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;

const int N=100010;
vector<PII> seg,res;
int n;

void merge()
{
    int st=-2e9,ed=-2e9; //初始化-2e9的目的是能顺利的将第一个区间加入res中

    sort(seg.begin(),seg.end());
    
    for(auto i:seg)
        if(i.first>ed)
        {
            if(st!=-2e9) res.push_back({st,ed});
            st=i.first,ed=i.second;
        }   
        else ed=max(ed,i.second);
    if(st!=-2e9) res.push_back({st,ed});
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        seg.push_back({l,r});
    }
    merge();
    cout<<res.size();
    return 0;
}