Brief description :

给定 n 个字符串，询问其中以给定串为前缀，给定串为后缀的字串数目，询问有 m 个。
（ n, m <= 100000 )

Analysis :

分别对原和和逆串进行排序，则原题等价为给定一个排列，查询下标在 [l, r] 之间，项 [a, b] 之间的数目。
离线树状数组可做。

const int N = 100009;

string S[N], R[N];
int A[N], ans[N], n, m;

struct BIT{
    int C[N];
    BIT(){RST(C);}
    void modify(int x){++x; do ++C[x], x += low_bit(x); while (x <= n);}
    int operator[](int x){++x; int s = 0; do s += C[x], x -= low_bit(x); while(x); return s;}
} T;

struct Event{
    int l, r, d, id;
    Event(int _l, int _r, int _d, int _id):l(_l), r(_r), d(_d), id(_id){}
    void process(){ans[id] += (T[r] - T[l]) * d;}
};

vector<Event> E[N];

void locate(string S[], string x, int &l, int &r){
    l = lower_bound(S, S + n, x) - S - 1, ++x[SZ(x)-1];
    r = lower_bound(S, S + n, x) - S - 1;
}

int main(){

    //freopen("in.txt", "r", stdin);

    REP_C(i, _RD(n)){
        cin >> S[i], R[i] = S[i], reverse(ALL(R[i]));
    }

    sort(S, S + n), sort(R, R + n);

    REP(i, n){
        string t = S[i]; reverse(ALL(t));
        A[i] = lower_bound(R, R + n, t) - R;
    }

    string pre, suf; int l, r, a, b;
    REP_C(i, _RD(m)){
        cin >> pre >> suf; locate(S, pre, l, r); if (l == r) continue;
        reverse(ALL(suf)); locate(R, suf, a, b); if (a == b) continue;
        E[r].PB(Event(a, b, 1, i));
        if (l >= 0) E[l].PB(Event(a, b, -1, i));
    }

    REP(i, n){
        T.modify(A[i]); ECH(it, E[i]) it->process();
    }

    REP(i, m) OT(ans[i]);
}

External link:

http://acm.sgu.ru/problem.php?contest=0&problem=505

Posted by xiaodao
Category: 日常