Uma string de exclusão pode ser representada como inserção com coeficiente -1. No modo offline, cada string existe em um intervalo de tempo (sufixo), sendo atribuída a um nó da árvore de segmentos. Em um nó da árvore, podemos construir um autômato AC (Aho-Corasick) para todas as strings daquele intervalo e responder consultas.

Entretanto, o problema exige operações online. A solução é utilizar o agrupamento binário: as strings atuais são divididas em grupos cujos tamanhos seguem potências de 2. Cada grupo mantém seu próprio autômato AC. Por exemplo, se n=7, os grupos são 4+2+1.

Quando uma nova string é adicionada, ela forma um grupo de tamanho 1 e é colocada no final. Se os dois últimos grupos tiverem o mesmo tamanho, eles são mesclados (ex: 4+2+1+1 → 4+2+2). O novo grupo gerado é reconstruído (executa-se a construção do autômato AC). Esse processo se repete até que os dois últimos grupos tenham tamanhos diferentes.

Análise de complexidade: cada string é mesclada no máximo log n vezes, pois cada mesclagem dobra o tamanho do grupo. Uma consulta percorre no máximo log n grupos. Complexidade total: O(n log n).

Código (reestruturado)

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define trav(i,v) for(int i=0;i<(int)v.size();++i)
#define pb push_back
using namespace std;

const int N=6e5+5;
int n,op,len;
char s[N];
int cnt[N];
int nxt[N][26],tot;

int ins(int u,int c){
    if(!nxt[u][c]) nxt[u][c]=++tot;
    return nxt[u][c];
}

int q[N],head,tail,fail[N];
long long sum[N];

void build(int root){
    fill(nxt[0],nxt[0]+26,root);
    q[head=tail=0]=root; fail[root]=0; sum[root]=0;
    while(head<=tail){
        int u=q[head++];
        rep(c,0,25) if(nxt[u][c]){
            int v=nxt[u][c];
            int k=fail[u];
            while(!nxt[k][c]) k=fail[k];
            k=nxt[k][c];
            fail[v]=k;
            sum[v]=cnt[v]+sum[k];
            q[++tail]=v;
        }
    }
}

int merge(int a,int b){
    if(!a||!b) return a+b;
    cnt[a]+=cnt[b];
    rep(c,0,25) nxt[a][c]=merge(nxt[a][c],nxt[b][c]);
    return a;
}

const int M=35;
int roots[M],sizes[M],num;

void compact(){
    while(num>1 && sizes[num]==sizes[num-1]){
        roots[num-1]=merge(roots[num-1],roots[num]);
        sizes[num-1]+=sizes[num];
        num--;
        build(roots[num]);
    }
}

int go(int u,int c){
    while(!nxt[u][c]) u=fail[u];
    return nxt[u][c];
}

int main(){
    scanf("%d",&n);
    rep(i,1,n){
        scanf("%d%s",&op,s+1); len=strlen(s+1);
        if(op<3){
            roots[++num]=++tot; sizes[num]=1;
            int u=roots[num];
            rep(j,1,len) u=ins(u,s[j]-'a');
            cnt[u]+= (op==1 ? 1 : -1);
            build(roots[num]);
            compact();
        }else{
            long long ans=0;
            rep(i,1,num){
                rep(c,0,25) nxt[0][c]=roots[i];
                int u=roots[i];
                rep(j,1,len){
                    u=go(u,s[j]-'a');
                    ans+=sum[u];
                }
            }
            printf("%lld\n",ans); fflush(stdout);
        }
    }
    return 0;
}

Exemplo 2: LOJ 3273

O problema envolve quatro operações; devemos primerio resolver o caso sem operação 4. Observa-se que depois de movido uma vez, o ponto torna-se monotônico. Mantemos duas árvores balanceadas: uma para pontos já movidos (com operações de atribuição de intervalo via busca binária) e outra para pontos nunca movidos (para localizar os que serão movidos).

No modo offline, cada consulta é um intervalo de operações, resolvível com segment tree divide-and-conquer. Para a versão online, aplicamos agrupmaento binário nos pontos atuais. Quando dois grupos são mesclados, consideramos que todos os pontos do novo grupo nunca foram movidos. A cada operação, percorremos os O(log n) grupos e aplicamos a operação em cada um.

Exemplo 3: BZOJ 4140 (Ponto dentro do círculo)

Seja (u,v) o centro e (x,y) o ponto consultado. A condição (x-u)²+(y-v)² ≤ u²+v² equivale a 2(ux+vy) ≥ x²+y². Assim, o problema reduz-se a minimizar ux+vy. Ignorando y=0, escrevemos y(u·x/y+v). Para y>0, queremos o máximo sobre um conjunto de retas; para y<0, o mínimo. Mantemos um casco convexo superior e inferior e realizamos busca binária.

Offline: cada círculo existe em um intervalo de tempo, resolvemos com segment tree divide-and-conquer. Online: agrupamento binário com reconstrução após mesclagem. Complexidade O(n log² n).

Código (reestruturado)

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
typedef double db;
struct Pt{db x,y; Pt(db _x=0,db _y=0):x(_x),y(_y){}};
const db eps=1e-8;

auto cmp1=[](Pt a,Pt b){return a.x==b.x?a.y<a.x a="" a.x="=b.x?a.y" auto="" b="" cmp2="[](Pt">b.y:a.x<b.x a="" all="" ans="(2*mi" b="" build="" const="" continue="" db="" else="" eps="" for="" if="" int="" inter="" low="" low.clear="" low.pb="" low.pop_back="" m="(l+r)/2;" main="" mi="1e18;" num="" num--="" p:all="" pos="0,l=0,r=sz(up)-2;" puts="" q="" r="m-1;" ratio="x/y;" rep="" return="" scanf="" solve="" sort="" sum_yes="0;" up="" up.back="" up.clear="" up.pb="" up.pop_back="" vector="" void="" while="" x="" y=""></b.x></a.x>