HDU5687字典树WA乐求调
  • 板块灌水区
  • 楼主Vitamin_B
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/7/9 18:45
  • 上次更新2024/7/9 20:19:19
查看原帖
HDU5687字典树WA乐求调
743373
Vitamin_B楼主2024/7/9 18:45

rt,HDU5687WA力求找bug

//# pragma GCC optimize("Ofast,no-stack-protector")
//
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

# include <bits/stdc++.h>

# define I return

# define AK 0

# define IOI ;

typedef long long ll;

using namespace std;

int q, tr[3000005][30], s[3000005], tot;

bitset <3000005> lazy;

string op, a;

void pushdown (int x) {

    if (! lazy[x])
        return ;

    for (int i = 0; i < 26; ++ i)
        if (tr[x][i])
            s[tr[x][i]] = 0, lazy[tr[x][i]] = 1;

    lazy[x] = 0;

    return ;

}

void add () {

    int now = 0;

    for (char& i : a) {

        const int x = i - 'a';

        if (tr[now][x])
            now = tr[now][x];
        else
            now = tr[now][x] = ++ tot;

        ++ s[now];

    }

    return ;

}

void del () {

    int now = 0, t;

    for (char& i : a) {

        const int x = i - 'a';

        if (tr[now][x])
            now = tr[now][x];
        else
            return ;

        pushdown (now);

    }

    t = s[now], lazy[now] = 1, now = 0;

    for (char& i : a) {

        const int x = i - 'a';

        now = tr[now][x];

        s[now] -= t;

        pushdown (now);

    }

    return ;

}

bool find () {

    int now = 0;

    for (char& i : a) {

        const int x = i - 'a';

        if (tr[now][x])
            now = tr[now][x];
        else
            return 0;

        pushdown (now);

    }

    return s[now];

}

int main () {

    ios::sync_with_stdio (0);

    cin.tie (0);

    cout.tie (0);

    cin >> q;

    while (q --) {

        cin >> op >> a;

        if (op[0] == 'i')
            add ();
        else if (op[0] == 'd')
            del ();
        else
            cout << (find () ? "Yes\n" : "No\n");

    }

    I AK IOI

}
2024/7/9 18:45
加载中...