2434: [Noi2011]阿狸的打字机 - BZOJ

By | 06月26日
Advertisement

Description

阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和'B'、'P'两个字母。

经阿狸研究发现,这个打字机是这样工作的:

l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

l 按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。

l 按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。

例如,阿狸输入aPaPBbP,纸上被打印的字符如下:

a

aa

ab

我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?
Input

输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m,表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为(x, y)。
Output

输出m行,其中第i行包含一个整数,表示第i个询问的答案。
Sample Input
aPaPBbP

3

1 2

1 3

2 3

Sample Output
2

1

0
HINT

1<=N<=10^5

1<=M<=10^5

输入总长<=10^5

首先我们建出ac自动机,然后对于一组询问(x,y)就是从根到y字符串这条路径有多少点可以通过fail走到x节点,然后fail反向建出来的是一棵树(就叫fail树算了)

于是一组询问(x,y)就是从根到y字符串这条路径有多少点在x节点的子树中,于是我们处理出dfs序,我们就只要维护区间和就行了

对于多组询问我们就离线处理,按照他打字机的顺序遍历点,小写字母就在他的dfs序上+1,B就在现在这个节点的dfs序上-1,走到x单词的结束节点时处理询问(i,x)

2434: [Noi2011]阿狸的打字机 - BZOJ
2434: [Noi2011]阿狸的打字机 - BZOJ

  1 const
  2     maxn=100100;
  3 type
  4     node=record
  5         x,y,id:longint;
  6     end;
  7 var
  8     go:array[0..maxn,'a'..'z']of longint;
  9     q:array[0..maxn]of node;
 10     ch:array[0..maxn]of char;
 11     e,p,fa,ll,rr,ans,fail,first,last,next,bit:array[0..maxn]of longint;
 12     n,cnt,tot,now,sum:longint;
 13     s:ansistring;
 14
 15 procedure insert(x,y:longint);
 16 begin
 17     inc(tot);
 18     last[tot]:=y;
 19     next[tot]:=first[x];
 20     first[x]:=tot;
 21 end;
 22
 23 function nexts(x:longint;c:char):longint;
 24 begin
 25     if go[x,c]=0 then
 26     begin
 27         inc(cnt);go[x,c]:=cnt;
 28         fa[cnt]:=x;ch[cnt]:=c;
 29     end;
 30     exit(go[x,c]);
 31 end;
 32
 33 procedure swap(var x,y:node);
 34 var
 35     t:node;
 36 begin
 37     t:=x;x:=y;y:=t;
 38 end;
 39
 40 procedure sort(l,r:longint);
 41 var
 42     i,j,y:longint;
 43 begin
 44     i:=l;j:=r;y:=q[(l+r)>>1].x;
 45     repeat
 46         while q[i].x<y do inc(i);
 47         while q[j].x>y do dec(j);
 48         if i<=j then
 49         begin
 50             swap(q[i],q[j]);
 51             inc(i);dec(j);
 52         end;
 53     until i>j;
 54     if i<r then sort(i,r);
 55     if j>l then sort(l,j);
 56 end;
 57
 58 procedure dfs(x:longint);
 59 var
 60     i:longint;
 61 begin
 62     inc(sum);ll[x]:=sum;
 63     i:=first[x];
 64     while i<>0 do
 65         begin
 66             dfs(last[i]);
 67             i:=next[i];
 68         end;
 69     rr[x]:=sum;
 70 end;
 71
 72 var
 73     que:array[0..maxn]of longint;
 74     l,r:longint;
 75
 76 procedure bfs;
 77 var
 78     i,j:longint;
 79     c:char;
 80 begin
 81     que[1]:=0;l:=0;r:=0;
 82     while l<=r do
 83         begin
 84             for c:='a' to 'z' do
 85                 if go[que[l],c]>0 then
 86                 begin
 87                     inc(r);
 88                     que[r]:=go[que[l],c];
 89                 end;
 90             inc(l);
 91         end;
 92     for i:=1 to cnt do
 93         begin
 94             j:=que[i];c:=ch[j];j:=fail[fa[j]];
 95             while (j<>0) and (go[j,c]=0) do
 96                 j:=fail[j];
 97             fail[que[i]]:=go[j,c];
 98             if fail[que[i]]=que[i] then fail[que[i]]:=0;
 99             insert(fail[que[i]],que[i]);
