求助!神仙们救救蒟蒻吧...

回复帖子

@skicean 2019-06-22 21:45 回复
#include <cstdio>

using namespace std;

const int N = 6e5 + 10;
int n, m, q, tot;
int val[N], head[N], root[N], ch[N][2], par[N], sze[N], t[N], id[N];
//head就是并查集里面的祖先变量

void print(int x)
{
    if (ch[x][0]) print(ch[x][0]);
    printf("%d ", val[x]);
    if (ch[x][1]) print(ch[x][1]);
}

void newNode(int fa, int x, bool side, int index)
{
    val[++tot] = x;
    ch[tot][0] = ch[tot][1] = 0;
    if (fa)
    {
        par[tot] = fa;
        ch[fa][side] = tot;
    }
    sze[tot] = 1;
    id[tot] = index;
}

void init()
{
    for (int i = 1; i <= n; ++i)
    {
        newNode(0, val[i], 0, i);
        root[i] = tot;
        head[i] = i;
        t[i] = i;
    }
}

bool identify(int deal)
{
    return deal == ch[par[deal]][1];
}

void connect(int deal, int fa, bool side)
{
    ch[fa][side] = deal;
    par[deal] = fa;
}

void update(int deal)
{
    sze[deal] = sze[ch[deal][0]] + sze[ch[deal][1]] + 1;
}

void rotate(int deal)
{
    int fa = par[deal], gra = par[fa];
    bool sideFa = identify(fa), sideDeal = identify(deal);
    connect(ch[deal][sideDeal ^ 1], fa, sideDeal);
    connect(fa, deal, sideDeal ^ 1);
    connect(deal, gra, sideFa);
    update(fa); update(deal);
}

void splay(int i, int at, int to = 0)
{
    while (par[at] != to)
    {
        int fa = par[at], gra = par[fa];
        if (gra == to)
            rotate(at); 
        else if (identify(at) == identify(fa)) rotate(fa), rotate(at);
        else rotate(at), rotate(at);
    }
    if (!to) root[i] = at;
}

void insert(int i, int v, int index) //在第i棵树上插入权值为x的结点
{
    int now = root[i], p;
    while (now)
    {
        p = now;
        now = ch[now][val[now] < v];
    }
    newNode(p, v, val[p] < v, index);
    splay(i, tot);
}

int get(int x)
{
    if (head[x] == x) return x;
    else return head[x] = get(head[x]);
}

void dfs(int now, int i)
{
    if (ch[now][0]) dfs(ch[now][0], i);
    insert(i, val[now], id[now]);
    if (ch[now][1]) dfs(ch[now][1], i);
}

void swap(int &u, int &v)
{
    int r = u;
    u = v;
    v = r;
}

void merge(int u, int v)
{
    u = get(u), v = get(v);
    if (sze[root[t[u]]] > sze[root[t[v]]])
        swap(u, v);
    if (u != v)
        head[u] = v;
    else return;
    dfs(root[t[u]], t[v]);
}

void check()
{
    for (int i = 1; i <= n; ++i)
    {
        int Hi = get(i);
        printf("Hi = %d t[Hi] = %d mid : ", Hi, t[Hi]);
        print(root[t[Hi]]);
        printf("\n");
    }
}

void ask(int u, int v)
{
    u = get(u);
    if (v > sze[root[t[u]]])
    {
        printf("-1\n");
        return;
    }
    int now = root[t[u]];
    while (1)
    {
        if (v <= sze[ch[now][0]]) now = ch[now][0];
        else if (sze[ch[now][0]] + 1 == v)
        {
            printf("%d\n", id[now]);
            return;
        }
        else v -= sze[ch[now][0]], now = ch[now][1];
    }
}

void solve()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &val[i]);
    init();
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        merge(u, v);
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i)
    {
        char opr; int u, v;
        scanf("\n%c%d%d", &opr, &u, &v);
        if (opr == 'B') merge(u, v);
        else ask(u, v);
    }
}

int main()
{
    solve();
    return 0;
}

WA 2,AC 1,TLE* 7. 莫名其妙!救救我吧。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。