Alphabet-Rearrange-Inator 3000（字典树自定义排序）

                                                    Alphabet-Rearrange-Inator 3000

题目描述

Thank goodness you’re here, agents!  We were just about to start the annual agency gift exchange when we learned of Dr. Hunts Mittleshmirtz’s latest plot.  He has created a new device capable of changing the order of letters in the alphabet!  Agent B is already off to go stop him, but in the meantime we’ll need your help here.  You see, for the gift exchange I had written codes on every present and was going to give my first friend the lexicographically first present, the second the second, and so on.   
For example, take presents with the following codes: apple, book, and candle.  Normally, I would give the presents in that order: the present with code “apple” first, followed by the present with code “book” and then the present with code “candle” last.  However, if Dr. Hunts Mittleshmirtz were to change the order of letters “a” and “c”, then it would cause me to give the “candle” present first, then the “book” present, and the “apple” present last!   
Yet it gets more complex.  If Dr. Hunts Mittleshmirtz were then to change the current ordering of letters “a” and “b”, then it would cause me to give the “candle” present first, then the “apple” present, and the “book” present last.  With the orders of letters changing all the time, I’ll need your help to figure out which present is what number.  
Good luck, agents. 

Determine the lexicographically k th  present, while responding to a changing alphabet ordering. 

输入

Input begins with a single, positive integer, t, representing the number of gift exchanges.  Each gift exchange will be described on multiple lines. 
The first line of each gift exchange will contain with two integers, n and q  ( 1≤ n ≤ 105 ; 1 ≤ q ≤ 105 ), representing the number of presents and number of queries, respectively.  This will be followed by n lines each consisting of a single string, s, each representing a single present’s label.  Each label will consist of only lowercase letters.  There will be no more than 105  total letters across all n strings, and the maximum length of each individual string will be 50 letters.  In addition, each label within a single gift exchange will be unique. 
This will be followed by q lines representing a query. Queries come in two forms, denoted by either a1 or a2 as the first number in the line.  Type 1 queries represent the Alphabet-Rearrange-Inator 3000 firing, and will be in the form “1 x y” where x and y are distinct (x and y will not be the same) and represent single lowercase letters that are being swapped in the alphabet. 
Type 2 queries are a request for the kth  present given the current alphabet, and will come in the form “2 k” where 1≤ k ≤ n.  For example, if k is 1, you should return what present should currently be given first (given the ordering at the time of the query); similarly, if k is 4, you should return the fourth present.  Note these are only queries and the gifts are not actually given! 

输出

For each gift exchange, output on its own line “Gift Exchange #i:” where i is the number of the query being answered in the input (starting at 1).  Following this, the result of each type 2 query should be output, each on their own lines.  Output a blank line after each gift exchange. 

样例输入

2 
3 3 
a 
c 
b 
2 1 
2 2 
2 3 
4 3 
ucf 
platypus 
knights 
chargeon 
2 1 
1 a k 
2 1

样例输出

Gift Exchange #1: 
a 
b 
c 
 
Gift Exchange #2: 
chargeon 
knights

//记得用scanf，printf输入输出数字 string用cin就好，能跑500ms，下面全用cin5000ms qaq

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int trie[200000][26];
int tar[200000];
int tot;
int p;
int pos[200000];int w[200000];  //用来交换大小
int num[200000];       //记录一个节点被多少字符串用，排序的关键。
int day;
void insert(string s){
    int i;
    p=0;
    for(i=0;i<(int)s.size();i++){
        if(trie[p][s[i]-'a']==0){
            trie[p][s[i]-'a']=tot;
            tot++;
        }
        p=trie[p][s[i]-'a'];
        num[p]++;  //记录这个点有多少字符串经过
    }
    tar[p]=1;  //目标节点与字符串一一对应
}
void search(int k,int begin){
    p=begin;
    int i;
    for(i=0;i<26;i++){
        if(trie[p][w[i]]==0)continue;  //以我们自定义字典顺序
        int tmp=trie[p][w[i]];
        if(k>num[tmp]){   //换路
            k-=num[tmp];
        }else{
            cout<<(char)(w[i]+'a');
            p=trie[p][w[i]];   
            if(tar[p]==1)k--;  //经过一个目标节点，建一。
            if(k==0){           //k表示在当前节点下的第k个字符串，不包括当前节点为目标节点的
                return ;             //字符串。但也受循环的影响，即左右分支
            }  //k==0表示到了。
            search(k,p);
            return ;  //之前的tmp是尝试，那条路不行的话，就不走，走的话表示路一定是符合条件的，
        }             //所以在search(k,p)返回之后直接return就行，不用再尝试其他的了
    }
}
void solve(){
    int i,j;
    memset(trie,0,sizeof(trie));
    memset(tar,0,sizeof(tar));
    memset(num,0,sizeof(num));
    for(i=0;i<26;i++){
        pos[i]=i;
        w[i]=i;
    }
    tot=1;
    int n;int q;
    cin>>n>>q;
    for(i=1;i<=n;i++){
        string s;
        cin>>s;
        insert(s);
    }
    day++;
    cout<<"Gift Exchange #"<<day<<": "<<endl;
    for(i=1;i<=q;i++){
        int x;
        cin>>x;
        if(x==1){
            char u,v;
            cin>>u>>v;
            swap(w[pos[u-'a']],w[pos[v-'a']]);
            swap(pos[u-'a'],pos[v-'a']);
        }else if(x==2){
            int k;
            cin>>k;
            search(k,0);
            cout<<endl;
        }
    }
    cout<<endl;
    return ;
}
int main (){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

//diao题写了一早上，还好有学长的帮助qwq，大爱tmc学长qwq