可持久化链表（链式前向星）-白红宇

可持久化链表（链式前向星）

阅读量：6112 次

发布时间：2019-06-21

本文共 2080 字，大约阅读时间需要 6 分钟。

1 /************************************************************************* 2     > File Name: 可持久化链式前向星 3     > Author: QWX 4     > Mail:  5     > Created Time: 2018/10/8 19:49:24 6  ************************************************************************/ 7  8  9 //{
     {
     { #include10 #include
      
       11 #include
       
        12 #include
        
         13 #include
         
          14 #include
          
           15 #include
           
            16 #include
            17 #include
             
              18 #include
              
               19 #include
               
                20 #include
                
                 21 #include
                 
                  22 #define mp make_pair23 #define pb push_back24 #define first fi25 #define second se26 #define pw(x) (1ll << (x))27 #define sz(x) ((int)(x).size())28 #define all(x) (x).begin(),(x).end()29 #define rep(i,l,r) for(int i=(l);i<(r);i++)30 #define per(i,r,l) for(int i=(r);i>=(l);i--)31 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)32 #define eps 1e-933 #define PIE acos(-1)34 #define cl(a,b) memset(a,b,sizeof(a))35 #define fastio ios::sync_with_stdio(false);cin.tie(0);36 #define lson l , mid , ls37 #define rson mid + 1 , r , rs38 #define ls (rt<<1)39 #define rs (ls|1)40 #define INF 0x3f3f3f3f41 #define LINF 0x3f3f3f3f3f3f3f3f42 #define ll long long43 #define ull unsigned long long44 #define dd(x) cout << #x << " = " << (x) << "," 45 #define de(x) cout << #x << " = " << (x) << "\n" 46 #define endl "\n"47 using namespace std;48 //}}}49 50 const int N=5e5+7;51 int h[N],rh[N];52 int cnt;53 54 struct Node{55 int v,next;56 }node[N];57 void add(int u,int v,int *h)58 {59 node[cnt].v=v;node[cnt].next=h[u];60 h[u]=cnt++;61 }62 63 int main()64 {65 int n,m;cin>>n>>m;66 int now=1;67 cl(h,-1);cl(rh,-1);68 rep(i,0,n){69 string s;cin>>s;70 int a,b,c;71 if(s=="learn")cin>>a>>b,add(a,b,h);72 else if(s=="rollback")cin>>c,add(c,node[h[c]].v,rh),h[c]=node[h[c]].next;73 else if(s=="relearn")cin>>c,add(c,node[rh[c]].v,h),rh[c]=node[rh[c]].next;74 else if(s=="clone")cin>>c,h[++now]=h[c],rh[now]=rh[c];75 else {cin>>c;if(h[c]==-1)puts("basic");else cout<
                  
                   <