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

本文主要是介绍【长郡NOIP2014模拟10.22】字符串查询，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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
【友情提示】
字符串全部由小写字母a到j组成，行末保证没有多余字符，没有多余的空行，没有空串

Data Constraint

30%数据满足n，q≤1000
另有30%数据满足n，q≤50000，所有询问中a，b串长度丌超过2
100%数据满足n，q≤50000，字符串长度丌超过100，任意两串最长公共前缀较短

Solution

时限很大，意思就是让你排序的
怕被卡的话就把它压成十进制数然后排序（字母只有a~j共10个）
按照前缀和后缀分别排序，那么每个字符串都有前缀的名次x和后缀的名次y
把每个字符串想象成一个点(x,y)
那么询问时的前缀就一定是一个连续的区间[l,r]
同理，后缀也是连续的区间[a,b]
这里的a,b,l,r都可以用二分求出，也可以都加入到原序列中一起排序得出
那么变成求在这两个区间的交集中有多少个点

离线处理
对于询问，拆成两个即x为1~l区间和1~r区间，用后者-前者
从小到大排序，然后对于某个询问的z可能属于原来询问的后者或前者，判断一下就好
用树状数组维护此时（x=1-z）时y的个数，询问时调用就行了
c++排序建议用sort，二分因为我不会用upperbound之类的所以打了四个，判断大小也打了四个……

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 101000
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,q,ans[N],e[N*2],bz[N];
struct note{char a[110];int n,z;
}s[N],t[N];struct node{int x,y,z,r;
}c[N],b[N];bool cnt(node x,node y){return x.x<y.x;}
bool cmt(note x,note y)
{fo(i,1,min(x.n,y.n)){if(x.a[i]<y.a[i]) return 1;if(x.a[i]>y.a[i]) return 0;}if(x.n<y.n) return 1;else return 0;
}
bool cmt2(note x,note y)
{fo(i,1,min(x.n,y.n)){if(x.a[x.n-i+1]<y.a[y.n-i+1]) return 1;if(x.a[x.n-i+1]>y.a[y.n-i+1]) return 0;}if(x.n<y.n) return 1;else return 0;
}
bool same(note x,note y)
{fo(i,1,y.n)if(x.a[i]!=y.a[i]) return 0;return 1;
}
bool same1(note x,note y)
{fo(i,1,y.n)if(x.a[x.n-i+1]!=y.a[y.n-i+1]) return 0;return 1;
}
bool cnt1(note x,note y)
{fo(i,1,x.n) {if(x.a[i]<y.a[i]) return 1;if(x.a[i]>y.a[i]) return 0;}return 1;
}
bool cnt2(note x,note y)
{fo(i,1,x.n) {if(x.a[i]>y.a[i]) return 1;if(x.a[i]<y.a[i]) return 0;}return 1;
}
bool cnt3(note x,note y)
{fo(i,1,x.n) {if(x.a[x.n-i+1]<y.a[y.n-i+1]) return 1;if(x.a[x.n-i+1]>y.a[y.n-i+1]) return 0;}return 1;
}
bool cnt4(note x,note y)
{fo(i,1,x.n) {if(x.a[x.n-i+1]>y.a[y.n-i+1]) return 1;if(x.a[x.n-i+1]<y.a[y.n-i+1]) return 0;}return 1;
}
int ef1(int l,int r,note z)
{while(l+1<r){int m=(l+r)/2;if(cnt1(z,s[m])) r=m;else l=m;}if(same(s[l],z)) r=l;return r;
}
int ef2(int l,int r,note z)
{while(l+1<r){int m=(l+r)/2;if(cnt3(z,t[m])) r=m;else l=m;}if(same1(t[l],z)) r=l;return r;
}
int ef3(int l,int r,note z)
{while(l+1<r){int m=(l+r)/2;if(cnt4(z,t[m])) l=m;else r=m;}if(same1(t[r],z)) l=r;return l;
}
int ef4(int l,int r,note z)
{while(l+1<r){int m=(l+r)/2;if(cnt2(z,s[m])) l=m;else r=m;}if(same(s[r],z)) l=r;return l;
}
int lowbit(int x){return x&(-x);}
void insert(int x)
{for(;x<=n;x+=lowbit(x)) e[x]++;
}
int get(int x)
{int an=0;for(;x;x-=lowbit(x)) an+=e[x];return an;
}
int main()
{scanf("%d%d\n",&n,&q);fo(i,1,n) scanf("%s\n",s[i].a+1),s[i].n=strlen(s[i].a+1),s[i].z=i,t[i]=s[i];sort(s+1,s+n+1,cmt);fo(i,1,n) c[s[i].z].x=i;sort(t+1,t+n+1,cmt2);fo(i,1,n) c[t[i].z].y=i;int tot=0;fo(i,1,q){note x,y;scanf("%s\n",x.a+1);scanf("%s\n",y.a+1);x.n=strlen(x.a+1),y.n=strlen(y.a+1);int jy1=ef2(1,n,y);int jy2=ef3(1,n,y);b[++tot].x=ef1(1,n,x);b[tot].y=jy1;b[tot].r=jy2;b[tot].z=i;b[++tot].x=ef4(1,n,x)+1;b[tot].y=jy1;b[tot].r=jy2;b[tot].z=i;}sort(c+1,c+n+1,cnt);sort(b+1,b+tot+1,cnt);int j=1;fo(i,1,tot){for(;c[j].x<b[i].x&&j<=n;j++) insert(c[j].y);int jy=get(b[i].r);jy -=get(b[i].y-1);if(bz[b[i].z]==0) ans[b[i].z]-=jy,bz[b[i].z]=1;else ans[b[i].z]+=jy;}fo(i,1,q) printf("%d\n",ans[i]);
}