Tác giả: skyvn97

https://www.youtube.com/live/fL4OzpDDCG8?si=rrpj2HSpsNp8OfGk

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define fi   first
#define se   second
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X,class Y>
    void minimize(X &x,const Y &y) {
        if (x>y) x=y;
    }
template<class X,class Y>
    void maximize(X &x,const Y &y) {
        if (x<y) x=y;
    }
template<class T>
    T Abs(const T &x) {
        return (x<0?-x:x);
    }

/* Author: Van Hanh Pham */

/** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/

class FenwickTree {
private:
    int n;
    vector<int> v;

public:
    FenwickTree(int n = 0) {
        this->n = n;
        v.assign(n + 7, 0);
    }

    void update(int x, int d) {
        if (x == 0) return;
        for (; x <= n; x += x & -x) v[x] += d;
    }

    int get(int x) const {
        int res = 0;
        for (; x >= 1; x &= x - 1) res += v[x];
        return res;
    }

    int getSum(int l, int r) const {
        return l == 1 ? get(r) : get(r) - get(l - 1);
    }
};

struct Node {
    Node *child[26];
    int last;

    Node() {
        REP(i, 26) child[i] = nullptr;
        last = 0;
    }
};
#define MAX_NODE   1111111
Node nodes[MAX_NODE];
int cntNode;
Node *createNode(void) {
    return &nodes[cntNode++];
}

#define MAX_SIZE   300300
int numWord, numQuery;
string words[MAX_SIZE];
Node *prefixRoot, *suffixRoot;
vector<pair<int, int>> queryAt[MAX_SIZE];
long long answer[MAX_SIZE];

void init(void) {
    cin >> numWord >> numQuery;
    FOR(i, 1, numWord) cin >> words[i];
    FOR(i, 1, numQuery) {
        int l, r; cin >> l >> r;
        queryAt[r].push_back(make_pair(l, i));
    }
}

void addString(Node *root, const string &s) {
    Node *p = root;

    FORE(it, s) {
        if (p->child[*it - 'a'] == nullptr) p->child[*it - 'a'] = createNode();
        p = p->child[*it - 'a'];
    }
}

void prepare(void) {
    prefixRoot = createNode();
    suffixRoot = createNode();

    FOR(i, 1, numWord) {
        addString(prefixRoot, words[i]);
        reverse(ALL(words[i]));
        addString(suffixRoot, words[i]);
        reverse(ALL(words[i]));
    }
}

void process(void) {
    FenwickTree prefixBit[26], suffixBit[26], allSuffixBit;

    REP(i, 26) {
        prefixBit[i] = FenwickTree(numWord);
        suffixBit[i] = FenwickTree(numWord);
    }
    allSuffixBit = FenwickTree(numWord);

    FOR(i, 1, numWord) {
        Node *p = prefixRoot;
        FORE(it, words[i]) {
            p = p->child[*it - 'a'];
            if (it != words[i].begin()) prefixBit[*it - 'a'].update(p->last, -1);
            p->last = i;
            if (it != words[i].begin()) prefixBit[*it - 'a'].update(p->last, 1);
        }

        reverse(ALL(words[i]));

        p = suffixRoot;
        FORE(it, words[i]) {
            p = p->child[*it - 'a'];
            allSuffixBit.update(p->last, -1);
            if (it != words[i].begin()) suffixBit[*it - 'a'].update(p->last, -1);
            p->last = i;
            allSuffixBit.update(p->last, 1);
            if (it != words[i].begin()) suffixBit[*it - 'a'].update(p->last, 1);
        }

        reverse(ALL(words[i]));

        FORE(jt, queryAt[i]) {
            int l = jt->fi, r = i, id = jt->se;
            REP(k, 26) {
                if (prefixRoot->child[k] != nullptr && prefixRoot->child[k]->last >= l)
                    answer[id] += allSuffixBit.getSum(l, r);
                int numPre = prefixBit[k].getSum(l, r);
                int numSuf = allSuffixBit.getSum(l, r) - suffixBit[k].getSum(l, r);
                answer[id] += 1LL * numPre * numSuf;
            }
        }
    }

    FOR(i, 1, numQuery) cout << answer[i] << "\n";
}

int main(void) {
#ifdef ONLINE_JUDGE
    freopen("preandsuf.inp", "r", stdin);
    freopen("preandsuf.out", "w", stdout);
#endif // ONLINE_JUDGE

    init();
    prepare();
    process();
    return 0;
}

/*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/