Untitled

#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);
    }
}