2.位运算双指针排序二分

1.位运算

​ 与：&

​ 或：|

​ 非：！

​ 异或：^ （任何数，与0进行异或都等于0）eg:【a + b = 2（a & b）+ (a ^ b)】

​ 移位：<< (左移)，>>(右移)

​ 取反：~

bitset<n>(x)   //将x转换为n进制
x <<= 1 	   //将x左移一位

2.排序

数组去重排序模板：

vector<int> a;
for(int i = 1;i <= n;i++)
	{
		int num;cin >> num;
		a.push_back(num); 							//push_back,是vector数组的方法，且vector会自动更新长度
	}
sort(a.begin(),a.end()); 							//从小到大排序
a.erase(unique(a.begin(),a.end()),a.end()); 		//unique作用：(将a里的重复元素放到末尾并返回最后有效元素的下一位)
													//erase作用： (将传入两个参数所含的部分清除掉)
for(auto &i : a) cout << i << '\n';    				//以i为索引遍历每一个数组a的元素，并将其输出

reverse(a + 1,a + 1 + n); 							//翻转a数组中的元素

遇见一个元素中有多个数据，且需要排列不同元素时，就需要使用cmp或struct；

struct book{                                        //结构体
	int a,b,c;
	bool operator < (const book &u)const{			//重载运算符
		if(u.a == a && u.b == b) return u.c < c;
		if(u.a == a) return u.b < b;
		else return u.a < a;
	}
}p[N];

bool cmp(const book &u,const book &v){				//cmp函数，用在sort(a.begin(),a.end(),cmp)
	if(u.a == v.a && u.b == v.b) return u.c > v.c;
	if(u.a == v.a) return u.b > v.b;
	else return u.a > v.a;
}

#include<bits/stdc++.h>
using namespace std;
using ll = long long;


int main()
{
   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   ll n;cin >> n;
   vector<int>a;
   for(int i = 1;i <= n;i++)
   {
   	int num;cin >> num;
   	a.push_back(num);
   }
   sort(a.begin(),a.end());
   a.erase(unique(a.begin(),a.end()),a.end());
   for(auto &i : a)cout << i << ' '; 
   return 0;
}

3.双指针

​ 1.只往一个方向走

​ 2.一快一慢

​ 3.在区间内

//https://www.starrycoding.com/problem/36
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
using ll = long long;
ll a[N],c[N];

void solve()
{
	ll n;cin >> n;
	ll res = 0;
	for(int i = 1;i <= n;i++)cin >> a[i];
	for(int i = 1;i <= n;i++)c[a[i]] = 0;
	for(int i = 1,j = 0;i <= n;i++)
	{
		while(j < n && c[a[j+1]] == 0) c[a[++j]]++;
		res = max(res , j - i + 1ll);
		c[a[i]]--;
	}
	cout << res << '\n';
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;cin >> _;
	while(_--) solve();
	return 0;
}

4.二分

while(l + 1 != r)
		{
			mid = (l + r) >> 1;
			if(a[mid] < x) l = mid;
			else r = mid;
		}

//https://www.starrycoding.com/problem/57

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+10;
ll a[N];

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n, q;cin >> n >> q;
	for(int i = 1;i <= n;i++)cin >> a[i];
	while(q--)
	{
		ll l=0,r=n,mid,x;
		cin >> x;
		while(l + 1 != r)
		{
			mid = (l + r) >> 1;
			if(a[mid] < x) l = mid;
			else r = mid;
		}
		if(a[r] == x) cout << r << ' '; 
		else cout << -1 << '\n';
	}
	return 0;
}