烟台五一培训day1笔记
不完善的地方会补的
没写完啊啊
程序相关
不要用<<endl！！！
要用"\n"！！！
注意不要把\打成/
栈&队列相关
#include<queue>
//#include<bits/stdc++.h>
using namespace std;
queue<int> q;
//queue<队列里面的元素类型> 变量名;
int main()
{
q.push(233);
q.push(2233);//向队列里面加入一个元素
q.pop();//从队列中删除一个元素 删除是队列头的元素 233 void类型没有返回值
int x = q.front();//获取队列头元素 2233
cout << q.size() << endl;//获取队列剩余的元素个数 1
} dfs&bfs实现
dfs用栈可以快速回溯（弹出栈头下一个就是）
但是容易爆栈（因为递归）
bfs用队列实现即可
单调队列
让队列里的元素单调递增或递减
如：1 2 3 4就是一个单调（递增）队列，注意1或2个数一定是单调队列
维护一个单调递增的队列：把不符合条件的删掉；
也就是说，一旦加入一个不是单调递增的数就删掉
举个例子：加入3 1 4 2
33 1删掉31 41 4 2删掉2
此时第四步的[1,4]就是单调队列
例子：计算逆序对
void merge(int l,int r)//要计算l~r这个区间有多少个逆序对
{
if (l==r) return;
int m=(l+r) >> 1;//(l+r)/2
merge(l,m);//递归去算l~m的答案 a[l]~a[m] 排好序了
merge(m+1,r);//递归去算m+1~r的答案 a[m+1]~a[r] 排好序了
//i在左边 j在右边的答案
int p1 = l, p2 = m+1;
for (int i=l;i<=r;i++)
{
if (p1 > m) b[i] = a[p2],p2++;
else if (p2 > r) b[i] = a[p1],p1++;
else if (a[p1] <= a[p2]) b[i] = a[p1],p1++;
else b[i] = a[p2],p2++,ans+=m-p1+1;
}
for (int i=l;i<=r;i++)
a[i] = b[i];
}双端队列
deque（stl）
但是不建议，因为用起来时空都更差，但方便，所以可以手写 特性：支持所有队列操作，两边都能进出
所以stl里的操作有好多种，前后查找和前后加入删除之类的
我们可以用deque来实现单调队列 一个while，持续判断队列是不是保持单调状态，如果不是就删掉队尾 或者说直到前面的数是再加入新数后符合单调条件再加入
维护单调队列：4 2 5 7
维护出来就是[2,5,7]
那问题来了，一段区间的最小值和单调队列有什么关系？
最小值一定是单调队列的最前面！！ 因为最小值插进来之后，后面的数是不可能来到它前面的，它就是在最前面
总结
总结一下，找一个区间的最小值，就是找出其单调队列维护完后的第一个数
维护好双指针，就能保证每个数都加入和删除一次
即为O（n）复杂度，每次操作是O（1）
trie:
struct node
{
int nxt[2];//nxt[0] nxt[1] 代表从当前点走0和1会走到哪里 走到0的话代表这个节点不存在
node()
{
nxt[0] = nxt[1] = 0;
}
}z[23333];
void insert(int x)
{
int p=root;
for (int i=30;i>=0;i--)
{
int y=(x>>i)&1;//取出x二进制的第i位
if (z[p].nxt[y] == 0) {;
cnt++;
z[p].nxt[y] = cnt;
}
p = z[p].nxt[y];
}
}
int query(int x)//从trie中找一个数 使得他和x异或之后最大
{
int p=root,ans=0;
for (int i=30;i>=0;i--)
{
int y=(x>>i)&1;
if (z[p].nxt[y^1] != 0) ans=ans|(1<<i),p=z[p].nxt[y^1];
else p=z[p].nxt[y];
}
return ans;
}
int main()
{
root = 1;
}例题
P1886 滑动窗口
模板题没有好说的
堆
分为大根堆和小根堆
小根堆包括插入一个数、删除最大值、询问最大值
简单实现方法：stl
queue->priority_queue<int> q;
这样我们就生成了一个大根堆
堆也是平衡树的基础，但手写大根堆好像并没什么用
大根堆的性质与栈类似
小根堆（最简单的）实现方法：把所有的元素存进去的时候取其相反数，其他操作也是
取负号。
问题来了，把结构体存到堆里怎么存？
新的函数：重载运算符，会定义两个小于运算怎么去算 和“<”一样？包不是的 ，把 < 改为 > 就可以改算法
但是不能重载大于号
结论：把结构体放在stl比大小，只能用小于号
手写堆不用管（？） 可以用来实现二叉树（本质就是一颗二叉树） 二叉树指有右儿子就一定有左儿子，即完全二叉树
写法啊。
#include<queue>
//#include<bits/stdc++.h>
using namespace std;
priority_queue<int> q;
//大根堆
//小根堆最简单的方法：取负号
struct rec
{
int a,b;
};
//如果要把结构体 放入 stl比大小 只能重载小于号
bool operator<(const rec &x,const rec &y)
{
return x.a + x.b > y.a + y.b;
}
priority_queue<rec> qq;//取出a+b最小的结构体
int main()
{
q.push(233);
q.push(2233);//向堆里面加入一个元素
q.pop();//从堆中删除一个元素 删除是堆中最大的元素 2233 void类型没有返回值
int x = q.top();//获取堆中最大元素 233
cout << q.size() << endl;//获取堆剩余的元素个数 1
} heapa
struct heap
{
int a[1010];//堆的每一个元素
int n=0;//堆有几个元素
int top()//询问最大值
{
return a[1];
}
void push(int x)//插入一个数
{//O(logn)
n++;a[n] = x;
int p=n;
while (p!=1)
{
if (a[p] > a[p>>1])
{
swap(a[p],a[p>>1]);
p = p>>1;
}
else
{
break;
}
}
}
void pop()//删除最大值
{
swap(a[1],a[n]);n--;
int p=1;
while ((p<<1) <= n)
{
int l=p<<1;
int r=l|1;//p*2+1
int pp=l;
if (r<=n && a[r] > a[l]) pp=r;//pp一定是两个儿子中较大的那个
if (a[pp] > a[p])
{
swap(a[pp],a[p]);
p=pp;
}
else
{
break;
}
}
}
int size()//询问还有几个数
{
return n;
}
};并查集
int to[maxn];//to[i] 代表i的箭头指向谁
int go(int p)//从p点出发 看最后会走到哪里
{
if (p == to[p]) return p;
else
{
to[p] = go(to[p]);
return to[p];
}
}
int main()
{
cin >> n;
for (int i=1;i<=n;i++)
to[i] = i;
//合并
to[go(p1)] = go(p2);
//查询
go(p1) == go(p2);
}分块
int belong[maxn];//belong[i] 代表第i个数属于第几块
int sum[maxn];//sum[i] 代表第i块的和是多少
int daxiao[maxn];//daxiao[i] 代表第i块的大小是多少
int col[maxn];//col[i] 代表第i块被整体加了col[i]
int main()
{
cin >> n >> m;
for (int i=1;i<=n;i++)
cin >> a[i];
int s = sqrt(n);//每块的大小
for (int i=1;i<=n;i++)
belong[i] = i/s+1;
for (int i=1;i<=n;i++)
{
sum[belong[i]] += a[i];
daxiao[belong[i]] ++;
}
for (int x=1;x<=m;x++)
{
int opt;
cin >> opt;
if (opt == 1)//询问操作
{
int l,r;
cin >> l >> r;
int ans=0;
if (belong[l] == belong[r])
for (int i=l;i<=r;i++)
ans += a[i] + col[belong[i]];
else
{
for (int i=l;belong[i] == belong[l]; i++)
ans += a[i] + col[belong[i]];
for (int i=r;belong[i] == belong[r]; i--)
ans += a[i] + col[belong[i]];
for (int i=belong[l] + 1; i < belong[r]; i++)
ans += sum[i];
}
cout << ans << "\n";
}
else
{
int l,r,v;
cin >> l >> r >> v;
if (belong[l] == belong[r])
for (int i=l;i<=r;i++)
a[i] += v;
else
{
for (int i=l;belong[i] == belong[l]; i++)
a[i] += v,sum[belong[i]] += v;
for (int i=r;belong[i] == belong[r]; i--)
a[i] += v,sum[belong[i]] += v;
for (int i=belong[l] + 1; i < belong[r]; i++)
{
sum[i] += v * daxiao[i];
col[i] += v;
}
}
}
}
return 0;
}附录（题目）
A 已过
B 已过
C 未过
d 已过
e 已过
f 未过
g 未过
h 未过
i 已过
j 未过