{"id":271,"date":"2010-06-02T16:40:00","date_gmt":"2010-06-02T08:40:00","guid":{"rendered":"http:\/\/localhost\/?p=271"},"modified":"2010-06-02T16:40:00","modified_gmt":"2010-06-02T08:40:00","slug":"sgu_505_prefixes_and_suffixes","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=271","title":{"rendered":"SGU 505. Prefixes and suffixes"},"content":{"rendered":"\n

\u5c31\u662f\u7ed9\u4f60\u4e00\u5927\u5806\u5b57\u7b26\u4e32\uff0c\u7136\u540e\u6bcf\u6b21\u8be2\u95ee\u4ee5\u4e00\u4e2a\u7ed9\u5b9a\u4e32\u4e3a\u524d\u7f00\uff0c
\u4e00\u4e2a\u7ed9\u5b9a\u4e32\u4e3a\u540e\u7f00\u7684\u5b57\u7b26\u4e32\u6709\u51e0\u4e2a\uff1f
\u6211\u662f\u4e00\u76f4\u6ca1\u6709\u601d\u8def\u7684\uff0c\u4f46\u662f\u5728\u505a\u51fa\u7f51\u6613\u6bd4\u8d5b\u7684\u62ff\u5230\u6709\u9053\u641c\u7d22\u6846\u4e4b\u540e
\u6211\u5c31\u5df2\u7ecf\u77e5\u9053\u7b97\u6cd5\u4e86\u3002\u3002\u4f46\u662f
\u4e00\u76f4WA\uff0c\u4eca\u5929\u624d\u53d1\u73b0\u662f\u72af\u4e86\u4e2aSB\u9519\u8bef\u56e7\u554a\u3002\u3002\u3002
\u662f\u8fd9\u6837\u7684\uff0c\u5c06\u6240\u6709\u5b57\u7b26\u4e32\u6392\u5e8f\uff0c\u7531\u90a3\u9898\u6211\u660e\u767d\u4e86\u6240\u6709\u7531\u67d0\u4e2a\u524d\u7f00\u7684\u5b57\u7b26\u4e32\u662f\u4e00\u4e2a\u533a\u95f4\uff0c
\u7136\u540e\u5c06\u6240\u6709\u5b57\u7b26\u4e32
\u5168\u90e8\u53cd\u8fc7\u6765\u6392\u5e8f\uff0c\u90a3\u4e48\u7531\u67d0\u4e2a\u540e\u7f00\u7684\u5b57\u7b26\u4e32\u4e5f\u662f\u4e00\u4e2a\u533a\u95f4\uff0c\u628a\u8fd9\u4e9b\u5b57\u7b26\u4e32\u90fd\u6807\u4e0a\u5176\u5728
\u7b2c\u4e00\u904d\u6392\u5e8f\u4e2d\u7684\u6392\u540d\u3002\u3002\u90a3\u4e48\u95ee\u9898\u5c31\u6210\u4e86\uff0c\u5728[a,b]\u4e2d\uff0c[l,r]\u4e4b\u95f4\u7684\u6570\u6709\u51e0\u4e2a\u3002\u3002
\u90a3\u4e48\u7531\u4e24\u79cd\u529e\u6cd5\uff0c\u4e00\u79cd\u662f\u5728\u7ebf\u7b97\u6cd5\uff0c\u5c31\u662f\u5efa\u4e2a\u7ebf\u6bb5\u6811\uff0c\u90a3\u4e48\u662fLogN^2\u7684\u3002\u3002
\u53e6\u4e00\u79cd\u5c31\u662f\u79bb\u7ebf\u7b97\u6cd5\uff0c\u53ea\u9700\u8981\u4e00\u4e2a\u6811\u72b6\u6570\u7ec4\u5c31OK\u4e86\u3002\u3002\u3002
\u9274\u4e8e\u7b2c\u4e00\u4e2a\u53ef\u80fdTLE\u3002\u3002\u6240\u4ee5\u6211\u7528\u4e86\u79bb\u7ebf\u7b97\u6cd5\u3002\u3002\u7f16\u5199\u4e0a\u9700\u8981\u6ce8\u610f\u4e00\u4e9b\u4e1c\u897f\u3002\u3002
\u6211\u53d1\u73b0\u5173\u4e8estring\u7684\u8bdd\uff0ccin\u8fd8\u662f\u86ee\u5feb\u7684\u3002\u3002
Code:
include<string><\/strong>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#define pb push_back
#define Rep(i,n) for(int i=0;i<n;i++)
#define All(x) x.begin(),x.end()
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
using namespace std;
const int maxn=100000,maxm=100000;
string S[maxn],R[maxn];
int n,m,Ans[maxm]={},A[maxn];
struct Data
{
    int l,r,num,d;
    Data(int _l,int _r,int _num,int _d):l(_l),r(_r),num(_num),d(_d){}
};
vector<Data> E[maxn];
bool AsPrefix(const string&str,const string&prefix)
{
    if(str.size()<prefix.size()||str.substr(0,prefix.size())!=prefix)
        return false;
    return true;
}
void get(string S[maxn],string pre,int&l,int&r)
{
    l=lower_bound(S,S+n,pre)-S;
    pre[pre.size()-1]++;
    r=lower_bound(S,S+n,pre)-S;
}
struct TreeArray
{
    int H[maxn+10];
    TreeArray(){memset(H,0,sizeof(H));}
    void Add(int l,int d)
    {
        l++;
        for(;l<=n;l+=(l&-l))
            H[l]+=d;
    }
    int operator[](int l)
    {
        l++;int ret=0;
        for(;l>0;l-=(l&-l))
            ret+=H[l];
        return ret;
    }
}T;
int main()
{
    \/\/freopen("in","r",stdin);
    cin>>n;Rep(i,n)cin>>S[i],R[i]=S[i],reverse(All(R[i]));
    sort(S,S+n);sort(R,R+n);
    Rep(i,n)
    {
        string tmp=R[i];reverse(All(tmp));
        A[i]=lower_bound(S,S+n,tmp)-S;
    }
    cin>>m;string Pre,Suf;
    Rep(i,m)
    {
        cin>>Pre>>Suf;
        int l,r,a,b;
        get(S,Pre,l,r);
        if(l==r)continue;
        reverse(All(Suf));
        get(R,Suf,a,b);
        if(a==b)continue;
        E[b-1].pb(Data(l,r-1,i,1));
        if(a)E[a-1].pb(Data(l,r-1,i,-1));
    }
    Rep(i,n)
    {
        T.Add(A[i],1);
        tr(e,E[i])Ans[e->num]+=(T[e->r]-T[e->l-1])*e->d;
    }
    Rep(i,m)printf("%dn",Ans[i]);
}<\/p>\n","protected":false},"excerpt":{"rendered":"

\u5c31\u662f\u7ed9\u4f60\u4e00\u5927\u5806\u5b57\u7b26\u4e32\uff0c\u7136\u540e\u6bcf\u6b21\u8be2\u95ee\u4ee5\u4e00\u4e2a\u7ed9\u5b9a\u4e32\u4e3a\u524d\u7f00\uff0c\u4e00\u4e2a\u7ed9\u5b9a\u4e32\u4e3a\u540e\u7f00\u7684\u5b57\u7b26\u4e32\u6709\u51e0\u4e2a\uff1f\u6211\u662f\u4e00\u76f4\u6ca1\u6709\u601d\u8def\u7684\uff0c\u4f46\u662f\u5728\u505a\u51fa\u7f51\u6613\u6bd4\u8d5b\u7684\u62ff\u5230\u6709\u9053\u641c\u7d22\u6846\u4e4b\u540e\u6211\u5c31\u5df2\u7ecf\u77e5\u9053\u7b97\u6cd5\u4e86\u3002\u3002\u4f46\u662f\u4e00\u76f4WA\uff0c\u4eca\u5929\u624d\u53d1\u73b0\u662f\u72af\u4e86\u4e2aSB\u9519\u8bef\u56e7\u554a\u3002\u3002\u3002\u662f\u8fd9\u6837\u7684\uff0c\u5c06\u6240\u6709\u5b57\u7b26\u4e32\u6392\u5e8f\uff0c\u7531\u90a3\u9898\u6211\u660e\u767d\u4e86\u6240\u6709\u7531\u67d0\u4e2a\u524d\u7f00\u7684\u5b57\u7b26\u4e32\u662f\u4e00\u4e2a\u533a\u95f4\uff0c\u7136\u540e\u5c06\u6240\u6709\u5b57\u7b26\u4e32\u5168\u90e8\u53cd\u8fc7\u6765\u6392\u5e8f\uff0c\u90a3\u4e48\u7531\u67d0\u4e2a\u540e\u7f00\u7684\u5b57\u7b26\u4e32\u4e5f\u662f\u4e00\u4e2a\u533a\u95f4\uff0c\u628a\u8fd9\u4e9b\u5b57\u7b26\u4e32\u90fd\u6807\u4e0a\u5176\u5728\u7b2c\u4e00\u904d\u6392\u5e8f\u4e2d\u7684\u6392\u540d\u3002\u3002\u90a3\u4e48\u95ee\u9898\u5c31\u6210\u4e86\uff0c\u5728[a,b]\u4e2d\uff0c[l,r]\u4e4b\u95f4\u7684\u6570\u6709\u51e0\u4e2a\u3002\u3002\u90a3\u4e48\u7531\u4e24\u79cd\u529e\u6cd5\uff0c\u4e00\u79cd\u662f\u5728\u7ebf\u7b97\u6cd5\uff0c\u5c31\u662f\u5efa\u4e2a\u7ebf\u6bb5\u6811\uff0c\u90a3\u4e48\u662fLogN^2\u7684\u3002\u3002\u53e6\u4e00\u79cd\u5c31\u662f\u79bb\u7ebf\u7b97\u6cd5\uff0c\u53ea\u9700\u8981\u4e00\u4e2a\u6811\u72b6\u6570\u7ec4\u5c31OK\u4e86\u3002\u3002\u3002\u9274\u4e8e\u7b2c\u4e00\u4e2a\u53ef\u80fdTLE\u3002\u3002\u6240\u4ee5\u6211\u7528\u4e86\u79bb\u7ebf\u7b97\u6cd5\u3002\u3002\u7f16\u5199\u4e0a\u9700\u8981\u6ce8\u610f\u4e00\u4e9b\u4e1c\u897f\u3002\u3002\u6211\u53d1\u73b0\u5173\u4e8estring\u7684\u8bdd\uff0ccin\u8fd8\u662f\u86ee\u5feb\u7684\u3002\u3002Code:include<string>#include<algorithm>#include<iostream>#include<vector>#include<cstring>#include<cstdio>#define pb push_back#define Rep(i,n) for(int i=0;i<n;i++)#define All(x) x.begin(),x.end()#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)using namespace std;const int maxn=100000,maxm=100000;string S[maxn],R[maxn];int n,m,Ans[maxm]={},A[maxn];struct Data{    int l,r,num,d;    Data(int _l,int _r,int _num,int _d):l(_l),r(_r),num(_num),d(_d){}};vector<Data> E[maxn];bool AsPrefix(const string&str,const string&prefix){    if(str.size()<prefix.size()||str.substr(0,prefix.size())!=prefix)        return false;    return true;}void get(string S[maxn],string pre,int&l,int&r){    l=lower_bound(S,S+n,pre)-S;    pre[pre.size()-1]++;    r=lower_bound(S,S+n,pre)-S;}struct TreeArray{    int H[maxn+10];    TreeArray(){memset(H,0,sizeof(H));}    void Add(int l,int d)    {        l++;        for(;l<=n;l+=(l&-l))            H[l]+=d;    }    int operator[](int […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/271"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=271"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/271\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=271"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=271"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=271"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}