学习到的内容 : 初步了解并使用trie树, 初步了解了离线算法
对于询问的区间的字符串建一个trie树的话, 每个节点(除去根节点, 或者是边数)走两次, 最长的字符串不用回退, 答案就是 节点数 * 2 - 最长串的长度
求每次询问区间形成的trie树, 可以用离线算法, 给询问r端点排序, 这时只需要减去左边不包含的区间的节点就行了. 对于重复的边, 每次都让他计算为新来的字符串的长度, 不计算为以前的字符串的长度
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
template <typename T>
struct Fenwick {int n;std::vector<T> a;Fenwick(int n_ = 0) {init(n_);}void init(int n_) {n = n_;a.assign(n, T{});}void add(int x, const T &v) {for (int i = x; i <= n; i += i & -i) {a[i] = a[i] + v;}}T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = ans + a[i];}return ans;}T rangeSum(int l, int r) {return sum(r) - sum(l - 1);}};Fenwick<int> fenwick(1000001);
int nex[1000001][26], tot;
int cnt[1000001]; // 该结点结尾的字符串的数量
int belongto[1000001];
struct Trie {void insert(string s, int idx, int t = 1) { // 插入字符串int p = 0;for (int i = 0; i < s.length(); i++) {int c = s[i] - 'a';if (!nex[p][c]) nex[p][c] = ++tot; // 如果没有，就添加结点p = nex[p][c];;if(belongto[p]) fenwick.add(belongto[p], -1);belongto[p] = idx;fenwick.add(belongto[p], 1);}cnt[p] += t;}bool find(string s) { // 查找字符串int p = 0;for (int i = 0; i < s.length(); i++) {int c = s[i] - 'a';if (!nex[p][c]) return 0;p = nex[p][c];}return cnt[p];}
};template<class Info>
struct SegmentTree {int n;std::vector<Info> info;SegmentTree() : n(0) {}SegmentTree(int n_, Info v_ = Info()) {init(n_, v_);}template<class T>SegmentTree(std::vector<T> init_) {init(init_);}void init(int n_, Info v_ = Info()) {init(std::vector(n_, v_));}template<class T>void init(std::vector<T> init_) {n = init_.size();info.assign(4 << std::__lg(n), Info());std::function<void(int, int, int)> build = [&](int p, int l, int r) {if (r - l == 1) {info[p] = init_[l];return;}int m = (l + r) / 2;build(2 * p, l, m);build(2 * p + 1, m, r);pull(p);};build(1, 0, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void modify(int p, int l, int r, int x, const Info &v) {if (r - l == 1) {info[p] = v;return;}int m = (l + r) / 2;if (x < m) {modify(2 * p, l, m, x, v);} else {modify(2 * p + 1, m, r, x, v);}pull(p);}void modify(int p, const Info &v) {modify(1, 1, n, p, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l >= y || r <= x) {return Info();}if (l >= x && r <= y) {return info[p];}int m = (l + r) / 2;return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 1, n, l, r + 1);}template<class F>int findFirst(int p, int l, int r, int x, int y, F &&pred) {if (l >= y || r <= x) {return -1;}if (l >= x && r <= y && !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findFirst(2 * p, l, m, x, y, pred);if (res == -1) {res = findFirst(2 * p + 1, m, r, x, y, pred);}return res;}template<class F>int findFirst(int l, int r, F &&pred) {return findFirst(1, 1, n, l, r + 1, pred);}template<class F>int findLast(int p, int l, int r, int x, int y, F &&pred) {if (l >= y || r <= x) {return -1;}if (l >= x && r <= y && !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findLast(2 * p + 1, m, r, x, y, pred);if (res == -1) {res = findLast(2 * p, l, m, x, y, pred);}return res;}template<class F>int findLast(int l, int r, F &&pred) {return findLast(1, 1, n, l, r + 1, pred);}
};constexpr int inf = 1E9 + 1;
struct Info {int max = -inf;int min = inf;
};
Info operator+(const Info &a, const Info &b) {return { std::max(a.max, b.max), std::min(a.min, b.min) };
}struct qur {int l, idx;
};
void solve(){int n, m;cin >> n >> m;vector<string> s(n + 1);SegmentTree<Info> maxlen(n + 1);for(int i = 1; i <= n; i++) cin >> s[i], maxlen.modify(i, {(int)s[i].length(),(int)s[i].length()});vector<vector<qur>> xun(n + 1);for(int i = 1; i <= m; i++) {int l, r;cin >> l >> r;xun[r].push_back({l, i});}Trie trie;vector<int> ans(m + 1);for(int i = 1; i <= n; i++) {trie.insert(s[i], i);for(auto it : xun[i]) {int l = it.l, idx = it.idx;auto mxln = maxlen.rangeQuery(l, i).max;ans[idx] = fenwick.rangeSum(l, i) * 2 - mxln;} }for(int i = 1; i <= m; i++) cout << ans[i] << endl;}int main(){std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int T = 1;//cin >> T;// cout << 1 << endl;while(T--) solve();return 0;
}