题解 - Vijos

1

#include<bits/stdc++.h>
using ll=long long;
using namespace std;
#define chk(c) ((c <= 'z' && c >= 'a') || (c =='P') || (c == 'B'))
#define C(c) (c - 'a')
 
const int maxn = 100009;
const int c = 26;
 
inline int read() {
    char c = getchar();
    for(; !isdigit(c); c = getchar());
    int ret = 0;
    for(; isdigit(c); c = getchar())
        ret = ret * 10 + c - '0';
    return ret;
}
 
struct Node {
    Node *ch[c], *fail, *par;
    int v, d;
    Node() : v(0) {
        memset(ch, 0, sizeof ch);
        fail = par = 0;
    }
} pool[maxn], *V[maxn], *pt = pool, *Rt;
 
struct Q {
    int d, x, y;
    inline void Read(int _d) {
        d = _d;
        x = read();
        y = read();
    }
    bool operator < (const Q &o) const {
        return y < o.y;
    }
} q[maxn];
 
int n, dfsn, qn;
int L[maxn], R[maxn], ql[maxn], qr[maxn], ans[maxn];
 
void Init() {
    int cnt = dfsn = n = 0;
    pt->d = n++;
    Rt = pt++;
    Node* t = Rt;
    char c = getchar();
    for(; !chk(c); c = getchar());
    for(; chk(c); c = getchar()) {
        if(c == 'P') {
            V[t->v = ++cnt] = t;
        } else if(c == 'B') {
            t = t->par;
        } else {
            if(!t->ch[C(c)]) {
                pt->par = t;
                pt->d = n++;
                t->ch[C(c)] = pt++;
            }
            t = t->ch[C(c)];
        }
    }
    scanf("%d", &qn);
    for(int i = 0; i < qn; i++) 
        q[i].Read(i);
    sort(q, q + qn);
    memset(ql, 0, sizeof(int) * (cnt + 1));
    memset(qr, -1, sizeof(int) * (cnt + 1));
    for(int i = 0; i < qn; i++) {
        if(!i || q[i - 1].y != q[i].y)
            ql[q[i].y] = i;
        if(i + 1 == qn || q[i + 1].y != q[i].y)
            qr[q[i].y] = i;
    }
}
 
struct edge {
    int to;
    edge* next;
} E[maxn << 1], *Pt = E, *head[maxn];
 
inline void AddEdge(int u, int v) {
    Pt->to = v;
    Pt->next = head[u];
    head[u] = Pt++;
}
 
queue<Node*> que;
 
void buildFail() {
    que.push(Rt);
    while(!que.empty()) {
        Node* t = que.front(); que.pop();
        if(t->fail)
            AddEdge(t->fail->d, t->d);
        for(int i = 0; i < c; i++) if(t->ch[i]) {
            Node* f = t->fail;
            while(f && !f->ch[i])
                f = f->fail;
            t->ch[i]->fail = f ? f->ch[i] : Rt;
            que.push(t->ch[i]);
        }
    }
}
 
struct BIT {
    int b[maxn];
    BIT() {
        memset(b, 0, sizeof b);
    }
    inline void Add(int x, int v) {
        for(; x <= n; x += x & -x)
            b[x] += v;
    }
    inline int Sum(int x) {
        int ret = 0;
        for(; x; x -= x & -x)
            ret += b[x];
        return ret;
    }
    inline int Query(int l, int r) {
        return Sum(r) - Sum(l - 1);
    }
} Bit;
 
void DFS(int x) {
    L[x] = ++dfsn;
    for(edge* e = head[x]; e; e = e->next) DFS(e->to);
    R[x] = dfsn;
}
 
void dfsAC(Node* t) {
    Bit.Add(L[t->d], 1);
    if(t->v) {
        for(int i = ql[t->v]; i <= qr[t->v]; i++)
            ans[q[i].d] = Bit.Query(L[V[q[i].x]->d], R[V[q[i].x]->d]);
    }
    for(int i = 0; i < c; i++)
        if(t->ch[i]) dfsAC(t->ch[i]);
    Bit.Add(L[t->d], -1);
}
 
