队列和栈
queue<int>q;
int n;
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n=read();
for (int i=1;i<=n;i++)
{
int opt=read();
if(opt==1){
int x=read();
q.push(x);
}
else {
printf("%d
",q.front());
q.pop();
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
int st[B], head=0, tail=0, n;
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n=read();
for (int i=1;i<=n;i++)
{
int opt=read();
if(opt==1)
{
int x=read();
st[++head]=x;
}
else{
printf("%d
", st[head]);
head--;
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
单调队列（松弛操作）
/*暴力O（n^2)*/
for (int a=1;a<=n-k+1;i++)
{
int ans=oo;
for (int b=0;b<k;b++)
{
ans=min(ans,z[a+b]);
}
printf("%d
",ans);
}
法1 单调队列
本质：在前面删一个数，从后面加一个数。队列+最小值
样例
1 3 -1 -3 5 3 6 7， 3
要求最小值，维护单调递增的，
不单调的本质就是最后的数和他不是递增的，所以扔掉就好了，
保持单调递增根最小值有啥关系呢？
单调队列中队首就是我们需要的最小值，维护区间长度就是判断队尾和队首是否存在来维护即可
int z[B], n;
struct monotone_queue//单调递增
{
int head,tail;
int q[233333];
monotone_queue()
{
head=1,tail=0;
}
void push(int p)
{
while (head<=tail && z[q[tail]] >= z[p]) tail--;
q[++tail]=p;
}
int front (){
return q[head];
}
void pop()
{
head++;
}
}q;
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
scanf("%d",&z[i]);
for (int i=1;i<=k;i++)
q.push(i);//放入队列的是坐标
printf("%d
", z[q.front()]);
for (int a=k+1;a<=n;a++)
{
q.push(a);
if (q.front()==a-k) q.pop();
printf("%d
", z[q.front()]);
}
}
法2 ST表
(O(nlogn))
例题
笔记
思路
如果 (l=1) 那么怎么找右 (r);
int n, k;
int z[23333];
int l=1,r=1;
int sum=z[1];
while(sum<k)
{
r++;
sum+==z[r];
}
ans=min(ans, l-r+1)// 左端点为1时，满足条件区间时多少
那么 (l=2) 时呢，同理
那么请问，(r1,r2) 之间有什么关系 (r2>r1),这里指的是坐标
int n, k;
int z[23333];
int l=1,r=1;
int sum=z[1];
for (int l=1,r=1,sum=z[l];r>=n;)
{
while(r<n && sum<k)
{
r++;
sum+=z[r];
}
if(sum>=k) ans=min(ans, r-l+1);
else break;
sum-=z[l];
l++;
}
复杂度是 (O(n)) 每个元素只会被加入一次和出队一次，而且队首和队尾循环时独立的并不冲突，所以总的复杂度为 (O(n)),
共同性：当区间左端点右移的时候，右端点也一定右移，
ＳＴＬ
双端对列 (deque)
include <deque>
void push(int p)
{
while (q.size() && z[q.back()] >= z[p])
q.pop_back();
q.push_back();
}
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
scanf("%d",&z[i]);
for (int i=1;i<=k;i++)
q.push(i);//放入队列的是坐标
printf("%d
", z[q.front()]);
for (int a=k+1;a<=n;a++)
{
q.push(a);
if (q.front()==a-k) q.pop_front();
printf("%d
", z[q.front()]);
}
}
堆
大根堆
- 加入一个数
- 询问最大值
- 删除最大值
小根堆
- 相反即可
STL
大根堆-priority_queue<int> head
小根堆-将数字取个负数（相反数）
手写堆
一 如何构造二叉树
二 如何完成堆
大根堆：任何一个点的值都不小于儿子的值
只能删掉最大值！
srtuct heap{
int n;//元素个数
int z[2333333];//村原属；
heap()
{
n=0;
}
int size()
{
return n;
}
int push()//加入x
{
n++;
z[n]=x;
int p=n;
while (p!=1)
{
int f=p/2;
if (z[f]<z[p])//父亲节点是p/2
{
swap(z[f],z[p]);
p=f;//一直换
}
else break;
}
}
int pop()//删除最大值
{
swap([z[1],z[n]]);
n--;//保证树的形态没改变,但是堆的性质没了，所以就需要头不断的向下换
int p=1;
while (p*2<=n)
{
int pp=p*2;//比较两个儿子的大小
if (pp+1 <= n && z[pp+1] > z[pp]) pp+=1;
if (z[p] < z[pp])
{
swap(z[p], z[pp]);
p=pp;
}
else break;
}
}
int top()
{
return z[1];
}
}
树状数组
有 (N) 个数 (a_1,a_2...，a_n),
- 将 (a_i) 加上 (v);
- 询问 ([l,r]) 区间和
超级快，常数比较小，解决数据小的，且功能小；
(lowbit(x)=2^y) 得到数中最多的 (2^n)
(y_i) 从 (i) 点往下走能走到 (z) 位置的和；
(y_i=z_i+z_{i-1}...+z_{i-lowbit(i)+1})
所以询问 ([l,r]) 和就是前缀和，就是 ([1,r]-[1,l-1])
那么怎么询问 ([1,p]) 和？
[s(p)=egin{matrix}y(p)\overbrace{a_p+a_{p-1}+a_{p-2}+a_{p-lowbit(p)}}end{matrix}
+egin{matrix}y(p-lowbit(p))\overbrace{aa_{p-lowbit(p)+1}...+a_1}end{matrix}
]
#define lb(x) x&(-x)
int n, y[23333];
void modify(int p, int v)
{
for (;p<=n;p+=lb(p)) y[p]+=v;
}
int query(int p)
{
int ans=0;
for (;p-=lb(p);) ans+=y[p];
return ans;
}
int main()
{
scanf("%d",&n);
//发一预处理
for (int a=1;a<=n;a+=2)
lb[a]=1;
for (int a=1;a<=n/2;a++)
lb[a*2]=lb[a]*2;
for (int i=1;i<=n;i++)
{
int v;
scanf("%d",&v);
modify(a,v);
}
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int p, v;
modify(p,v);
query(p);
}
}
单点询问，区间修改
差分的思想就将单点询问转换成区间询问
例题
有多少对逆序对？
思路
对于一个数 (a_i) 他能产生的逆序对就是比前面小的，比后面大的即可，
那么先考虑只有前面的
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define lb(x) x&(-x)
using namespace std;
const int A = 1e5 + 11;
const int B = 1e8 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int m, y[B], z[B],n;
void updata(int x,int v){
for (;x<=n;x+=lb(x)) y[x]+=v;
}
int query(int x)
{
int ans=0;
for (;x;x-=lb(x)) ans+=y[x];
return ans;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
m=read();
for (int i=1;i<=m;i++)
scanf("%d",&z[i]), n=max(n,z[i]);
int ans=0;
for (int i=1;i<=m;i++)
{
updata(z[i],1);
ans+=query(n)-query(z[i]);
}
printf("%d
",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
problem 14
1-N的无序排列，做旋转置换，问怎样的置换能够使得得到的逆序对最小
int m, y[B], z[B],n;
void updata(int x,int v){
for (;x<=n;x+=lb(x)) y[x]+=v;
}
int query(int x)
{
int ans=0;
for (;x;x-=lb(x)) ans+=y[x];
return ans;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n=read();
int ans=0;
for (int i=1;i<=n;i++) updata(i,1);
for (int i=1;i<=n;i++)
{
cin>>z[i];
updata(z[i]+1,-1);
ans+=query(z[i]+1);
}
int sum=ans;
for (int i=1;i<=n;i++)
{
ans+=(-z[i]+n-z[i]-1);
if (ans<sum)
sum=ans;
}
cout << sum;
}