题目描述
阿里巴巴的手机代理商正在研究 infra 输入法的新功能。他们需要分析单词频率以改进用户输入法的体验。于是需要你在系统内核里面写一个 API。API有如下功能：
- 添加操作
添加操作格式为$insert~~barty~~8$，意思为插入$barty$这个单词，这个单词词频为 $8$ 次。注意如果再次添加$insert~~barty~~8$操作时，就会将词频增加为 $16$ 次。（不会出现词频$\le 0$的情况）。 - 删除操作
删除操作格式为$delete~~barty$，意思为删除所有$barty$这个单词。
如果当前没有删除的词汇，输出"$Empty$"。 - 查询操作
查询操作格式为$query~~ty$，意思为查询当前版本以$ty$结尾的单词词频总和。 - 修改操作
修改操作格式为$update~~ty~~tied$，意思为将所有结尾是$ty$的单词更新为$tied$结尾，比如$barty$会变为$bartied$。如果不存在$ty$结尾的单词，输出$Empty$。如果已经存在$tied$结尾的单词，那么说明存在$conflict$。 不做合并，输出$Conflict$。如果既不存在$ty$结尾的单词，也已经存在以$tied$结尾的单词，则输出$Empty$。
输入格式
第一行读入一个整数 $T$，代表数据组数。
每组数据的第一行读入一个整数 $N$ 代表操作数。
接下来 $N$ 行，每行形容一个操作。
保证数据满足 $1\le T\le 10$，$1\le N\le 10^5$，$insert$和$update$操作的字符串总长度之和 $\le 10^6$，所有字符串长度 $≤10^6$，输入只有小写字母。
输出格式
输出题目中要求的结果
样例输入
1
10
update y ty
insert barty 8
delete shawn
update ty tied
query tied
insert party 9
update y tied
query ty
delete barty
query tied样例输出
Empty
Empty
8
Conflict
9
Empty
8题目链接
注:登陆了才能看到题目
思路
逆序字典树，转移的时候把所有节点都移过去的ok了，这样每个操作效率是$O(n*26),n<10^6$。
代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef long long LL;
struct trie
{
LL count;
trie *next[26];
};
trie *root;
trie* newtrie()
{
trie *t;
t=(trie*)malloc(sizeof(struct trie));
memset(t,0,sizeof(struct trie));
return t;
}
char oo[100000+100];
char o2[100000+100];
void Insert(char *ch,LL num)
{
int i;
trie *t,*s;
s=root;
for(i=0;ch[i];i++)
{
if(s->next[ch[i]-'a'])
{
s=s->next[ch[i]-'a'];
s->count=s->count+num;
}
else
{
t=newtrie();
s->next[ch[i]-'a']=t;
s=t;
s->count=num;
}
}
}
LL Search(char *ch)/*搜索函数，返回0则代表字典树不存在该字符串，反之亦然 */
{
int i;
trie *s=root;
if(ch[0]==0) return 0;
for(i=0;ch[i];i++)
{
if(s->next[ch[i]-'a'])
s=s->next[ch[i]-'a'];
else
break;
}
if(ch[i]==0) return s->count;
else return 0;
}
bool Delete(char *ch)/*删除函数，将该字符串从字典树中删除（删除之前记得事先判断存不存在该字符串）*/
{
int i;
trie *s;
s=root;
if(ch[0]==0)
return false;
for(i=0;ch[i];i++)
{
// printf("%c -%lld\n",ch[i],s->count);
if(s->next[ch[i]-'a'])
s=s->next[ch[i]-'a'];
else
return false;
}
LL sum=0;
sum+=s->count;
for(i=0;i<26;i++)
if(s->next[i])
sum-=s->next[i]->count;
if(sum==0)
return false;
Insert(ch,-sum);
return true;
}
LL Update(char *ch1,char *ch2)
{
LL t1,t2;
t1=Search(ch1);
t2=Search(ch2);
if(t1==0)
return -1;//printf("%d %d\n",t1,t2);
if(t2!=0)
return 1;
//
int i;
trie *t,*s;
s=root;
for(i=0;ch1[i];i++)
s=s->next[ch1[i]-'a'];
trie *pp[26];
LL sum=s->count;
for(i=0;i<26;i++)
{
pp[i]=s->next[i];
s->next[i]=NULL;
}
Insert(ch1,-sum);
s=root;
//
for(i=0;ch2[i];i++)
{
if(s->next[ch2[i]-'a'])
{
s=s->next[ch2[i]-'a'];
s->count+=sum;
}
else
{
t=newtrie();
s->next[ch2[i]-'a']=t;
s=t;
s->count=sum;
}
}
for(int i=0;i<26;i++)
s->next[i]=pp[i];
return 0;
//
}
void swap(char *ch)
{
int len=strlen(ch);
for(int i=0;i<len/2;i++)
{
char z=ch[i];
ch[i]=ch[len-1-i];
ch[len-1-i]=z;
}
}
void clear(trie *now)
{
if(now==NULL)
return ;
for(int i=0;i<26;i++)
clear(now->next[i]);
free(now);
}
int main()
{
int T;
scanf("%d",&T);
root=newtrie();
while(T--)
{
int N;
scanf("%d",&N);
clear(root);
root=newtrie();
while(N--)
{
char ope[10];
getchar();
scanf("%s",ope);
if(ope[0]=='i')
{
LL tt;
scanf("%s %lld",oo,&tt);
swap(oo);
Insert(oo,tt);
}
if(ope[0]=='d')
{
scanf("%s",oo);
swap(oo);
bool q=Delete(oo);
if(q==false)
printf("Empty\n");
}
if(ope[0]=='q')
{
scanf("%s",oo);
swap(oo);
LL z=Search(oo);
if(z==0)
printf("0\n");
else
printf("%lld\n",z);
}
if(ope[0]=='u')
{
scanf("%s %s",oo,o2);
swap(oo);
swap(o2);
int z=Update(oo,o2);
if(z==-1)
printf("Empty\n");
if(z==1)
printf("Conflict\n");
// printf("\n\n%d\n\n",z);
}
}
}
return 0;
}