int main() {
    
    Init();
    buildFail();
    DFS(0);
    dfsAC(Rt);
    for(int i = 0; i < qn; i++)
        printf("%d\n", ans[i]);
    
    return 0;
}

1

JSZX11556 LV 9 @ 9 年前

AC自动机+dfs序+树状数组
详细题解&&代码：
http://www.cnblogs.com/JSZX11556/p/5107395.html

0

151052 LV 9 @ 8 年前

调了一天，最后发现数组下标数据类型开成char了。。。我的青春啊！

0

TenderRun LV 10 @ 9 年前

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
char S[maxn];
int Query[maxn][2],ans[maxn],cntQ;
struct A_Cautomation{
int ch[maxn][27],fail[maxn],end[maxn],fa[maxn],ID[maxn],cnt,root,cont;
int fir[maxn],nxt[maxn],to[maxn],cot;
int be[maxn],en[maxn],sjc;
void Init()
{
memset(ch,0,sizeof(ch));
memset(fail,0,sizeof(fail));
memset(end,0,sizeof(end));
sjc=cot=cnt=cont=root=0;
}
void Insert()
{
scanf("%s",S);
int len=strlen(S),node=root;
for(int i=0;i<len;i++)
{
if(S[i]>='a'&&S[i]<='z'){
if(ch[node][S[i]-'']){ node=ch[node][S[i]-''];
}
else{
fa[++cnt]=node;
node=ch[node][S[i]-'`']=cnt;
}
}
else{
if(S[i]=='B'){
node=fa[node];
}
else{
end[node]=++cont;
ID[cont]=node;
}

}
}
}
void Build()
{
queue<int>q;
for(int i=1;i<=26;i++){
if(ch[root][i]){
fail[ch[root][i]]=root;
q.push(ch[root][i]);
}
else
ch[root][i]=root;
}
while(!q.empty())
{
int node=q.front();q.pop();
for(int i=1;i<=26;i++){
if(ch[node][i]){
fail[ch[node][i]]=ch[fail[node]][i];
q.push(ch[node][i]);
}
else{
ch[node][i]=ch[fail[node]][i];
}
}
}
}

void addedge(int a,int b)
{nxt[++cot]=fir[a];fir[a]=cot;to[cot]=b;}

void DFS(int node)
{
be[node]=++sjc;
for(int i=fir[node];i;i=nxt[i])
DFS(to[i]);
en[node]=sjc;
}

void BuildTree()
{
for(int i=1;i<=cnt;i++)
addedge(fail[i],i);

DFS(root);

}

int bit[maxn];
void change(int k,int x)
{
while(k<=100000)
{
bit[k]+=x;
k+=k&(-k);
}
}

int Quer(int k)
{
int ret=0;
while(k)
{
ret+=bit[k];
k-=k&(-k);
}
return ret;
}

void Solve()
{
memset(fir,0,sizeof(fir));cot=0;
memset(bit,0,sizeof(bit));
for(int i=1;i<=cntQ;i++)
Query[i][0]=ID[Query[i][0]],
Query[i][1]=ID[Query[i][1]],
addedge(Query[i][1],Query[i][0]);

int len=strlen(S),node=root;
for(int i=0;i<len;i++)
{
if(S[i]>='a'&&S[i]<='z'){
node=ch[node][S[i]-'`'];
change(be[node],1);
}
else{
if(S[i]=='B'){
change(be[node],-1);
node=fa[node];
}
else{
for(int i=fir[node];i;i=nxt[i]){
ans[i]=Quer(en[to[i]])-Quer(be[to[i]]-1);
}
}

}
}

for(int i=1;i<=cntQ;i++)
printf("%d\n",ans[i]);
}
}AC;

int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
AC.Init();
AC.Insert();
AC.Build();
AC.BuildTree();

int Q;
scanf("%d",&Q);
while(Q--)
scanf("%d%d",&Query[cntQ][0],&Query[++cntQ][1]);

AC.Solve();
return 0;
}

0

freefood LV 10 @ 11 年前

