\u7ed9\u5b9a n \u4e2a\u5b57\u7b26\u4e32\uff0c\u8be2\u95ee\u5176\u4e2d\u4ee5\u7ed9\u5b9a\u4e32\u4e3a\u524d\u7f00\uff0c\u7ed9\u5b9a\u4e32\u4e3a\u540e\u7f00\u7684\u5b57\u4e32\u6570\u76ee\uff0c\u8be2\u95ee\u6709 m \u4e2a\u3002
\n\uff08 n, m <= 100000 )\n<\/p>\n
\u5206\u522b\u5bf9\u539f\u548c\u548c\u9006\u4e32\u8fdb\u884c\u6392\u5e8f\uff0c\u5219\u539f\u9898\u7b49\u4ef7\u4e3a\u7ed9\u5b9a\u4e00\u4e2a\u6392\u5217\uff0c\u67e5\u8be2\u4e0b\u6807\u5728 [l, r] \u4e4b\u95f4\uff0c\u9879 [a, b] \u4e4b\u95f4\u7684\u6570\u76ee\u3002
\n\u79bb\u7ebf\u6811\u72b6\u6570\u7ec4\u53ef\u505a\u3002<\/p>\n
\r\nconst int N = 100009;\r\n\r\nstring S[N], R[N];\r\nint A[N], ans[N], n, m;\r\n\r\nstruct BIT{\r\n int C[N];\r\n BIT(){RST(C);}\r\n void modify(int x){++x; do ++C[x], x += low_bit(x); while (x <= n);}\r\n int operator[](int x){++x; int s = 0; do s += C[x], x -= low_bit(x); while(x); return s;}\r\n} T;\r\n\r\nstruct Event{\r\n int l, r, d, id;\r\n Event(int _l, int _r, int _d, int _id):l(_l), r(_r), d(_d), id(_id){}\r\n void process(){ans[id] += (T[r] - T[l]) * d;}\r\n};\r\n\r\nvector<Event> E[N];\r\n\r\nvoid locate(string S[], string x, int &l, int &r){\r\n l = lower_bound(S, S + n, x) - S - 1, ++x[SZ(x)-1];\r\n r = lower_bound(S, S + n, x) - S - 1;\r\n}\r\n\r\nint main(){\r\n\r\n \/\/freopen("in.txt", "r", stdin);\r\n\r\n REP_C(i, _RD(n)){\r\n cin >> S[i], R[i] = S[i], reverse(ALL(R[i]));\r\n }\r\n\r\n sort(S, S + n), sort(R, R + n);\r\n\r\n REP(i, n){\r\n string t = S[i]; reverse(ALL(t));\r\n A[i] = lower_bound(R, R + n, t) - R;\r\n }\r\n\r\n string pre, suf; int l, r, a, b;\r\n REP_C(i, _RD(m)){\r\n cin >> pre >> suf; locate(S, pre, l, r); if (l == r) continue;\r\n reverse(ALL(suf)); locate(R, suf, a, b); if (a == b) continue;\r\n E[r].PB(Event(a, b, 1, i));\r\n if (l >= 0) E[l].PB(Event(a, b, -1, i));\r\n }\r\n\r\n REP(i, n){\r\n T.modify(A[i]); ECH(it, E[i]) it->process();\r\n }\r\n\r\n REP(i, m) OT(ans[i]);\r\n}\r\n\r\n<\/pre>\nExternal link:<\/h3>\n