首页分享 JZOJ 3887. 【长郡NOIP2014模拟10.22】字符串查询

JZOJ 3887. 【长郡NOIP2014模拟10.22】字符串查询

来源：花匠小妙招时间：2024-09-10 15:43

题目

Description
给定n个字符串和q个询问
每次询问在这n个字符串中，有多少个字符串同时满足
1. 字符串a是它的前缀
2. 字符串b是它的后缀
Input
第一行两个数n，q ，表示给定字符串数和询问数
接下来n行每行一个字符串
再接下来q组询问，每组询问2行，分别表示两个字符串a，b，意义上述
Output
q行每行一个数，表示有多少个字符串满足条件
Sample Input
4 2
abc
bac
ac
acc
a
c
ba
ac
Sample Output
3
1
Data Constraint
100%数据满足n，q≤50000，字符串长度丌超过100，任意两串最长公共前缀较短
字符串全部由小写字母a到j组成，行末保证没有多余字符，没有多余的空行，没有空串

题解

我们可以慢慢地观察到，以某个串为前缀的所有字符串一定是连续的一段，后缀同理。
所以现在我们我们有一个字符串a。
先将所有字符串按照前缀排个序，那么设a的排名为x，再将所有字符串按照后缀排个序，那么设a的排名为y。
那么对于一个询问，就是求在前缀中的合法的区间[l1,r1]" role="presentation">[l1,r1]和在后缀中的合法的区间[l2,r2]" role="presentation">[l2,r2]。通过二维偏序统计，将询问按照[l1,r1]" role="presentation">[l1,r1]排序，把第i个字符串的后缀排名wz[i]" role="presentation">wz[i]放入树状数组中。然后扫到l1−1" role="presentation">l1−1的位置时减去从树状数组中搜索的值，扫到r1" role="presentation">r1的位置时加上从树状数组中搜索的值。

代码

var qu:array[0..50003,0..4] of longint; a,b:array[0..50003] of string; ns,c,wz,o,head,ans:array[0..50003] of longint; go,next,l,r,xs:array[0..100003] of longint; tot,tot1,i,j,n,m:longint; a1,b1,c1:string; procedure lb(x,y,l2,r2,xishu:longint); begin inc(tot); go[tot]:=y; next[tot]:=head[x]; head[x]:=tot; l[tot]:=l2; r[tot]:=r2; xs[tot]:=xishu; end; function cmp(x,y:string):longint; var i,fy:longint; begin fy:=length(y); for i:=1 to fy do if (x[i]>y[i]) then exit(2) else if (x[i]<y[i]) then exit(1); exit(0); end; function lowbit(x:longint):longint; begin exit(x and (-x)); end; procedure add(k:longint); begin while (k<=n) do begin inc(c[k]); k:=k+lowbit(k); end; end; function find(k:longint):longint; var sum:longint; begin sum:=0; while (k>0) do begin inc(sum,c[k]); k:=k-lowbit(k); end; exit(sum); end; procedure qsort(l,r:longint); var i,j:longint; mid,t:string; begin i:=l; j:=r; mid:=a[(l+r) div 2]; while (i<j) do begin while (a[i]<mid) do inc(i); while (a[j]>mid) do dec(j); if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; inc(i);dec(j); end; end; if (l<j) then qsort(l,j); if (i<r) then qsort(i,r); end; procedure qsor1(l,r:longint); var i,j,t1:longint; mid,t:string; begin i:=l; j:=r; mid:=b[(l+r) div 2]; while (i<j) do begin while (b[i]<mid) do inc(i); while (b[j]>mid) do dec(j); if i<=j then begin t:=b[i];b[i]:=b[j];b[j]:=t; t1:=wz[i];wz[i]:=wz[j];wz[j]:=t1; inc(i);dec(j); end; end; if (l<j) then qsor1(l,j); if (i<r) then qsor1(i,r); end; function ef(op:longint):longint; var i,j,l,r,mid:longint; begin ef:=0; l:=1; r:=n; repeat mid:=(l+r)div 2; case op of 0:begin if (cmp(a[mid],a1)=1) then begin ef:=mid; l:=mid+1; end else r:=mid-1; end; 1:begin if (cmp(a[mid],a1)<2) then begin ef:=mid; l:=mid+1; end else r:=mid-1; end; 2:begin if (cmp(b[mid],b1)=1) then begin ef:=mid; l:=mid+1; end else r:=mid-1; end; 3:begin if (cmp(b[mid],b1)<2) then begin ef:=mid; l:=mid+1; end else r:=mid-1; end; end; until l>r; end; begin readln(n,m); for i:=1 to n do readln(a[i]); qsort(1,n); for i:=1 to n do begin for j:=1 to length(a[i]) do b[i]:=a[i][j]+b[i]; a[i]:=a[i]+' '; b[i]:=b[i]+' '; wz[i]:=i; end; qsor1(1,n); for i:=1 to n do o[wz[i]]:=i; for i:=1 to m do begin readln(a1); b1:=''; readln(c1); for j:=1 to length(c1) do b1:=c1[j]+b1; qu[i,0]:=ef(0); qu[i,1]:=ef(1); qu[i,2]:=ef(2); qu[i,3]:=ef(3); qu[i,4]:=i; if (qu[i,1]>qu[i,0])and(qu[i,3]>qu[i,2]) then begin if (qu[i,0]>0) then lb(qu[i,0],i,qu[i,2],qu[i,3],-1); lb(qu[i,1],i,qu[i,2],qu[i,3],1); end; end; for i:=1 to n do begin add(o[i]); j:=head[i]; while (j<>0) do begin ans[go[j]]:=ans[go[j]]+(find(r[j])-find(l[j]))*xs[j]; j:=next[j]; end; end; for i:=1 to m do writeln(ans[i]); end.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173