作为一个一个蒟蒻，跪了三个星期，终于在蔡大神的帮助下a了。这题网上的题解很多，不过大都把题解写的太简单了（对因为大神的题解只有三个字：傻叉题）……
总结一下网上题题解，其实就是一个奇妙的fail数，这个巧妙的东西看都看不懂真正比赛一定就是不出的。像我这种傻逼的做法就是建立一个ac自动机（蔡大神跪了两天我跪了2个星期）。首先建立一个ac自动机，不过不要把每个单词都取出来，网上话：1）遇到新的字母，增加节点（父亲节点下没有）或向下走（父亲节点下已有）； 2）遇到删除字母('B)，向上一层（即走到父节点） 3）产生一个新的单词('P')，标记一下这里是单词末尾。然后通过j单词上的节点的fail指针走能走到某个单词（i）的末尾，那么i就是j单词的一个匹配。（有一点好奇怪的就是一开始理解为一个单词在另一个单词中出现的个数，后来重新看题才发现是这个单词在整个字符串中出现的位置）。然后这样的话会超时……
所以大神们想了一个方法：反转fail指针，建立一个fail tree。从单词j上可以通过fail走到i的数量等于fail tree上，以i为根的子树有多少个单词j的点（嗯，由于数据很大大神们才不会告诉你要邻接表）。然后这只是第一步。
第二步就是所谓建立dfs序，这个东西好像很神奇但一直很乱到底是什么意思，其实很简单，就是比如根a1有两个节点a2、a3，那么dfs序就是a1-a2-a2-a3-a3-a1，其实就是dfs一遍时遍历的顺序呗。这是第二步
第三步就是处理了，重新处理一遍字符串，网上话:1)当遇到增加字母的时候，在dfs序中相应的位置（这个节点的op）+1; 2)当遇到删除字母（‘B'）的时候，将上一步加的op-1; 3)当产生一个新的单词（’P‘）的时候，处理询问，就是询问x的op到ed之间的和……
实际上处理很麻烦（一定是因为我代码能力差，各种各种怪的小方法解决了一些很麻烦的问题）然后第一个wa第二次只是开大了数组就ac了……三个星期终于在期中前搞完了。感谢大神们的指导以及不指导。关键还是要自己想通……

http://hi.baidu.com/macaulish64/item/9a0237f8a0244e9a31c199b1 代码……

0

Towerlight LV 10 @ 11 年前

蒟蒻虽然缩行得没法看还是写了80行……真是弱得不行……

/* Template the Final Chapter Light --- Fimbulvetr version 0.1 /
/ In this blizzard, I will find peace. */
# include <cstring>
# include <cstdio>
# include <algorithm>

