智乃的Notepad(Hard version) (trie树 + 离线) 2025牛客寒假算法底子集训营 - IT评测·应用市场-qidao123.com

#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;
}

复制代码