本文共 1877 字，大约阅读时间需要 6 分钟。
\(thu\)怎么那么喜欢出\(trie\)树的题。。。
#include #include #include #include #include #include #include #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair #define LL long long int#define pb(x) push_back(x)using namespace std;const int maxn = 100005,maxm = 7000005,INF = 1000000000;inline LL read(){ LL out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}int n,lans;int ch[maxm][10],sum[maxm],mx[maxm],cnt;vector t[maxm];char s[70];void ins(int now,int v){ int u = 0,id,len = strlen(s + 1); for (int i = 1; i <= len; i++){ id = s[i] - 'a'; sum[u] += v; if (sum[u] > mx[u]) t[u].pb(mp(sum[u],now)),mx[u] = sum[u]; u = ch[u][id] ? ch[u][id] : ch[u][id] = ++cnt; } sum[u] += v; if (sum[u] > mx[u]) t[u].pb(mp(sum[u],now)),mx[u] = sum[u];}int query(LL v){ int u = 0,len = strlen(s + 1); for (int i = 1; i <= len; i++) u = ch[u][s[i] - 'a']; int l = 0,r = t[u].size() - 1,mid; while (l < r){ mid = l + r >> 1; if (t[u][mid].first > v) r = mid; else l = mid + 1; } return t[u][l].first > v ? t[u][l].second : -1;}int main(){ n = read(); int opt; LL a,b,c,v; for (int i = 1; i <= n; i++){ opt = read(); scanf("%s",s + 1); if (opt == 1) ins(i,1); else if (opt == 2) ins(i,-1); else { a = read(); b = read(); c = read(); v = (1ll * a * abs(lans) % c + b % c) % c; if (v >= i) lans = -1; else lans = query(v); printf("%d\n",lans); } } return 0;}
转载于:https://www.cnblogs.com/Mychael/p/9086902.html