\(Day\) \(3\)
位运算
位运算包含了五个运算符，分别是：
-
&与
只有两个对应位都为 \(1\) 时才为 \(1\) -
|或
只要两个对应位中有一个 \(1\) 时就为 \(1\) -
^异或
只有两个对应位不同时才为 \(1\) -
<<左移
如 \(n<<i\) 表示将 \(n\) 的二进制向左移动 \(i\) 位，等价于\(n*2^i\) -
>>右移
如 \(n>>i\) 表示将 \(n\) 的二进制向右移动 \(i\) 位，等价于\(n/2^i\)
这里有一个有趣的等式
\((a\)&\(b)+(a\)^\(b)=(a|b)\)
请问，^有什么用？
来看一道题
给你 \(2N+1\) 个数 ，有 \(N\) 个数出现了两次，请找出那个只出现一次的数（不能用数组）
想一想异或的含义，只要把这几个数全部异或起来就行了
用位运算判断 \(x\) 的奇偶
我们知道，若要判断 \(x\) 的奇偶，我们只要判断 \(x\)%\(1\) 是否等于\(1\)
这里，我们还可以判断 \(x\)&\(1\) 是否等于 \(1\)
当然，这里要注意，位运算的这几个运算符优先级都很低，在进行运算的时候要加上括号
而且，优先级越低，运算速度越快
数据结构
队列\(queue\)
队列是一个先进先出的数据结构，很像我们生活中的排队
它支持以下几个操作：
- 在队尾加入一个元素
- 在队首删除一个元素
- 查看队首元素
点击查看代码
#include<iostream>
#include<queue>
using namespace std;queue<int> q;//声明了一个元素类型为int的队列 int main(){q.push(233);q.push(2333);//向队列中放入一个元素cout << q.front() << endl;//询问队首元素是多少: 233q.pop();//从队列中删除队首元素cout << q.size() << endl;//询问队列中还有多少个元素 return 0;
}
可是STL中的\(queue\)无法查看队尾元素，我们可以手写\(queue\)
点击查看代码
struct queue{int a[maxn];//存队列里面的元素 int head,tail;//代表当前队列的存储区间为 a[head~tail]queue(){head=1;tail=0;} void push(int x){tail++;a[tail]=x;}void pop(){head++;}int size(){return tail-head+1;}int front(){return a[head];}
};
栈\(stack\)
栈是一种后进先出的数据结构
它支持以下操作：
- 向栈顶加入一个元素
- 删除栈顶元素
- 询问栈顶元素
点击查看代码
#include<iostream>
#include<stack>
using namespace std;stack<int> s;//声明一个元素类型为int的栈int main(){s.push(233);s.push(2333); cout << s.top() << endl;//询问栈顶元素是多少:2333s.pop();cout << s.size() << endl;
}
给你\(N\)个数和一个\(L\)，求所有长度为\(L\)的区间最小值\((L \le N \le 3*10^6)\)
很容易想到队列
可是要找出最小值，这就需要一个单调递增的队列
单调队列\(monotone\) \(queue\)
如果加入的元素不符合单调递增，那就将其删除，直到满足条件
点击查看代码
#include<iostream>using namespace std;struct monotone_queue{int a[maxn];//存队列里面的元素 当前的队列要单调不降 int head,tail;//代表当前队列的存储区间为 a[head~tail]queue(){head=1;tail=0;} void push(int x){while (head<=tail && a[tail] > x)tail--;tail++;a[tail]=x;}void pop(){head++;}int size(){return tail-head+1;}int front(){return a[head];}
}q;int main(){cin >> n >> l;for (int i=1;i<=n;i++)cin >> z[i];for (int i=1;i<=l;i++)q.push(z[i]);//把第一个区间的数全部扔进单调队列int ans=q.front();//第一个区间的最小值必然是队首元素for (int i=l+1;i<=n;i++){//当前要加入第i个数q.push(z[i]);//把第i个数加入队列if (z[i-l] == q.front()) q.pop();//从队列中删除z[i-l]这个数 ans += q.front();//区间i-l+1~i的最小值 } cout << ans << endl;return 0;
}
双端队列\(deque\)
可以理解为是栈和队列的结合体
点击查看代码
#include<deque>
#include<iostream>
using namespace std;deque<int> d;//声明了一个元素类型为int的双端队列 int main(){d.size();//询问还有几个元素 d.push_front(1);//从前面加入1d.front();//询问最前面的元素是谁d.back();//询问最后面的元素是谁 d.pop_front();//从前面弹出一个元素 d.push_back(2);//从后面加入2 d.pop_back();//从后面弹出元素 return 0;
}
堆/优先队列 \(riority\) $queue￥
堆支持以下操作：
- 加入一个数
- 刚除最大值
- 询问最大值
这是大根堆
若将上面的最大值改为最小值，就是小根堆
点击查看代码
#include<iostream>
#include<queue>using namespace std;priority_queue<int> heap;//声明一个元素类型为int的大根堆
priority_queue<int> heap2;//小根堆 int main(){heap.push(233);heap.push(2333);//堆中加入一个元素heap.top();//询问堆中最大的元素:2333heap.pop();//删除堆中最大的元素heap.size();//询问堆中还有几个元素 heap2.push(-233);//加入元素的时候取一个相反数 heap2.push(-2333);//取元素的时候就能够取出来最小的数的相反数
}
看一道题：
对每种颜色的木棍放入一个大根堆，每次取每个不同颜色大根堆中最大的三根，若组不成三角形，就把最长的木棍扔掉
\(ST\)表
给你\(N\)个数，\(M\)次询问，求\(L\)到\(R\)这个区间的最小值
\(ST\)表就是用 \(f_{i,j}\) 来存储从第\(i\)个数开始的\(2^j\)个数的最小值
简单来说，\(f_{i,j}=\min(f_{i,j-1},f_{i+2^{j-1},j-1})\)
点击查看代码
#include<iostream>using namespace std;const int maxn=100010;int n,a[maxn],f[maxn][20],b[maxn];int main()
{cin >> n;for (int i=1;i<=n;i++)cin >> a[i];for (int i=0;(1<<i)<=n;i++)for (int j=(1<<i);j<(1<<(i+1));j++)b[j] = i;//两个长度为2^i的区间 一定能够覆盖住一个长度为j的区间 for (int i=1;i<=n;i++)f[i][0] = a[i];for (int j=1;(1<<j)<=n;j++)//要计算长度为2^j的区间的最小值 for (int i=1;i+(1<<j)-1<=n;i++)//这段区间的开始位置为if[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]); //O(nlogn)cin >> m;for (int i=1;i<=m;i++)//O(m){int l,r;cin >> l >> r;int len=r-l+1;//区间长度int x=b[len];cout << min(f[l][x],f[r-(1<<x)+1][x]) << endl;//从l开始向后的2^x个数的最小值//从r开始向前的2^x个数的最小值 }
}
\(set\)
点击查看代码
#include<set>
#include<iostream>using namespace std;set<int> se;//定义了一个元素类型为int的集合
//每个数只能在set中出现一次 struct jgt
{int a,b;
};bool operator<(const jgt &a,const jgt &b)
{return a.a<b.a;
}set<jgt> se2;int main()
{se.insert(233);se.insert(233);se.insert(2333);//向set进行插入cout << se.size() << endl;//查询set的大小cout << se.count(233) << endl;//查询233在set中出现了多少次 要么0 要么1se.erase(233); //从set中删除2333 cout << se.count(233) << endl;se.insert(333);se.insert(254);//输出set中的所有元素（3种） //for (set<int>::iterator it=se.begin(); it != se.end(); it++)// cout << (*it) << endl;//for (auto it = se.begin(); it != se.end(); it++)// cout << (*it) << endl;for (auto it : se)cout << it << endl;se.clear();}
\(pair\)
点击查看代码
#include<iostream>
#include<algorithm>using namespace std;pair<int,int> p;//声明一个二元组 第一个元素类型为int 第二个元素类型为int pair<int,int> a[100010];pair<int, pair<int,int> > r;//三元组 int main()
{p.first = 22;//first第一个元素 p.second = 33;//second第二个元素p = make_pair(22,33);cout << (a[1] < a[2]) << endl;//先比较first 再比较second cout << (a[1]==a[2]) << endl;//first和second都要相等 r.first;r.second.first;r.second.second;int n=10;sort(a+1,a+n+1);//按照first作为第一关键字 second作为第二关键字从小到大排序
}
\(map\)
点击查看代码
#include<iostream>
#include<map>
#include<string>using namespace std;map<int,int> ma1;//数组
//第一个int 代表这个数组的下标类型
//第二个int 代表这个数组的元素类型
map<int, map<int,int> > ma2;
map<pair<int,int>, int> ma3;map<string,string> ma4;
//log
int main()
{cout << ma1.size() << endl;ma1.clear();ma1[233] = 2333;ma1[2147483647] = 23333;ma1[-2345] = 3444;for (auto it : ma1)cout << it.first << " " << it.second << endl;ma2[1][2] = 3;for (auto it1 : ma2)for (auto it2 : ma2[it1.first])cout << it1.first << " " << it2.first << " " << it2.second << endl;ma3[{1,3}] = 3;ma4["hello"] = "world";
}
\(vector\)
点击查看代码
#include<iostream>
#include<vector>using namespace std;vector<int> z;//动态数组 元素类型为int //z 已经有32768个数
//push_back
//把占用的内存从32768 -> 65536
//第32769这个位置拿来存数 int main()
{z.push_back(233);z.push_back(2333);//在数组后面加入一个数z.pop_back();//删除数组最后一个数z.push_back(23333);cout << z.size() << endl;//数组中有几个数for (int i=0;i<z.size();i++)cout << z[i] << endl; z.resize(1000);//把vector数组大小变为1000 return 0;
}
并查集
点击查看代码
int to[233];//to[i]代表i点的箭头指向谁 int go(int p)//从p出发最后会走到哪里 O(1)
{if (p==to[p]) return p;//else return to[p]=go(to[p]);else{to[p] = go(to[p]);return to[p];}
}int main()
{cin >> n;for (int i=1;i<=n;i++)to[i] = i;//每个点的箭头都指向自己 //合并x和y所在的部分 to[go(x)] = go(y);//判断x和y是否属于同一部分go(x) == go(y);
}
线段树
点击查看代码
#include<iostream>using namespace std;const int maxn=100010;int n,m,a[maxn];struct node//线段树的一个节点
{//第一个需要修改的地方：增加维护的值 int l,r;//这段区间的左端点、右端点int sum;//这段区间的和int minv;//这段区间的最小值 int tag;//懒标记//代表当前节点所对应的区间 每一个数都被加了tag//但是 这件事还没有告诉当前节点的两个儿子 node(){//第二个需要修改的地方：增加维护的值的初始化 l=r=sum=tag=minv=0;}
}z[maxn*4];//z[i]代表线段树的第i个节点#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1node operator+(const node &l,const node &r)//定义线段树如何合并两个区间
{//第三个需要修改的地方：增加维护的值 计算方法 node res;res.l=l.l; res.r=r.r;res.sum = l.sum + r.sum;res.minv = min(l.minv,r.minv);return res;
}void build(int l,int r,int rt)//当前的线段树节点编号为rt 其所对应的区间为l~r
//建立这棵线段树
{if (l==r)//走到了最下面 区间只有一个数 那就建立这个节点 {//第四个需要修改的地方：长度为1的区间这个值怎么处理 z[rt].l=z[rt].r=l;z[rt].sum = a[l];z[rt].minv=a[l];return;}int m=(l+r)>>1;//从l~r中间砍开 l~m作为左儿子区间 m+1~r作为右儿子区间build(lson);//build(l,m,rt<<1);//build(l,m,rt*2);//建立左儿子 build(rson);//build(m+1,r,rt<<1|1);//build(m+1,r,rt*2+1);//建立右儿子 z[rt] = z[rt<<1] + z[rt<<1|1];
} void color(int rt,int v)//给节点rt打一个+v的懒标记
{//第五个需要修改的地方：增加维护的值的打标记方法 z[rt].sum += v * (z[rt].r-z[rt].l+1);z[rt].tag += v;z[rt].minv += v;
} void push_col(int rt)//把节点rt的标记告诉它的儿子
{if (z[rt].tag != 0){color(rt<<1,z[rt].tag);color(rt<<1|1,z[rt].tag);z[rt].tag=0;}
} node query(int l,int r,int rt,int nowl,int nowr)//logn
//当前线段树节点为l~r，编号为rt 此时要询问nowl~nowr这段区间
{if (nowl<=l && r<=nowr) return z[rt];//l~r当前线段树节点所对应的区间被询问区间完全包含push_col(rt);//把懒标记下放 int m=(l+r)>>1; if (nowl<=m)//询问区间和左儿子有交 {if (m<nowr)//询问区间和右儿子有交return query(lson,nowl,nowr) + query(rson,nowl,nowr);else//代表只和左儿子有交return query(lson,nowl,nowr); }else//只和右儿子有交return query(rson,nowl,nowr);
} void modify(int l,int r,int rt,int nowl,int nowr,int v)
//当前线段树节点编号为rt 区间为l~r
//修改操作为给nowl~nowr这段区间整体+v
{if (nowl<=l && r<=nowr) {//当前区间被修改区间整体包含 color(rt,v);//给节点rt打一个整体+v的懒标记return; }push_col(rt);//把懒标记下放 int m=(l+r)>>1;if (nowl<=m) modify(lson,nowl,nowr,v);//修改区间和左儿子有交 if (m<nowr) modify(rson,nowl,nowr,v);//修改区间和右儿子有交z[rt] = z[rt<<1] + z[rt<<1|1];
} int main()
{cin >> n >> m;for (int i=1;i<=n;i++)cin >> a[i];build(root);//建树 for (int i=1;i<=m;i++){int opt;cin >> opt;if (opt==1)//修改操作{int x,y,k;cin >> x >> y >> k;modify(root,x,y,k);}else//询问操作 {int x,y;cin >> x >> y;cout << query(root,x,y).sum << endl;} }return 0;
}
