Untitled
unknown
c_cpp
2 years ago
1.9 kB
4
Indexable
#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; struct Node* nxt; } Node; Node *set[MOD]; int cnt(int val){ Node *p=set[val%MOD]; int ans=0; while(p){ if(p->val==val) ans++; p=p->nxt; } return ans; } void insert(int val){ if(set[val%MOD] == NULL){ set[val%MOD]=malloc(sizeof(Node)); set[val%MOD]->val=val; }else{ Node *newNode=malloc(sizeof(Node)); newNode->nxt=set[val%MOD]; newNode->val=val; set[val%MOD]=newNode; } } void delete(int val){ if(set[val%MOD]->val==val){ set[val%MOD]=set[val%MOD]->nxt; }else{ Node *p=set[val%MOD]; while(p->nxt){ if(p->nxt->val==val){ 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; } 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); 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); } }
Editor is loading...