二分

• 浮点二分精度+2
• 二分的前提是具备二段性
• 注意二分的边界,有时候题目在某段边界才满足二段性,所以左指针右指针不要无脑0和inf

// 大于等于
lower_bound(start,end,target);

对于不是大于等于,可以简单的推出以下转化:

• 大于: lb(x+1)
• 小于: lb(x)-1
• 小于等于: lb(x+1)-1

位运算

基本集合操作

交集	并集	差集	全集	属于	添加	删除
a&b	a|b	a&~b	(1<<(n+1))-1	(s >> i) & 1	s | (1 << i)	s & ~(1 << i)

常用小技巧

• 删除最小元素 s&(s-1) (即lowbit)
• 元素个数__builtin_popcount(s)
• 二进制长度__lg(s)+1
• 最大__lg(s)
• 集合中的最小元素__builtin_ctz(s)
• 快速获取每一位1的下标

  while n:
      idx=int(log2(n&-n))
      n&=(n-1) # 或者n-=n&(-n)

• 二进制枚举

  n=20
  s=6
  
  # 遍历集合
  for i in range(n):
      if (s >> i) & 1:
          pass
      
  # 枚举[0,n-1]全部集合
  for s in range(1 << n):
      pass
  
  # 枚举s的非空子集
  sub = s
  while sub:
      # 处理 sub 的逻辑
      sub = (sub - 1) & s
  
  # 从大到小枚举 s 的所有子集(s到空)
  sub = s
  while True:
      # 处理 sub 的逻辑
      sub = (sub - 1) & s
      if sub == s:
          break

离散化

template <typename T>
struct Discrete{
    vector<T> arr;
    Discrete(){}
    Discrete(vector<T> &arr){
        init(arr);
    }
    void init(vector<T> &arr){
        this->arr=arr;
        clear();
    }
    void add(T val){
        arr.push_back(val);
    }
    void clear(){
        sort(arr.begin(),arr.end());
        arr.erase(unique(arr.begin(),arr.end()),arr.end());
    }
    T get(T v){
        return lower_bound(arr.begin(),arr.end(),v)-arr.begin();
    }
};

双指针

构造决策单调性

前缀和与差分

使用O(n)的时间预处理,然后将后续的查询/操作转为O(1)的复杂度

前缀和可以支持O(1)的区间查询

差分支持O(1)的区间修改

• 也常用于操作转换(区间转单点,单点转区间)
• 注意差分思想不局限于维护加减,实际上可以维护具备结合律的关系,比如异或关系

二维

const int N = 150;
int a[N][N];

int get(int x1, int y1, int x2, int y2)
{
    return a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
}

int n = read();
memset(a, 0, sizeof(a));

For(i, 1, n + 1)
{
    For(j, 1, n + 1)
    {
        a[i][j] = read();
        a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    }
}

void update(int x1,int y1,int x2,int y2,int v){
    x2++;
    y2++;
    a[x1][y1]+=v;
    a[x2][y1]-=v;
    a[x1][y2]-=v;
    a[x2][y2]+=v;
    
}