题目概述

有 $n$ 个询问：

1. $Insert\ s\ x$ ：增加 $x$ 个 $s$ 。
2. $Delete\ s$ ：删除所有 $s$ 。
3. $Query\ s$ ：查询以 $s$ 为后缀的字符串数量。
4. $Update\ s\ t$ ：把后缀 $s$ 换成 $t$ ，保证 $Query\ t=0$ 。

解题报告

神tm调代码能力大赛，先把串反一下，然后后缀就变成了前缀，用Trie搞就行了。

$Update$ 操作实际上就是把 $s$ 的子树截下来然后移到 $t$ 的子树上，因为保证之前 $t$ 不存在，所以不用考虑子树合并（而且我也不会啊）。

其实有进阶版的……就是多了个回退操作……可持久化一下就行了，懒得写了XD。

示例程序

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxl=1e6,maxt=maxl<<1,maxi=26;

int te,n;char td[maxl+5],s[maxl+5],t[maxl+5];
int si,son[maxt+5][maxi];LL sum[maxt+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline int reads(char *s){
    int len=0;char ch=readc();while (!islower(ch)) ch=readc();
    while (islower(ch)) s[++len]=ch,ch=readc();return s[len+1]=0,len;
}
inline void Insert(char *s,LL num){
    int p=0;sum[p]+=num;
    for (int i=1;s[i];i++){
        if (!son[p][s[i]-'a']) son[p][s[i]-'a']=++si;
        p=son[p][s[i]-'a'];sum[p]+=num;
    }
}
inline LL val(int p){
    LL ans=sum[p];
    for (int i=0;i<maxi;i++)
        if (son[p][i]) ans-=sum[son[p][i]];
    return ans;
}
inline void Delete(char *s){
    int p=0;
    for (int i=1;s[i];i++){
        if (!son[p][s[i]-'a']) {puts("Empty");return;}
        p=son[p][s[i]-'a'];
    }
        LL tot=val(p);if (!tot) {puts("Empty");return;}
    p=0;sum[p]-=tot;for (int i=1;s[i];i++) sum[p=son[p][s[i]-'a']]-=tot;
}
inline LL Query(char *s){
    int p=0;
    for (int i=1;s[i];i++){
        if (!son[p][s[i]-'a']) return 0;
        p=son[p][s[i]-'a'];
    }
    return sum[p];
}
inline void Update(char *s,char *t){
    if (!Query(s)) {puts("Empty");return;} else if (Query(t)) {puts("Conflict");return;}
    int S=strlen(s+1),T=strlen(t+1),p,pp;
    p=0;for (int i=1;i<S;i++) p=son[p][s[i]-'a'];pp=son[p][s[S]-'a'];son[p][s[S]-'a']=0;
    p=0;sum[p]-=sum[pp];for (int i=1;i<S;i++) sum[p=son[p][s[i]-'a']]-=sum[pp];Insert(t,0);
    p=0;sum[p]+=sum[pp];for (int i=1;i<T;i++) sum[p=son[p][t[i]-'a']]+=sum[pp];son[p][t[T]-'a']=pp;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (readi(te);te;te--){
        si=0;memset(son,0,sizeof(son));memset(sum,0,sizeof(sum));
        for (readi(n);n;n--){
            reads(td);int len=reads(s);for (int i=1;i<=(len>>1);i++) swap(s[i],s[len-i+1]);
            if (!strcmp(td+1,"insert")) {int x;readi(x);Insert(s,x);}
            else if (!strcmp(td+1,"delete")) Delete(s);
            else if (!strcmp(td+1,"query")) printf("%lld\n",Query(s));
            else {len=reads(t);for (int i=1;i<=(len>>1);i++) swap(t[i],t[len-i+1]);Update(s,t);}
        }
    }
    return 0;
}