TP1 奶牛排序

思路： 通过一个deque的双端队列来满足题目条件，题目是这么说的：

• A L：一头奶牛从队列左边加入；
• A R：一头奶牛从队列右边加入；
• D L K：K 头奶牛从队伍左边离开；
• D R K：K 头奶牛从队伍右边离开 A L/A R：

if(x=='A')
		{
			if(y=='L') 
				a.push_front(t),t++;
			else if(y=='R') 
				a.push_back(t),t++;
		}

D L K/D R K

if(x=='D')
		{
			if(y=='L')
			{
				int m;
				cin>>m;
				for(int j=1;j<=m;j++) a.pop_front();
			}
			else if(y=='R') 
			{
				int m;
				cin>>m;
				for(int j=1;j<=m;j++) a.pop_back();
			}
		}

代码：

#include<bits/stdc++.h>
using namespace std;
deque<int> a;
int main()
{
	freopen("pd.in","r",stdin);
	freopen("pd.out","w",stdout);
	long long n;
	cin>>n;
	long long t=1;
	for(int i=1;i<=n;i++)
	{
		char x,y;
		cin>>x>>y;
		if(x=='A')
		{
			if(y=='L') 
				a.push_front(t),t++;
			else if(y=='R') 
				a.push_back(t),t++;
		}
		else if(x=='D')
		{
			if(y=='L')
			{
				int m;
				cin>>m;
				for(int j=1;j<=m;j++) a.pop_front();
			}
			else if(y=='R') 
			{
				int m;
				cin>>m;
				for(int j=1;j<=m;j++) a.pop_back();
			}
		}
	}
	int w=a.size();
	for(int i=0;i<w;i++) 
	{
		cout<<a.front()<<"\n";
		a.pop_front();
	}
	return 0;
}

样例：

10 
A L 
A L 
A R 
A L 
D R 2 
A R 
A R 
D L 1 
A L 
A R

以下为输入的命令及对应的队列：

• 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。

TP2 插入删除

思路： 通过一个双链表来满足题目条件，再用一个哈希表来记住下标，题目是这么说的：

• 1 X y：在 A 中的元素 x 之后立即插入 y 。 给出此查询时，保证 A 中存在 x 。
• 2 X：从 A 中删除元素 x 。给出此查询时，保证 A 中存在 x 。可以保证在处理每个查询后， A 不会为空，并且其元素是不同的。 处理完所有查询后打印 A 。 1 x y：

void add(int k,int x)
{
	idx++;
	e[idx]=x;
	mp[x]=idx;
	lt[idx]=k;
	rt[idx]=rt[k];
	lt[rt[k]]=idx;
	rt[k]=idx;
}

2 x

void remove(int k) {
	rt[lt[k]]=rt[k];
	lt[rt[k]]=lt[k];
}

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int n,q,idx,h=0,t=N-1;
int e[N],lt[N],rt[N];
unordered_map<int,int> mp;
void add(int k,int x)
{
	idx++;
	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()
{
	freopen("insdel.in","r",stdin);
	freopen("insdel.out","w",stdout);
	rt[h]=t;
	lt[t]=h;
	cin>>n;
	int x;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		add(lt[t],x);
	}
	cin>>q;
	while(q--)
	{
		short a;
		cin>>a;
		if(a==1)
		{
			int x,y;
			cin>>x>>y;
			add(mp[x],y);
		}
		else 
		{
			int x;
			cin>>x;
			remove(mp[x]);
			mp[x]=0;
		}
	}
	for(int i=rt[h];i!=t;i=rt[i])
	{
		cout<<e[i]<<" ";
	}
	return 0;
}

样例：

4
2 1 4 3
4
2 1
1 4 5
2 2
1 5 1

输出4 5 1 3

TP3 奶牛拍照

思路： 先计算一共有多少个不同的奶牛，为了保证么有重复计算，就用一个桶来判断有没有重复，但是因为数组过大，要用map来算，为了保证下标连续，所以我们按下标来排序，最后用滑动窗口来找最短的满足条件的连续区间。 代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct P
{
	long long x;
	long long id;
}a[N];
map<int,int> mp;
long long cnt=0,minx=1e9+10;
bool cmp(P a,P b)
{
	return a.x<b.x;
}
int main()
{
	freopen("photo.in","r",stdin);
	freopen("photo.out","w",stdout);
	long long n;
	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);
	long long res=0,r=0;
	mp.clear();
	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)
			minx=min(a[r].x-a[l].x,minx);
		if(mp[a[l].id]==0) res--;
	}
	cout<<minx;
	return 0;
}

样例：

6 
25 7 
26 1 
15 1 
22 3 
20 1 
30 1

取 [22,26] 这个范围，这样可以包含 1,3,7 这三种品种的牛，符合条件。