100         end;
101 end;
102
103 function get(x:longint):longint;
104 begin
105     get:=0;
106     while x>0 do
107         begin
108             inc(get,bit[x]);
109             x:=x-(x and (-x));
110         end;
111 end;
112
113 procedure add(x,y:longint);
114 begin
115     while x<=sum do
116         begin
117             inc(bit[x],y);
118             x:=x+(x and (-x));
119         end;
120 end;
121
122 procedure main;
123 var
124     i,j:longint;
125 begin
126     readln(s);now:=0;
127     for i:=1 to length(s) do
128         begin
129             if s[i]='P' then
130                 begin
131                     inc(n);
132                     e[n]:=i;
133                     p[n]:=now;
134                 end
135             else
136                 if s[i]='B' then now:=fa[now]
137                 else now:=nexts(now,s[i]);
138         end;
139     bfs;
140     dfs(0);
141     read(n);
142     for i:=1 to n do
143         read(q[i].y,q[i].x);
144     for i:=1 to n do q[i].id:=i;
145     sort(1,n);
146     j:=0;now:=0;
147     for i:=1 to n do
148         begin
149             while j<e[q[i].x] do
150                 begin
151                     inc(j);
152                     if s[j]='B' then
153                         begin
154                             add(ll[now],-1);
155                             now:=fa[now];
156                         end
157                     else
158                         if s[j]<>'P' then
159                         begin
160                             now:=nexts(now,s[j]);
161                             add(ll[now],1);
162                         end;
163                 end;
164             ans[q[i].id]:=get(rr[p[q[i].y]])-get(ll[p[q[i].y]]-1);
165         end;
166     for i:=1 to n do writeln(ans[i]);
167 end;
168
169 begin
170     main;
171 end.

View Code