using namespace std;
# define REP( i, n ) for ( int i = 1; i <= n; i ++ )
# define REP_0( i, n ) for ( int i = 0; i < n; i ++ )
# define REP_0N( i, n ) for ( int i = 0; i <= n; i ++ )
# define REP_G( i, u ) for ( int i = pos[ u ]; i; i = g[ i ].frt )
# define NSIZE 201000
int n, tgsz, gsz, rsz, asz, l, ans[ NSIZE ], tree[ 10 * NSIZE ], st[ NSIZE ], ed[ NSIZE ], tsz, pos[ NSIZE ], nd[ NSIZE ];
int tt, tpos[ NSIZE ], q[ NSIZE ];
char s[ NSIZE ];
struct edge { int y, frt, val; void Set ( int yt, int fr, int vl ) { y = yt, frt = fr, val = vl; } } g[ 2 * NSIZE ], tg[ 2 * NSIZE ];
struct acmnode { int edge[ 30 ], fail, par; } acm[ NSIZE ];
inline void AddEdge ( int x, int y, edge *g, int *pos, int &gsz, int val ) { g[ ++ gsz ].Set ( y, pos[ x ], val ), pos[ x ] = gsz; }
inline int LowBit ( int x ) { return x & ( x ^ ( x - 1 ) ); }
inline void AddV ( int x, int add ) { if ( !x ) return ; while ( x <= asz * 2 ) tree[ x ] += add, x += LowBit ( x ); }
inline int Query ( int x )
{
int ret = 0;
while ( x > 0 ) ret += tree[ x ], x -= LowBit ( x );
return ret;
}
void Search ( int x )
{
st[ x ] = ++ tsz;
REP_G ( i, x ) Search ( g[ i ].y );
ed[ x ] = tsz;
}
int main ()
{
freopen ( "type.in", "r", stdin );
freopen ( "type.out", "w", stdout );
scanf ( "%s", s ), l = strlen ( s );
# define v acm[ u ].edge[ c ]
# define f acm[ acm[ u ].fail ].edge[ c ]
int head = 1, tail = 0, u = 0, t1, t2;
REP_0 ( i, l )
{
if ( s[ i ] == 'P' ) nd[ ++ rsz ] = u;
else if ( s[ i ] == 'B' ) u = acm[ u ].par;
else
{
int c = s[ i ] - 'a' + 1;
if ( !v ) v = ++ asz, acm[ v ].par = u;
u = v;
}
}
u = 0;
REP ( c, 26 ) if ( v ) AddEdge ( 0, q[ ++ tail ] = v, g, pos, gsz, 0 );
while ( head <= tail )
{
u = q[ head ++ ];
REP ( c, 26 )
{
if ( v ) acm[ q[ ++ tail ] = v ].fail = f, AddEdge ( f, v, g, pos, gsz, 0 );
else v = f;
}
}
Search ( 0 ), scanf ( "%d", &n ), u = 0;
REP ( i, n ) scanf ( "%d%d", &t1, &t2 ), AddEdge ( t2, t1, tg, tpos, tgsz, i );
REP_0 ( i, l )
{
int c = s[ i ] - 'a' + 1;
if ( s[ i ] == 'P' )
{
int sq = nd[ ++ tt ];
for ( int i = tpos[ tt ]; i; i = tg[ i ].frt )
ans[ tg[ i ].val ] = Query ( ed[ nd[ tg[ i ].y ] ] ) - Query ( st[ nd[ tg[ i ].y ] ] - 1 );
}
else if ( s[ i ] == 'B' ) AddV ( st[ u ], -1 ), u = acm[ u ].par;
else AddV ( st[ u = v ], 1 );
}
REP ( i, n ) printf ( "%d\n", ans[ i ] );
return 0;
}

0

绿色的云 LV 10 @ 11 年前

BIT+DFS序+AC自动机（WINDOWS下会RE LINUX下可以过。。。懒得改了）：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std ;

#define MAXN 100100
#define lowbit( x ) ( ( - x ) & x )
#define clear( x ) memset( x , 0 , sizeof( x ) )
#define MAXV 500100

int getstr( char *s ) {
int len = 0 , ch ;
for ( ch = getchar( ) ; ! ( ( ch >= 'a' && ch <= 'z' ) || ch == 'B' || ch == 'P' ) ; ch = getchar( ) ) ;
s[ len ++ ] = ch ;
for ( ch = getchar( ) ; ( ch >= 'a' && ch <= 'z' ) || ch == 'B' || ch == 'P' ; ch = getchar( ) ) s[ len ++ ] = ch ;
return len ;
}

void getint( int &t ) {
int ch ;
for ( ch = getchar( ) ; ! ( ch >= '0' && ch <= '9' ) ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; ch >= '0' && ch <= '9' ; ch = getchar( ) ) t *= 10 , t += ch - '0' ;
}

void putint( int t ) {
if ( ! t ) putchar( '0' )
; else {
int ans[ 20 ] ;
ans[ 0 ] = 0 ;
for ( ; t ; t /= 10 ) ans[ ++ ans[ 0 ] ] = t % 10 ;
for ( int i = ans[ 0 ] ; i ; i -- ) putchar( '0' + ans[ i ] ) ;
}
putchar( '\n' );
}

struct node {
int fail , father , child[ 26 ] ;
node ( ) {
fail = father = 0 ; clear( child ) ;
}
} v[ MAXV ] ;

char s[ MAXN ] ;
int V = 0 , cnt = 0 , w[ MAXN ] ;

void Make_trie( ){
int len = getstr( s ) ;
int t = 0 ;
for ( int i = 0 ; i < len ; i ++ ) {
if ( s[ i ] == 'P' ) {
w[ ++ cnt ] = t ;
} else if ( s[ i ] == 'B' ) {
t = v[ t ].father ;
} else {
if ( ! v[ t ].child[ s[ i ] - 'a' ] ) v[ t ].child[ s[ i ] - 'a' ] = ++ V ;
v[ v[ t ].child[ s[ i ] - 'a' ] ].father = t ;
t = v[ t ].child[ s[ i ] - 'a' ] ;
}
}
}

