第一眼, 这不是很裸嘛?
直接构造广义 SAM 然后跑就行了啊.
动态询问 endpos 集合大小, LCT 就好了嘛
(码...)
码了一半, 然后发现, 每次新加入一个子树啊, 复杂度是假的啊?
那这么说网上很多题解貌似都是假的...
(你按照 dfs 的顺序来加, 不是就必然会被卡了嘛)
但是这个题不强制在线!
可以先把整个树搭建好再处理询问.
考虑我们加入一个字符, 其实是在让一些 SAM 上的节点 从 "没出现过" 变成 "出现过"
考虑在 parent 树上, 可以直接跳, 因为一个节点只会从没出现过变成出现过一次, 是 $ O(n) $ 的
这样就可以方便的维护第一个东西啦
当然, 加入一个字符后就把这个点在 parent 树上的祖先全部 + 1, 这样就维护好第三个操作啦
祖先 + 1 可以看作单点 + 1, 区间查询, 可以用 BIT 维护
复杂度带个 BIT 的 log, 不卡常都 2000ms 跑过去.
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- #include<queue>
- using namespace std;
- typedef long long ll;
- #define MAXN 500006
- int n , lst , m;
- struct SAM{
- int son[MAXN][27]; // sons
- int par[MAXN] , len[MAXN]; // node
- int cnt;
- int sz[MAXN];
- int head[MAXN] , to[MAXN <<1] , nex[MAXN << 1] , ecn;
- ll num;
- void init( ) {
- memset( son , 0 , sizeof son ); memset( head , 0 , sizeof head );
- cnt = lst = 1; ecn = 0;
- }
- void ade( int u , int v ) {
- nex[++ecn] = head[u] , head[u] = ecn , to[ecn] = v;
- }
- void addall( ) {
- for( int i = 2 ; i <= cnt ; ++ i ) ade( par[i] , i );
- }
- void ins( int x ) {
- int cur = ++ cnt;
- len[cur] = len[lst] + 1 , sz[cur] = 1;
- int p = lst;
- while( p && !son[p][x] ) son[p][x] = cur , p = par[p];
- if( !p ) par[cur] = 1;
- else {
- int q = son[p][x];
- if( len[q] == len[p] + 1 ) par[cur] = q;
- else {
- int cl = ++ cnt;
- memcpy( son[cl] , son[q] , sizeof son[q] );
- par[cl] = par[q]; // copy
- len[cl] = len[p] + 1 , par[q] = par[cur] = cl;
- for( ; son[p][x] == q ; p = par[p] ) son[p][x] = cl;
- }
- }
- lst = cur;
- }
- int L[MAXN] , R[MAXN] , dfn;
- void dfs( int u ) {
- L[u] = ++ dfn;
- for( int i = head[u] ; i ; i = nex[i] )
- dfs( to[i] );
- R[u] = dfn;
- }
- int vis[MAXN];
- int jump( int u ) {
- if( vis[u] ) return 0;
- vis[u] = 1;
- return len[u] - len[par[u]] + jump( par[u] );
- }
- int T[MAXN];
- void add( int u , int c ) {
- while( u < MAXN ) T[u] += c , u += ( u & -u );
- }
- int sum( int u ) {
- int ret = 0;
- while( u> 0 ) ret += T[u] , u -= ( u & -u );
- return ret;
- }
- void getit( int u ) {
- // printf("get : %d\n",u);
- num += jump( u );
- add( L[u] , 1 );
- }
- int mach( char* c , int l ) {
- int cur = 1;
- for( int i = 0 ; i <l ; ++ i ) {
- if( !son[cur][c[i] - 'a'] ) return 0;
- else cur = son[cur][c[i] - 'a'];
- }
- return sum( R[cur] ) - sum( L[cur] - 1 );
- }
- } S ;
- int head[MAXN] , to[MAXN << 1] , nex[MAXN << 1] , wt[MAXN] , ecn;
- void ade( int u , int v , int w ) {
- to[++ ecn] = v , nex[ecn] = head[u] , head[u] = ecn , wt[ecn] = w;
- }
- int pos[MAXN] , fa[MAXN];
- vector<int> ps[MAXN]; int cni;
- void bfs( int u ) {
- queue<int> Q;
- Q.push( u );
- while( !Q.empty( ) ) {
- int x = Q.front(); Q.pop();
- for( int i = head[x] ; i ; i = nex[i] ) {
- int v = to[i];
- if( fa[x] == v || fa[v] ) continue;
- fa[v] = x;
- lst = pos[x];
- S.ins( wt[i] );
- pos[v] = lst , Q.push( v );
- ps[cni].push_back( v );
- }
- }
- }
- char ch[MAXN]; int bk[MAXN] , ln[MAXN] , id , tot;
- char op[MAXN];
- struct query {
- int opt , id;
- } Q[MAXN] ;
- int main() {
- scanf("%*d");
- cin>> n;
- for( int i = 1 , u , v ; i <n ; ++ i ) {
- scanf("%d%d%s",&u,&v,ch);
- ade( u , v , ch[0] - 'a' ) , ade( v , u , ch[0] - 'a' );
- }
- S.init(); pos[1] = 1;
- bfs( 1 );
- cin>> m;
- int opt , rt , s;
- for( int i = 1 ; i <= m ; ++ i ) {
- scanf("%d",&opt);
- if( opt == 1 ) {
- Q[i].opt = 1;
- } else if( opt == 2 ) {
- Q[i].opt = 2;
- ++ cni;
- scanf("%d%d",&rt,&s);
- for( int i = 1 , u , v ; i < s ; ++ i ) {
- scanf("%d%d%s",&u,&v,ch);
- ade( u , v , ch[0] - 'a' ) , ade( v , u , ch[0] - 'a' );
- }
- bfs( rt );
- Q[i].id = cni;
- } else {
- scanf("%s",op + tot);
- bk[i] = tot , ln[i] = strlen( op + tot );
- tot += ln[i];
- Q[i].opt = 3;
- }
- }
- Q[0].opt = 2;
- S.addall();
- S.dfs( 1 );
- for( int i = 0 ; i <= m ; ++ i ) {
- int o = Q[i].opt;
- if( o == 1 ) {
- printf("%lld\n",S.num);
- } else if( o == 2 ) {
- int c = Q[i].id;
- for( int j = 0 ; j < ps[c].size() ; ++ j ) {
- int u = ps[c][j];
- S.getit( pos[u] );
- }
- } else {
- printf("%d\n",S.mach( op + bk[i] , ln[i] ));
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3399409.html