Similar Posts:

  • BZOJ 2434([Noi2011]阿狸的打字机-AC自动机-Fail树)

    2434: [Noi2011]阿狸的打字机 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 544  Solved: 300 [Submit][Status][Discuss] Description 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机.打字机上只有28个按键,分别印有26个小写英文字母和'B'.'P'两个字母. 经阿狸研究发现,这个打字机是这样工作的: l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽

  • ★【AC自动机】【树状数组】【NOI2011】阿狸的打字机

    [问题描述] 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机.打字机 上只有 28 个按键,分别印有 26 个小写英文字母和'B'.'P'两个字母. 经阿狸研究发现,这个打字机是这样工作的: 输入小写字母,打字机的一个凹槽中会加入这个字母(按 P 前凹槽中至少有一个字母). 按一下印有'B'的按键,打字机凹槽中最后一个字母会消失. 按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失(保证凹槽中至少有一个字母) 例如,阿狸输入 aPaPBbP

  • [置顶] 给自己挖个坑

    :>_ < ?好多坑,感觉要炸了 :首次填坑 BZOJ 2434 阿狸的打字机 BZOJ 2553 禁忌 BZOJ 1100 对称轴osi BZOJ 3676: [Apio2014]回文串 BZOJ 2342: [Shoi2011]双倍回文 BZOJ 2565: 最长双回文串 BZOJ 3790: 神奇项链 OI 课题 预流推进 OI 课题 平衡树 POJ 3764 BZOJ 等差子序列 OI 课题 树的分治 BZOJ 1503 WA √填了 BZOJ 3224 splay

  • bzoj 2435: [Noi2011]道路修建 乱搞/水题

    Description 在 W 星球上有 n 个国家.为了各自国家的经济发展,他们决定在各个国家 之间建设双向道路使得国家之间连通.但是每个国家的国王都很吝啬,他们只愿 意修建恰好 n – 1条双向道路. 每条道路的修建都要付出一定的费用, 这个费用等于道路长度乘以道路两端的国家个数之差的绝对值.例如,在下图中,虚线所示道路两端分别有 2 个.4个国家,如果该道路长度为 1,则费用为1×|2 – 4|=2.图中圆圈里的数字表示国家的编号. 由于国家的数量十分庞大,道路的建造方案有很多种,同时每种

  • 【BZOJ】3319: 黑白树(并查集+特殊的技巧/-树链剖分+线段树)

    http://www.lydsy.com/JudgeOnline/problem.php?id=3319 以为是模板题就复习了下hld............................. 然后nlg^2n被tle成翔了.............................. 然后看题解QAQ,,,这... 神题做法...待会再写...(upd:[BZOJ]3319: 黑白树) tle的hld: #include <cstdio> #include <cstring> #i

  • 【BZOJ】3224: Tyvj 1728 普通平衡树(某不科学的oj)

    http://www.lydsy.com/JudgeOnline/problem.php?id=3224 无力吐槽,无力吐槽,无力吐槽....... bzoj竟然不能用time(0)我竟然不造!!re成一片..... (不管re没re,我也在我程序中找到了很多bug,,,一一修复了..我的treap写的真渣. 这次我发现了treap的很多问题,有一个细节的地方.就是null的weight必须要最大(或最小),你的堆是最小(或最大)的话,所以要将null的weight的初值设置一下,否则在删除操作

  • BZOJ 1052 [HAOI2007] 覆盖问题(DFS)

    题目大意 某人在山上种了 N 棵小树苗.冬天来了,温度急速下降,小树苗脆弱得不堪一击,于是树主人想用一些塑料薄膜把这些小树遮盖起来,经过一番长久的思考,他决定用 3 个 L*L 的正方形塑料薄膜将小树遮起来.我们不妨将山建立一个平面直角坐标系,设第i棵小树的坐标为 (Xi,Yi),3 个 L*L 的正方形的边要求平行于坐标轴,一个点如果在正方形的边界上,也算作被覆盖.当然,我们希望塑料薄膜面积越小越好,即求 L 最小值. 数据范围 100%的数据,-1,000,000,000<=Xi,Yi<=

  • 阿狸图标应用模板

    #####阿狸图标应用 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</title> <link rel="stylesheet" href="http://at.alicdn.com/t/font_1448520818_301091.css&quo

  • 【BZOJ】【4144】【AMPPZ2014】Petrol

    最短路+最小生成树+倍增 图论问题中综合性较强的一题= =(Orz vfk) 比较容易发现,关键的还是有加油站的这些点,其他点都是打酱油的. 也就是说我们重点是要求出 关键点之间的最短路. 这玩意--如果枚举加油站所在的点,然后跑单源最短路什么的--肯定TLE啊. 我们记from[i]表示离 i 最近的关键点,仔细考虑一下,A->B的最短路径上,一定是前一半的from[i]为A,然后走过某条路以后,后一半的from[i]为B.为什么呢?我们不妨设中间出现了一个点x的from[x]=C,那么我们大

  • 【BZOJ】【3697】采药人的路径&amp;【3127】【USACO2013 Open】Yin and Yang

    点分治 Orz hzwer 倒是比较好想到点分治--然而在方案统计这里,我犯了两个错误-- 1.我比较傻逼的想的是:通过儿子来更新父亲,也就是统计以x为根的子树中xxxx的路径有多少条--这样转移. 然而这实在是太傻逼了,黄学长教做人:从父亲来更新儿子,走到一个节点直接更新路径的统计数,反正我们要的是[经过root的xx路径的数量] 所以可以一遍dfs直接搞出来-- 2.统计方案的方式也想错了--我只考虑了以root作为中转站的路径,然而经过root的路径中,并不只有这种路径是合法的--中转站在

Tags: