后缀数组

POJ 3261 Milk Patterns

Posted on

后缀数组之可重叠 k 次最长重复子串。
数据好水……他的 “ 字符 ” 范围为 \( [ 0 , 1e6 ] \)
按我最开始的想法,求后缀数组的时候,在字符最大值超过 char 我就打算用 sort 代替基数排序了。
然而……直接取最大值用基数排序居然过了,还是 63 ms ……

下面是可重叠 k 次最长重复子串的求法:
解法与不可重叠最长重复子串的做法基本一致。
二分答案,将排序后的后缀按照二分值分成若干组,如果某一组的数量大于等于 k ,那么这个二分值是可行值。

题意:
可重叠 k 次最长重复子串。

思路:
见上。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 2e4 + 10;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int s[maxn];

    void DA(int n, int m)
    {
        int p, *x = t1, *y = t2;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i] = s[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[i]]] = i;
        for (int k = 1; k <= n; k <<= 1) {
            p = 0;
            range(i, n - k, n - 1) y[p++] = i;
            each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
            each(i, m) buc[i] = 0;
            each(i, n) buc[x[i]]++;
            range(i, 1, m - 1) buc[i] += buc[i - 1];
            reach(i, n) sa[--buc[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1, x[sa[0]] = 0;
            range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)
                break;
            m = p;
        }
    }

    void getHeight(int n)
    {
        int j, k = 0;
        each(i, n + 1) rank[sa[i]] = i;
        each(i, n)
        {
            k ? k-- : 0;
            j = sa[rank[i] - 1];
            while (s[i + k] == s[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

public:
    int sa[maxn];
    int rank[maxn], height[maxn];

    void input(int n)
    {
        len = n;
        int maxx = 0;
        each(i, n)
        {
            scanf("%d", s + i);
            maxx = max(maxx, s[i]);
        }
        s[len] = 0;
        DA(len + 1, maxx + 1);
        getHeight(len);
    }

    bool check(int key, int k)
    {
        int cnt = 1;
        range(i, 2, len) if (height[i] >= key)
        {
            if (++cnt >= k)
                return true;
        }
        else cnt = 1;
        return cnt >= k;
    }

} suffix_array;

int main()
{
    int n, k;
    while (scanf("%d %d", &n, &k) != EOF) {
        suffix_array.input(n);
        int l = 0, r = n, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (suffix_array.check(mid, k))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d\n", l - 1);
    }
    return 0;
}
后缀数组

HDU 4691 Front compression

Posted on

后缀数组之最长公共前缀的不定查询。
因为查询很多,所以要结合RMQ算法。这个也是很简单的,一般不会有什么变化,只要套一下木板就好了。

但是这个有一个非常困扰我的地方,就是题目给定的查询不是后缀之间的最长公共前缀查询,而是子串之间的查询,这可难倒我了,我也不知道该如何解决。

看了题解后,发现其实解决方法很简单,只要将求得的 LCP 与两个子串长度互相比较,三个长度取最小就是我们要得答案。

题意:
给你一个字符串,再给你很多子串,要你将所有给定的子串进行压缩。
压缩方式为将两个字符串的最长公共前缀在第二个字符串用数字表示。

输出未压缩的长度和压缩后的长度,要记空格和换行。

思路:
不断求 LCP 即可。
在求的过程中有几个注意的地方。

  • 注意后缀相同的情况。
  • 得到两个后缀的 rank 后不能直接使用 RMQ ,一方面有不确定的大小关系,另一方面,我们是对height 数组求 RMQ ,做区间应为 较小的 rank + 1 。
  • 注意将RMQ数组开大……

这道题使用的代码已经能成为我求 LCP 的模板了 除了改成DC3

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int mmin[maxn][17], s[maxn];

    void DA(int n, int m) 
    {
        int p, *x = t1, *y = t2;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i] = s[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[i]]] = i;
        for (int k = 1; k <= n; k <<= 1) {
            p = 0;
            range(i, n - k, n - 1) y[p++] = i;
            each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
            each(i, m) buc[i] = 0;
            each(i, n) buc[x[i]]++;
            range(i, 1, m - 1) buc[i] += buc[i - 1];
            reach(i, n) sa[--buc[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1, x[sa[0]] = 0;
            range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
            if (p >= n)
                break;
            m = p;
        }
    }

    void getHeight(int n) 
    {
        int j, k = 0;
        each(i, n + 1) rank[sa[i]] = i;
        each(i, n)
        {
            k ? k-- : 0;
            j = sa[rank[i] - 1];
            while (s[i + k] == s[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

public:
    int sa[maxn];
    int rank[maxn], height[maxn];

    void input(char* str)
    {
        len = strlen(str);
        range(i, 0, len) s[i] = str[i];
        DA(len + 1, 128);
        getHeight(len);
    }

    void initRMQ()
    {
        for (int i = 1; i <= len; i++)
            mmin[i][0] = height[i];
        for (int j = 1; (1 << j) <= len; j++)
            for (int i = 1; i + (1 << j) - 1 <= len; i++)
                mmin[i][j] = min(mmin[i][j - 1], mmin[i + (1 << (j - 1))][j - 1]);
    }

    int RMQ(int l, int r)
    {
        int k = 0;
        while ((1 << (k + 1)) <= r - l + 1)
            k++;
        return min(mmin[l][k], mmin[r - (1 << k) + 1][k]);
    }

    int lcp(int a, int l)
    {
        if (a == l)
            return len - a;
        int u = rank[a], v = rank[l];
        return u > v ? RMQ(v + 1, u) : RMQ(u + 1, v);
    }

} suffix_array;

char str[maxn];

int calc(int val)
{
    int ret = 1;
    while (val > 9) {
        val /= 10;
        ret++;
    }
    return ret;
}

int main()
{
    int qn, pl, pr, l, r;
    while (scanf("%s", str) != EOF) {
        suffix_array.input(str);
        suffix_array.initRMQ();
        scanf("%d %d %d", &qn, &pl, &pr);
        ll lans = pr - pl + 1, rans = pr - pl + 3;
        qn--;
        while (qn--) {
            scanf("%d %d", &l, &r);
            int lcp = suffix_array.lcp(pl, l);
            lcp = min(lcp, min(pr - pl, r - l));
            lans += r - l + 1;
            rans += r - l + 2 - lcp + calc(lcp);
            pl = l, pr = r;
        }
        printf("%lld %lld\n", lans, rans);
    }
    return 0;
}
后缀数组

HDU 4552 怪盗基德的挑战书

Posted on

一道不知所以然的题目……

没什么好废话的,直接上题解。

题意:
要你求一个字符串的所有前缀在自己本身的所有出现次数。

思路:
这道题如果用KMP的话是十分简单的,但是我一开始没想到用KMP,想了一些时间,看了kuangbin的博客说可以用KMP求解,略想了一下,果真如此。

KMP思路:
直接next数组跳几下就可以了。

后缀数组思路:
后缀数组的思路让我有点蒙逼……只要将所有后缀与最长的后缀,也就是原串的最长公共前缀相加再加上原串长度就是答案。
而看过论文的都应该知道,这个是可以\( O( n ) \)直接求出来的。
但是还是有点似董非董。

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 1e5 + 5;
int sa[maxn];
int t1[maxn], t2[maxn], buc[maxn];
int rnk[maxn], height[maxn];

void buildSA(int s[], int n, int m) //n取字符串长度+1 m为字符中的上界 一般为 128
{ 
    int p, *x = t1, *y = t2;
    each(i, m) buc[i] = 0;
    each(i, n) buc[x[i] = s[i]]++;
    range(i, 1, m - 1) buc[i] += buc[i - 1];
    reach(i, n) sa[--buc[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1) {
        p = 0;
        range(i, n - k, n - 1) y[p++] = i;
        each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1, x[sa[0]] = 0;
        range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
        if (p >= n)
            break;
        m = p;
    }
}

void getHeight(int s[], int n) //n为字符串长度
{
    int j, k = 0;
    each(i, n + 1) rnk[sa[i]] = i;
    each(i, n)
    {
        k ? k-- : 0;
        j = sa[rnk[i] - 1];
        while (s[i + k] == s[j + k])
            k++;
        height[rnk[i]] = k;
    }
}

char str[maxn];
int s[maxn];

int main()
{
    while (scanf("%s", str) != EOF) {
        int len = strlen(str);
        range(i, 0, len) s[i] = str[i];
        buildSA(s, len + 1, 128);
        getHeight(s, len);
        int t = rnk[0], ans = len, tmp = len;
        while (t > 1) {
            tmp = min(tmp, height[t--]);
            ans += tmp;
        }
        t = rnk[0] + 1, tmp = len;
        while (t <= len) {
            tmp = min(tmp, height[t++]);
            ans += tmp;
        }
        printf("%d\n", ans % 256);
    }
    return 0;
}
后缀数组

POJ 2774 Long Long Message

Posted on

后缀数组论文题,也是后缀数组的入门题——最长公共子串。
另外这题是双倍经验 HDU 1403 Longest Common Substring不过HDU的数据更水一点。

题意:
给你两个字符串,求最长公共子串。

思路:
因为是论文题,我不可能讲的比论文还详细的啦……这不是显然的吗

看了论文后基本就是套板子,因为它已经吧最关键的地方给证明了,然后有一个小地方,为什么可以直接拿 sa 数组与第一个字符串长度 key 比较呢?
那是因为,sa数组本身就是记录后缀排名第 idx 位的是哪一个后缀,而后缀和第一个字符串 key ,都是从左往右正向计数的。故可以直接拿来比较。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 2e5 + 10;
int sa[maxn];
int rnk[maxn], height[maxn];

void buildSA(int s[], int n, int m)
{
    int t1[maxn], t2[maxn], buc[maxn];
    int p, *x = t1, *y = t2;
    each(i, m) buc[i] = 0;
    each(i, n) buc[x[i] = s[i]]++;
    range(i, 1, m - 1) buc[i] += buc[i - 1];
    reach(i, n) sa[--buc[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1) {
        p = 0;
        range(i, n - k, n - 1) y[p++] = i;
        each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1, x[sa[0]] = 0;
        range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
        if (p >= n)
            break;
        m = p;
    }
}

void getHeight(int s[], int n)
{
    int j, k = 0;
    each(i, n + 1) rnk[sa[i]] = i;
    each(i, n)
    {
        k ? k-- : 0;
        j = sa[rnk[i] - 1];
        while (s[i + k] == s[j + k])
            k++;
        height[rnk[i]] = k;
    }
}

char str[maxn];
int s[maxn], slen[maxn];

int main()
{
    while (scanf("%s", str) != EOF) {
        int len = strlen(str), key = len;
        str[len] = '$';
        scanf("%s", str + len + 1);
        len = strlen(str);
        each(i, len+1) s[i] = str[i];
        buildSA(s, len + 1, 128);
        getHeight(s, len);
        int ans = 0;
        range(i, 2, len) if ((sa[i] < key) + (sa[i - 1] < key) == 1) ans = max(ans, height[i]);
        printf("%d\n", ans);
    }
    return 0;
}
KMP

HDU 6153 A Secret

Posted on

CCPC网络赛的KMP模板题……

比赛期间因为被1003卡住了,这道题根本没时间去想……

本来一眼看去我是想到AC自动机,只要吧字符串反转一下,就可以套用上一次的AC自动机直接求解。
但是模式串和匹配串都只有一个,建立AC自动机虽然可解,但有不必要的消耗。

这道题几乎卡掉了除了KMP以外的所有求这道题的其他解法。

题意:
给你两个串a , b,要你找出 b 串的所有后缀同时也是 a 串的子串。
然后按题意计算。

思路:
其实还是和上一道AC自动机有些类似之处。
但还是有很大不同,AC自动机可以在匹配的时候不断 fail 到前缀。
而KMP只能通过记录匹配,然后从后往前不断 next 累加。

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

const int mod = 1e9 + 7;
const int max_n = 1e6 + 10;

char des[max_n], src[max_n];
int nxt[max_n], dlen, slen;
int num[max_n];

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < dlen)
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

void KMPCount()
{
    fill(num, num + dlen + 1, 0);
    int i, j = 0;
    ll ans = 0;
    getNext();
    for (i = 0; i < slen; i++) {
        while (j > 0 && src[i] != des[j])
            j = nxt[j];
        if (src[i] == des[j]) {
            j++;
            num[j]++;
        }
        if (j == dlen)
            j = nxt[j];
    }
    for (int i = dlen; i > 0; i--)
        num[nxt[i]] += num[i];
    for (int i = 1; i <= dlen; i++)
        ans = (ans + (1LL * num[i] * i) % mod) % mod;
    printf("%lld\n", ans);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s %s", src, des);
        dlen = strlen(des), slen = strlen(src);
        reverse(des, des + dlen), reverse(src, src + slen);
        KMPCount();
    }
    return 0;
}
AC自动机

HDU 6138 Fleet of the Eternal Throne

Posted on

昨天多校的AC自动机入门题……

为什么我还要写AC自动机入门题呢,因为我太不甘心了……

题意:
给你很多个字符串,很多个询问。
每个询问两个数\( a , b\) ,表示询问第 \( a\)个字符串和第\( b\)个字符串的最长的子串同时必须是某一个给定字符串的前缀。

思路:
这个真的是很简单的,建议AC自动机初学者写完 HDU 2222 后马上来写这题……
仔细思考,AC自动机建立在Tire图上,Trie图上的一个结点就代表了一个前缀。
所以我将所有字符串建立一个AC自动机,对于一个询问的两个字符串,我用一个set去记录第一个字符串所能到达的结点。第二个字符串去查询是否有相同结点。如果有,就说明有一个子串同时是某一个字符串的前缀。将当前答案与这个结点的深度进行比较就好了……

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
const int max_n = 1e5 + 10;
const int max_c = 26;

struct Aho {
    int next[max_n][max_c], fail[max_n], dep[max_n];
    int root, size;
    queue<int> que;
    set<int> key;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        size++;
        return size - 1;
    }

    void init()
    {
        size = 1;
        root = newNode();
        dep[root] = 0;
    }

    void insert(const string& str)
    {
        int len = str.length(), now = root;
        for (int i = 0; i < len; i++) {
            int c = str[i] - 'a';
            if (!next[now][c]) {
                next[now][c] = newNode();
                dep[next[now][c]] = dep[now] + 1;
            }
            now = next[now][c];
        }
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    void query(const string& str, bool is_first)
    {
        if (is_first)
            key.clear();
        int now = root, len = str.length(), ans = 0;
        for (int i = 0; i < len; i++) {
            now = next[now][str[i] - 'a'];
            int cur = now;
            while (cur != root) {
                if (is_first)
                    key.insert(cur);
                else if (key.find(cur) != key.end()) 
                    ans = max(ans, dep[cur]);
                cur = fail[cur];
            }
        }
        if (!is_first)
            printf("%d\n", ans);
    }
} aho;

string str[max_n];

int main()
{
    ios_base::sync_with_stdio(false);

    int T, n, q, a, b;
    cin >> T;
    while (T--) {
        cin >> n;
        aho.init();
        for (int i = 0; i < n; i++) {
            cin >> str[i];
            aho.insert(str[i]);
        }
        aho.build();
        cin >> q;
        while (q--) {
            cin >> a >> b;
            if (a == b)
                printf("%d\n", (int)str[a - 1].length());
            else {
                aho.query(str[a - 1], true);
                aho.query(str[b - 1], false);
            }
        }
    }
    return 0;
}
AC自动机

HDU 6096 String

Posted on

AC自动机好题,恐怕出题人都完全没有想到是AC自动机。
队友在写这题的时候突然发现了AC自动机的题解。
我看了一下发现还真是板子题。

正文:

WTM!!!!想打人!!!!!!!!!

Shit!!!

淦,再也不为了缩行偷懒了

这题我真的写了好久,今天刚刚发现错误,真的真的真的就是一个板子题,不过要转换一下并且check一下长度就可以了。
但是!!我为了偷懒,在输出的时候,就把答案清零了,这就导致了相同前后缀的答案错误!!!

题意:
给你很多字符串。再给你多组前后缀,问这几组前后缀在以上字符串的出现次数。

思路:
将前缀prefix 与 后缀 suffix 通过一个非字母字符连接,插入到trie中。
再将模式串通过相同的非字母字符连接,对其跑一边AC 自动机记录一下答案就可以了。

需要注意的地方就是模式串的长度不能小于后缀+前缀。

AC Code

#include <bits/stdc++.h>

using namespace std;

const int max_n = 5e5 + 10;
const int max_c = 27;

int ans[max_n], mp[max_n];

struct Aho {
    int next[max_n][max_c], fail[max_n];
    int limit[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        limit[size++] = 0;
        return size - 1;
    }

    void init()
    {
        size = 1;
        root = newNode();
    }

    int insert(char str[])
    {
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            int c = str[i] - 'a';
            if (!next[now][c])
                next[now][c] = newNode();
            now = next[now][c];
        }
        limit[now] = len - 1;
        return now;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    void query(char str[], int len)
    {
        int now = root;
        for (int i = 0; str[i]; i++) {
            now = next[now][str[i] - 'a'];
            int cur = now;
            while (cur != root) {
                if (limit[cur] && len >= limit[cur])
                    ans[cur]++;
                cur = fail[cur];
            }
        }
    }
} aho;

char str[max_n], prefix[max_n], suffix[max_n];
pair<int, int> key[max_n];

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        memset(ans, 0, sizeof ans);
        scanf("%d %d", &n, &m);
        int cur = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%s", str + cur);
            key[i] = make_pair(cur, strlen(str + cur));
            cur += key[i].second;
        }
        aho.init();
        for (int i = 1; i <= m; i++) {
            scanf("%s %s", prefix + 1, suffix);
            prefix[0] = '{';
            strcat(suffix, prefix);
            mp[i] = aho.insert(suffix);
        }
        aho.build();
        for (int i = 1; i <= n; i++) {
            int st = key[i].first, en = st + key[i].second;
            for (int j = st; j <= en; j++)
                prefix[j - st] = suffix[j - st] = str[j];
            prefix[key[i].second] = suffix[key[i].second] = 0;
            strcat(prefix, "{");
            strcat(prefix, suffix);
            aho.query(prefix, key[i].second);
        }
        for (int i = 1; i <= m; i++)
            printf("%d\n", ans[mp[i]]); //我在这里给ans清零了……
    }
    return 0;
}