Problem G. Persistent Queue
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88258#problem/G
Description
Persistent data structures are designed to allow access and modi cation of any version of data structure. In this problem you are asked to implement persistent queue. Queue is the data structure that maintains a list of integer numbers and supports two operations: push and pop. Operation push(x) adds x to the end of the list. Operation pop returns the rst element of the list and removes it. In persistent version of queue each operation takes one additional argument v. Initially the queue is said to have version 0. Consider the i-th operation on queue. If it is push(v, x), the number x is added to the end of the v-th version of queue and the resulting queue is assigned version i (the v-th version is not modi ed). If it is pop(v), the front number is removed from the v-th version of queue and the resulting queue is assigned version i (similarly, version v remains unchanged). Given a sequence of operations on persistent queue, print the result of all pop operations.
Input
The rst line of the input le contains n the number of operations (1 ≤ n ≤ 200 000). The following n lines describe operations. The i-th of these lines describes the i-th operation. Operation push(v, x) is described as 1 v x, operation pop(v) is described as -1 v. It is guaranteed that pop is never applied to an empty queue. Elements pushed to the queue t standard signed 32-bit integer type.
Output
For each pop operation print the element that was extracted.
Sample Input
10
1 0 1
1 1 2
1 2 3
1 2 4
-1 3
-1 5
-1 6
-1 4
-1 8
-1 9
Sample Output
1
2
3
1
2
4
HINT
题意
让你维护可持久化队列
1 v x 给状态v下的队列的尾部插入x
-1 v pop状态v的队列首部
题解：
dfs离线搞一搞就好了
按照状态建成一个图
然后blabla就吼了……
一开始拿rope写的在线版本，无限TLE= =
代码：
//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 200051 #define mod 10007 #define eps 1e-9 int Num; //const int inf=0x7fffffff; //нчоч╢С const int inf=0x3f3f3f3f; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** vector<pair<int,int> > ans; vector<int> E[maxn]; vector<int> Q; struct node { int x,y,z; }; node op[maxn]; void dfs(int x,int l) { if(x==0) { for(int i=0;i<E[x].size();i++) dfs(E[x][i],l); } else if(op[x].x==1) { Q.push_back(op[x].z); for(int i=0;i<E[x].size();i++) dfs(E[x][i],l); Q.erase(Q.end()-1); } else { ans.push_back(make_pair(x,Q[l])); for(int i=0;i<E[x].size();i++) dfs(E[x][i],l+1); } } int main() { freopen("queue.in","r",stdin); freopen("queue.out","w",stdout); int n=read(); for(int i=1;i<=n;i++) { scanf("%d",&op[i].x); if(op[i].x==1) { scanf("%d%d",&op[i].y,&op[i].z); E[op[i].y].push_back(i); } else { scanf("%d",&op[i].y); E[op[i].y].push_back(i); } } dfs(0,0); sort(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) printf("%d ",ans[i].second); }