T1奶牛排队
思路：
这道题要用双端队列，dque。
用法：
deque
deque 是 STL 提供的 双端队列 数据结构，能够提供线性复杂度的插入和删除，以及常数复杂度的随机访问。
定义
常见的几种方式：
deque<int> q; 定义一个 int 类型的空双端队列
deque<int> q(10); 初始长度为 10，线性复杂度。
deque<int> q(10, 1); 初始化为 10 个 1，线性复杂度。
使用
q.push_front(数据) 在头部插入一个元素，常数复杂度。
q.push_back(数据) 在尾部插入一个元素，常数复杂度。
q.insert() 在某个位置插入元素，需要结合迭代器使用，线性复杂度。
q.pop_front() 删除头部元素，常数复杂度。
q.pop_back() 删除尾部元素，常数复杂度。
q.erase() 在某个位置删除元素，需要结合迭代器使用，线性复杂度。
q.size() 或 q.length() 获取长度
q[i] 获取下标为 i 的元素
q.front()获取首位元素，也可以使用下标 q[0]
q.back() 获取末尾元素，也可以使用下标 q[q.size()-1]
q.clear() 清空容器
q.begin() 返回一个迭代器，指向容器的第一个元素
q.end() 返回一个迭代器，指向容器的最后一个元素的后一位
题目说明：
A L：一头奶牛从队列左边加入；A R：一头奶牛从队列右边加入；D L K：K 头奶牛从队伍左边离开；D R K：K 头奶牛从队伍右边离开。
样例解释
输入
10
A L
A L
A R
A L
D R 2
A R
A R
D L 1
A L
A R
输出
7
2
5
6
8
A L：1；A L：2,1；A R：2,1,3；A L：4,2,1,3；D R 2：4,2；A R：4,2,5；A R：4,2,5,6；D L 1：2,5,6；A L：7,2,5,6；A R（最终序列）：7,2,5,6,8。
代码
while(n--){
char a,b;
cin>>a>>b;
long long k;
if(a=='D'&&b=='R'){
cin>>k;
while(k--&&q.empty()!=1)q.pop_back();
}
if(a=='D'&&b=='L'){
cin>>k;
while(k--&&q.empty()!=1)q.pop_front();
}
if(a=='A'&&b=='L'){
i++;
q.push_front(i);
}
if(a=='A'&&b=='R'){
i++;
q.push_back(i);
}
}
T2插入删除
思路：
1 X y：在 𝐴 中的元素 𝑥 之后立即插入 𝑦 。 给出此查询时，保证 𝐴 中存在 𝑥。2 X：从 𝐴 中删除元素 𝑥 。给出此查询时，保证 𝐴中存在 𝑥 。可以保证在处理每个查询后， 𝐴 不会为空，并且其元素是不同的。 处理完所有查询后打印 𝐴 。
要用双链表模拟删除和插入，要用unordered_map也就是哈希记住数组下标。
输入
4
2 1 4 3
4
2 1
1 4 5
2 2
1 5 1
输出
4 5 1 3
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+10;
int lt[N],rt[N],e[N],idx=1,h=0,t=N-1;
long long n,x,y,q;
unordered_map<int ,int> mp;
void add(int k,int x){
e[idx]=x;
mp[x]=idx;
lt[idx]=k;
rt[idx]=rt[k];
lt[rt[k]]=idx;
rt[k]=idx++;
}
void remove(int k){
rt[lt[k]]=rt[k];
lt[rt[k]]=lt[k];
}
int main(){
cin>>n;
lt[t]=h;
rt[h]=t;
for(int i=1;i<=n;i++){
cin>>x;
add(lt[t],x);
}
cin>>q;
while(q--){
int a;
cin>>a;
if(a==1){
cin>>x>>y;
add(mp[x],y);
}
if(a==2){
cin>>x;
remove(mp[x]);
mp[x]=0;
}
}
for(int i=rt[h];i!=t;i=rt[i]){
cout<<e[i]<<" ";
}
return 0;
}
T3拍照
思路：
先计算有几头牛，为了不重复，要用桶看有没有重复， 但数组过大，要用map，还要用sort排序，最后用滑动窗口来找最短的满足条件的连续区间。
输入
6
25 7
26 1
15 1
22 3
20 1
30 1
输出
4
解释
取 [22,26] 这个范围，这样可以包含 1,3,7 这三种品种的牛，符合条件。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
struct f{
long long x,id;
};
f a[N];
map<int,int> mp;
long long n,cnt,minn=0x3f3f3f3f;
bool cmp (f a,f b){
return a.x<b.x;
}
int main(){
freopen("photo.in","r",stdin);
freopen("photo.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].id;
if(mp[a[i].id]==0)mp[a[i].id]=1,cnt++;
}
sort(a+1,a+1+n,cmp);
mp.clear();
long long res=0,r=0;
for(int l=1;l<=n;l++){
while(res<cnt&&r<n){
r++;
if(mp[a[r].id]==0)res++;
mp[a[r].id]++;
}
mp[a[l].id]--;
if(res==cnt)minn=min(minn,a[r].x-a[l].x);
if(mp[a[l].id]==0)res--;
}
cout<<minn;
return 0;
}
