双指针/位运算/离散化/区间和并

模板：

for(int i = 1; i < n; ++ i){
	while(j < i && check(i, j)) j ++ ;
	//内部逻辑具体分析
}

//例如将一个字符串中的单词按行输出
str = "acv adf wers";
int len = strlen(str);
//双指针算法
for(int i = 0; i < len; ++ i){
	int j = i;
	while(j < len && str[j] != ' ') j ++ ;
	
	//内部逻辑具体分析
	//输出单词
	for(int k = i; k < j; ++ k) cout << str[k];
	cout << endl;
	int i = j;
}

常用操作：

• 求n的二进制的第k位：

  • 将n右移k位 (n >> k)
  • 再取右移k位后的个位 (n >> k) & 1

• 返回x的二进制中最后一位1的位置：

  • lowbit(x) = x & -x lowbit(x)的二进制中只有一个1，该1就是x的二进制中的最后一位1
  • -x = ~x + 1 补码为反码加一

• 求n的二进制中1的个数：

  • while(n) n -= lowbit(n), ans++;
  • 当n不为0时，n每次去掉最后一位1，ans即为n的二进制中1的数量

模板：

vector<int> alls;//离散化数组
sort(alls.begin(), alls.end()); //排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); //去重
//根据原值查找离散化后的下标
int find(int x){
	int l = -1, r = alls.size();
	while(l + 1 < r){
		int mid = l + r >> 1;
		if(alls[mid] >= x) r = mid;
		else l = mid;
	}
	return r + 1; //以1作为起点下标
}
//unique函数双指针实现
//在不递减的数列中快速提取出不重复的数
vector<int>::iterator unique(vector<int> &a){
	for(int i = 0, j = 0; i < a.size(); ++ i){
		if(!i || a[i] != a[i - 1]) //要么是第一个数，要么前一个数不同于后一个数
			a[j ++ ] = a[i]; //a[0] ~ a[j - 1] 是所有不同的数
	}
	return a.begin() + j;
}

模板：

typedef pair<int, int> PII; 
vector<PII> segs; //存储不同区间
//合并区间的函数
void merge(vector<PII> &segs){
	vector<PII> res; //存储答案区间
	sort(segs.begin(), segs.end()); //默认按first升序排序
	int st = -inf, ed = -inf; //维护的区间初始化
	for(auto seg : segs){ //遍历所有区间
		if(ed < seg.first){ //如果维护的区间与新区间不相交说明维护的区间已经合并完成
			if(st != -inf) res.push_back({st, ed}); //将合并完成的区间存储
			st = seg.first, ed = seg.second; //更新维护的区间
		}else ed = max(ed, seg.second); //否则取交集
		if(st != -inf) res.push_back({st, ed}); //所有区间合并成为一整个区间的情况
		swap(res, segs); //返回答案到原数组
	}
}