queue<int>Q ;

void Make_fail( ) {
while ( ! Q.empty( ) ) Q.pop( ) ;
for ( int i = 0 ; i < 26 ; i ++ ) if ( v[ 0 ].child[ i ] ) {
Q.push( v[ 0 ].child[ i ] ) ;
}
while ( ! Q.empty( ) ) {
int ve = Q.front( ) ; Q.pop( ) ;
for ( int i = 0 ; i < 26 ; i ++ ) if ( v[ ve ].child[ i ] ) {
Q.push( v[ ve ].child[ i ] ) ; int u = v[ ve ].fail ;
for ( ; u && ! v[ u ].child[ i ] ; u = v[ u ].fail ) ;
v[ v[ ve ].child[ i ] ].fail = v[ u ].child[ i ] ? v[ u ].child[ i ] : 0 ;
}
}
}

struct edge {
edge *next ;
int t ;
edge ( ) {
next = NULL ;
}
} *head[ MAXV ] ;

void AddEdge( int s , int t ) {
edge *p = new( edge ) ;
p -> t = t , p -> next = head[ s ] ;
head[ s ] = p ;
}

int arr[ MAXV * 2 ] , in[ MAXV ] , out[ MAXV ] , Index = 0 ;

void dfs( int t ) {
arr[ in[ t ] = ++ Index ] = t ;
for ( edge *p = head[ t ] ; p ; p = p -> next ) dfs( p -> t ) ;
arr[ out[ t ] = ++ Index ] = t ;
}

void Fail_tree( ) {
clear( head ) ;
for ( int i = 0 ; i ++ < V ; ) AddEdge( v[ i ].fail , i ) ;
dfs( 0 ) ;
}

struct qtype {
qtype *next ;
int x , r ;
} *fro[ MAXV ] ;

void Insert( int s , int t , int r ) {
qtype *p = new( qtype ) ;
p -> x = s , p -> r = r , p -> next = fro[ t ] ;
fro[ t ] = p ;
}

int m ;

void Init_query( ) {
getint( m ) ; clear( fro ) ;
for ( int i = 0 ; i ++ < m ; ) {
int s , t ;
getint( s ) , getint( t ) ; Insert( w[ s ] , w[ t ] , i ) ;
}
}

struct Bit {
int a[ MAXV *2 ] , N ;

void Init( int _N ) {
N = _N ; clear( a ) ;
}

void Add( int x ,int y ) {
for ( int i = x ; i <= N ; i += lowbit( i ) ) a[ i ] += y ;
}

int Sum( int l , int r ) {
int rec = 0 ;
for ( int i = r ; i ; i -= lowbit( i ) ) rec += a[ i ] ;
for ( int i = l - 1 ; i ; i -= lowbit( i ) ) rec -= a[ i ] ;
return rec ;
}
} bit ;

int ans[ MAXN ] ;

void Dfs( int t ) {
bit.Add( in[ t ] , 1 ) ;
for ( qtype *p = fro[ t ] ; p ; p = p -> next )
ans[ p -> r ] = bit.Sum( in[ p -> x ] , out[ p -> x ] ) ;
for ( int i = 0 ; i < 26 ; i ++ ) if ( v[ t ].child[ i ] ) {
Dfs( v[ t ].child[ i ] ) ;
}
bit.Add( out[ t ] , - 1 ) ;
}

void Solve( ) {
bit.Init( Index ) ;
Dfs( 0 ) ;
}

int main( ) {
Make_trie( ) ;
Make_fail( ) ;
Fail_tree( ) ;
Init_query( ) ;
Solve( ) ;
for ( int i = 0 ; i ++ < m ; ) putint( ans[ i ] ) ;
return 0 ;
}

题解

7 条题解

阿狸的打字机

信息

状态

开发

支持

题解

7 条题解

阿狸的打字机

信息

状态

开发

支持

还没有账户？

登录