Input有多组数据。
对于每一组数据，第一行读入两个数 NN 和 QQ。
接下来有 QQ 行，每行 33~44 个数，意义如上。
N≤150000,Q≤400000N≤150000,Q≤400000
1≤u,v≤N,0≤w≤1,1≤val≤1000001≤u,v≤N,0≤w≤1,1≤val≤100000
所有数据里 QQ 的和不超过500000500000
Output对于每组数据的每一个操作②，输出一行表示答案。
注意，如果操作②的队列是空的，就输出−1−1且不执行删除操作。Sample Input
2 10
1 1 1 23
1 1 0 233
2 1 1
1 2 1 2333
1 2 1 23333
3 1 2 1
2 2 0
2 1 1
2 1 0
2 1 1
Sample Output
23
-1
2333
233
23333
提示
由于读入过大，C/C++ 选手建议使用读入优化。
一个简单的例子：
void read(int &x){
char ch = getchar();x = 0;
for (; ch < ‘0‘ || ch > ‘9‘; ch = getchar());
for (; ch >=‘0‘ && ch <= ‘9‘; ch = getchar()) x = x * 10 + ch - ‘0‘;
}
题意：题目中说的很清楚了
双端队列代码：不知道为什么，内存超限，我也没改出来
1 #include<deque> 2 #include<iostream> 3 using namespace std; 4 5 deque<int> d[150010]; 6 int main() 7 { 8 std::ios::sync_with_stdio(false); 9 int n,m; 10 while(cin>>n>>m) 11 { 12 // d.clear(); 13 for(int i=0; i<=n; i++) 14 d[i].clear(); 15 int x,u,v,w,val; 16 for(int i=0; i<m; i++) 17 { 18 cin>>x; 19 if(x==1) 20 { 21 cin>>u>>w>>val; 22 if(w==0)//加在最前面 23 { 24 d[u].push_front(val); 25 } 26 else if(w==1)//在最后面 27 { 28 d[u].push_back(val); 29 } 30 } 31 else if(x==2) 32 { 33 cin>>u>>w; 34 if(d[u].empty()) 35 { 36 cout<<-1<<endl; 37 continue; 38 } 39 40 if(w==0)//询问并操作del最前面的元素，询问要求输出 41 { 42 cout<<d[u].front()<<endl; 43 d[u].pop_front(); 44 } 45 else if(w==1)//最后面 46 { 47 cout<<d[u].back()<<endl; 48 d[u].pop_back(); 49 } 50 } 51 else if(x==3)//该操作完成后，队列v被清空 52 { 53 cin>>u>>v>>w; 54 if(w==0)//队列v的开头和队列u的结尾连在一起 55 //队列v的结尾作为新队列的结尾 56 { 57 while(!d[v].empty())//这边注意一下 58 { 59 d[u].push_back(d[v].front()); 60 d[v].pop_front(); 61 } 62 } 63 else if(w==1) 64 { 65 while(!d[v].empty()) 66 { 67 d[u].push_back(d[v].back()); 68 d[v].pop_back(); 69 } 70 }//先将队列v翻转，再顺序接在队列u后面） 71 } 72 } 73 } 74 return 0; 75 }
后来查了一下，发现list占用内存比deque少，所以后来用了list过的。
1 #include<deque> 2 #include<list> 3 #include<iostream> 4 using namespace std; 5 6 list<int>d[150010]; 7 int main() 8 { 9 std::ios::sync_with_stdio(false); 10 int n,m; 11 while(cin>>n>>m) 12 { 13 // d.clear(); 14 for(int i=0; i<=n; i++) 15 d[i].clear(); 16 int x,u,v,w,val; 17 for(int i=0; i<m; i++) 18 { 19 cin>>x; 20 if(x==1) 21 { 22 cin>>u>>w>>val; 23 if(w==0)//加在最前面 24 { 25 d[u].push_front(val); 26 } 27 else if(w==1)//在最后面 28 { 29 d[u].push_back(val); 30 } 31 } 32 else if(x==2) 33 { 34 cin>>u>>w; 35 if(d[u].empty()) 36 { 37 cout<<-1<<endl; 38 continue; 39 } 40 41 if(w==0)//询问并操作del最前面的元素，询问要求输出 42 { 43 cout<<d[u].front()<<endl; 44 d[u].pop_front(); 45 } 46 else if(w==1)//最后面 47 { 48 cout<<d[u].back()<<endl; 49 d[u].pop_back(); 50 } 51 } 52 else if(x==3)//该操作完成后，队列v被清空 53 { 54 cin>>u>>v>>w; 55 if(w==0)//队列v的开头和队列u的结尾连在一起 56 //队列v的结尾作为新队列的结尾 57 { 58 // while(!d[v].empty())//这边注意一下 59 // { 60 // d[u].push_back(d[v].front()); 61 // d[v].pop_front(); 62 // } 63 d[u].insert(d[u].end(),d[v].begin(),d[v].end()); 64 d[v].clear(); 65 } 66 else if(w==1) 67 { 68 // while(!d[v].empty()) 69 // { 70 // d[u].push_back(d[v].back()); 71 // d[v].pop_back(); 72 // } 73 d[u].insert(d[u].end(),d[v].rbegin(),d[v].rend()); 74 d[v].clear(); 75 }//先将队列v翻转，再顺序接在队列u后面） 76 } 77 } 78 } 79 return 0; 80 }
而且内存比题目规定的少好多。。所以应该用deque是可以写的，但是我一直超内存。
题目规定：
HDU-6375-度度熊学队列-双端队列deque/list
原文：https://www.cnblogs.com/OFSHK/p/11312122.html