Untitled

 avatar
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...