Untitled
unknown
c_cpp
a year ago
2.4 kB
3
Indexable
Never
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #define int unsigned long long #define MAXN 1000005 #define MOD 39916801 #define mul 31 typedef struct Node{ int val, num, used; struct Node* nxt; } Node; Node *set[MOD]; int cur=0; int cnt(int val){ Node *p=set[val%MOD]; while(p){ if(p->val==val) { if(p->used==cur) return 0; p->used=cur; return p->num; } p=p->nxt; } return 0; } void insert(int val){ if(set[val%MOD] == NULL){ set[val%MOD]=malloc(sizeof(Node)); set[val%MOD]->val=val; set[val%MOD]->num=1; }else{ Node *p=set[val%MOD]; while(p){ if(p->val==val) { p->num++; return; } p=p->nxt; } Node *newNode=malloc(sizeof(Node)); newNode->nxt=set[val%MOD]; newNode->val=val; newNode->num=1; set[val%MOD]=newNode; } } void delete(int val){ if(set[val%MOD]->val==val){ set[val%MOD]->num--; if(set[val%MOD]->num==0) set[val%MOD]=set[val%MOD]->nxt; }else{ Node *p=set[val%MOD]; while(p->nxt){ if(p->nxt->val==val){ p->nxt->val--; if(p->nxt->val==0) p->nxt=p->nxt->nxt; break; } p=p->nxt; } } } char s[MAXN]; int ans=0; void add(){ scanf("%s",s); int len=strlen(s), hash=0, base=1; for(int i=0;i<len;i++){ s[i]-='a'-1; hash*=mul; hash+=s[i]; base*=mul; } cur++; for(int i=0;i<len;i++){ ans+=cnt(hash); hash*=mul; hash-=base*s[i]; hash+=s[i]; } insert(hash); } void rm(){ scanf("%s",s); int len=strlen(s), hash=0, base=1; for(int i=0;i<len;i++){ s[i]-='a'-1; hash*=mul; hash+=s[i]; base*=mul; } delete(hash); cur++; for(int i=0;i<len;i++){ ans-=cnt(hash); hash*=mul; hash-=base*s[i]; hash+=s[i]; } } signed main(){ int n,m; scanf("%llu %llu",&n,&m); for(int j=0;j<n;j++) { add(); } printf("%llu\n", ans); while(m--){ int x; scanf("%llu",&x); if(x==1) add(); else rm(); printf("%llu\n", ans); } }