题目

分析

首先，我们不需要真的从 AC 自动机中把串删掉。由于我们计算贡献和，我们只需要在 AC 自动机上，把已经删除的串的贡献抹掉就可以了。

接着考虑询问。这是一个很基础的问题，一般我们会在 AC 自动机上面处理出每个状态的贡献和，并且将询问的字符串在 AC 自动机上面跑一跑，答案就是经过的状态的贡献和的贡献和。

现在贡献是动态的，我们的贡献和也变成了动态的。不过，由于贡献和本质上就是\(fail\)树上到根的路径的贡献和，因此我们可以对\(fail\)树进行树链剖分，修改就是单点修改，查询就查询到根的贡献和。这样就可以用 BIT 来维护一下区间和。

另一种更简单的方法是，在一个点上改贡献的时候，有且仅有其子树内的点会被影响，因此我们用 BIT 维护差分，每次修改就是将子树内的贡献 +1 ，查询就直接查询。这样做就少了一个\(\log_2n\)。

这两种方法体现了两种不同的思想——统计贡献和维护贡献；两者需要具体问题具体分析再选择使用。

代码

#include <cstdio>

#include <iostream>

using namespace std;

#define Tour( c ) for( int c = 0 ; c < 26 ; c ++ )

#define up( x ) ( x += ( x & ( -x ) ) )

#define down( x ) ( x -= ( x & ( -x ) ) )

typedef long long LL;

const int MAXN = 1e5 + 5, MAXL = 1e6 + 5;

template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}

template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}

struct edge

{

	int to, nxt;

}Graph[MAXL << 1];

LL BIT[MAXL];

int head[MAXL], pos[MAXL], siz[MAXL];

int ch[MAXL][26], fail[MAXL], q[MAXL];

int ed[MAXN];

int N, K, tot, cnt, ID;

char S[MAXL];

bool inside[MAXN];

void update( int x, const int v ) { for( ; x <= ID ; up( x ) ) BIT[x] += v; }

LL getSum( int x ) { LL ret = 0; for( ; x ; down( x ) ) ret += BIT[x]; return ret; }

void update( const int x ) { if( ! inside[x] ) inside[x] = true, update( pos[ed[x]], 1 ), update( pos[ed[x]] + siz[ed[x]], -1 ); }

void remove( const int x ) { if( inside[x] ) inside[x] = false, update( pos[ed[x]], -1 ), update( pos[ed[x]] + siz[ed[x]], 1 ); }

void addEdge( const int from, const int to )

{

	Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];

	head[from] = cnt;

}

void insert( const int rnk )

{

	int p = 0, id;

	for( int i = 1 ; S[i] ; i ++ )

	{

		id = S[i] - 'a';

		if( ! ch[p][id] ) ch[p][id] = ++ tot;

		p = ch[p][id];

	}

	ed[rnk] = p;

}

void init()

{

	int h = 1, t = 0, u, v;

	Tour( i ) if( ch[0][i] ) q[++ t] = ch[0][i];

	while( h <= t )

	{

		u = q[h ++];

		Tour( i )

		{

			if( v = ch[u][i] ) fail[v] = ch[fail[u]][i], q[++ t] = v;

			else ch[u][i] = ch[fail[u]][i];

		}

		addEdge( fail[u], u );

	}

}

void DFS( const int u )

{

	siz[u] = 1, pos[u] = ++ ID;

	for( int i = head[u], v ; i ; i = Graph[i].nxt )

		DFS( v = Graph[i].to ), siz[u] += siz[v];

}

int main()

{

	LL ans; int id, p;

	read( N ), read( K );

	for( int i = 1 ; i <= K ; i ++ ) scanf( "%s", S + 1 ), insert( i );

	init();

	DFS( 0 );

	for( int i = 1 ; i <= K ; i ++ ) update( i );

	while( N -- )

	{

		scanf( "%s", S );

		if( S[0] == '?' )

		{

			ans = p = 0;

			for( int i = 1 ; S[i] ; i ++ )

				p = ch[p][S[i] - 'a'],

				ans += getSum( pos[p] );

			write( ans ), putchar( '\n' );

		}

		else if( S[0] == '+' ) sscanf( S + 1, "%d", &id ), update( id );

		else sscanf( S + 1, "%d", &id ), remove( id );

	}

	return 0;

}

巴特西

[CF163E]e-Government

题目

分析

代码

最新文章

热门文章