智乃的Notepad(Hard version) (trie树 + 离线) 2025牛客寒假算法底子集训营 ...

学习到的内容 :  初步了解并使用trie树, 初步了解了离线算法
对于扣问的区间的字符串建一个trie树的话, 每个节点(除去根节点, 或者是边数)走两次, 最长的字符串不消回退, 答案就是 节点数 * 2 - 最长串的长度
求每次扣问区间形成的trie树, 可以用离线算法, 给扣问r端点排序, 这时只必要减去左边不包含的区间的节点就行了. 对于重复的边, 每次都让他盘算为新来的字符串的长度, 不盘算为以前的字符串的长度

1. #include<bits/stdc++.h>
2. using namespace std;
3. using i64 = long long;
4. template <typename T>
5. struct Fenwick {
6.     int n;
7.     std::vector<T> a;
8.    
9.     Fenwick(int n_ = 0) {
10.         init(n_);
11.     }
12.    
13.     void init(int n_) {
14.         n = n_;
15.         a.assign(n, T{});
16.     }
17.    
18.     void add(int x, const T &v) {
19.         for (int i = x; i <= n; i += i & -i) {
20.             a[i] = a[i] + v;
21.         }
22.     }
23.    
24.     T sum(int x) {
25.         T ans{};
26.         for (int i = x; i > 0; i -= i & -i) {
27.             ans = ans + a[i];
28.         }
29.         return ans;
30.     }
31.    
32.     T rangeSum(int l, int r) {
33.         return sum(r) - sum(l - 1);
34.     }
35.    
36. };
38. Fenwick<int> fenwick(1000001);
39. int nex[1000001][26], tot;
40. int cnt[1000001];  // 该结点结尾的字符串的数量
41. int belongto[1000001];
42. struct Trie {
43.   
44.   void insert(string s, int idx, int t = 1) {  // 插入字符串
45.     int p = 0;
46.     for (int i = 0; i < s.length(); i++) {
47.       int c = s[i] - 'a';
48.       if (!nex[p][c]) nex[p][c] = ++tot;  // 如果没有，就添加结点
49.       p = nex[p][c];
50. ;
51.       if(belongto[p]) fenwick.add(belongto[p], -1);
52.       belongto[p] = idx;
53.       fenwick.add(belongto[p], 1);
55.     }
56.     cnt[p] += t;
57.   }
59.   bool find(string s) {  // 查找字符串
60.     int p = 0;
61.     for (int i = 0; i < s.length(); i++) {
62.       int c = s[i] - 'a';
63.       if (!nex[p][c]) return 0;
64.       p = nex[p][c];
65.     }
66.     return cnt[p];
67.   }
68. };
70. template<class Info>
71. struct SegmentTree {
72.     int n;
73.     std::vector<Info> info;
74.     SegmentTree() : n(0) {}
75.     SegmentTree(int n_, Info v_ = Info()) {
76.         init(n_, v_);
77.     }
78.     template<class T>
79.     SegmentTree(std::vector<T> init_) {
80.         init(init_);
81.     }
82.     void init(int n_, Info v_ = Info()) {
83.         init(std::vector(n_, v_));
84.     }
85.     template<class T>
86.     void init(std::vector<T> init_) {
87.         n = init_.size();
88.         info.assign(4 << std::__lg(n), Info());
89.         std::function<void(int, int, int)> build = [&](int p, int l, int r) {
90.             if (r - l == 1) {
91.                 info[p] = init_[l];
92.                 return;
93.             }
94.             int m = (l + r) / 2;
95.             build(2 * p, l, m);
96.             build(2 * p + 1, m, r);
97.             pull(p);
98.         };
99.         build(1, 0, n);
100.     }
101.     void pull(int p) {
102.         info[p] = info[2 * p] + info[2 * p + 1];
103.     }
104.     void modify(int p, int l, int r, int x, const Info &v) {
105.         if (r - l == 1) {
106.             info[p] = v;
107.             return;
108.         }
109.         int m = (l + r) / 2;
110.         if (x < m) {
111.             modify(2 * p, l, m, x, v);
112.         } else {
113.             modify(2 * p + 1, m, r, x, v);
114.         }
115.         pull(p);
116.     }
117.     void modify(int p, const Info &v) {
118.         modify(1, 1, n, p, v);
119.     }
120.     Info rangeQuery(int p, int l, int r, int x, int y) {
121.         if (l >= y || r <= x) {
122.             return Info();
123.         }
124.         if (l >= x && r <= y) {
125.             return info[p];
126.         }
127.         int m = (l + r) / 2;
128.         return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
129.     }
130.     Info rangeQuery(int l, int r) {
131.         return rangeQuery(1, 1, n, l, r + 1);
132.     }
133.     template<class F>
134.     int findFirst(int p, int l, int r, int x, int y, F &&pred) {
135.         if (l >= y || r <= x) {
136.             return -1;
137.         }
138.         if (l >= x && r <= y && !pred(info[p])) {
139.             return -1;
140.         }
141.         if (r - l == 1) {
142.             return l;
143.         }
144.         int m = (l + r) / 2;
145.         int res = findFirst(2 * p, l, m, x, y, pred);
146.         if (res == -1) {
147.             res = findFirst(2 * p + 1, m, r, x, y, pred);
148.         }
149.         return res;
150.     }
151.     template<class F>
152.     int findFirst(int l, int r, F &&pred) {
153.         return findFirst(1, 1, n, l, r + 1, pred);
154.     }
155.     template<class F>
156.     int findLast(int p, int l, int r, int x, int y, F &&pred) {
157.         if (l >= y || r <= x) {
158.             return -1;
159.         }
160.         if (l >= x && r <= y && !pred(info[p])) {
161.             return -1;
162.         }
163.         if (r - l == 1) {
164.             return l;
165.         }
166.         int m = (l + r) / 2;
167.         int res = findLast(2 * p + 1, m, r, x, y, pred);
168.         if (res == -1) {
169.             res = findLast(2 * p, l, m, x, y, pred);
170.         }
171.         return res;
172.     }
173.     template<class F>
174.     int findLast(int l, int r, F &&pred) {
175.         return findLast(1, 1, n, l, r + 1, pred);
176.     }
177. };
179. constexpr int inf = 1E9 + 1;
180. struct Info {
181.     int max = -inf;
182.     int min = inf;
183. };
184. Info operator+(const Info &a, const Info &b) {
185.     return { std::max(a.max, b.max), std::min(a.min, b.min) };
186. }
188. struct qur {
189.         int l, idx;
190. };
191. void solve(){
192.        
193.         int n, m;
194.         cin >> n >> m;
196.         vector<string> s(n + 1);
197.         SegmentTree<Info> maxlen(n + 1);
198.         for(int i = 1; i <= n; i++) cin >> s[i], maxlen.modify(i, {(int)s[i].length(),(int)s[i].length()});
199.         vector<vector<qur>> xun(n + 1);
200.         for(int i = 1; i <= m; i++) {
201.                 int l, r;
202.                 cin >> l >> r;
203.                 xun[r].push_back({l, i});
204.         }
205.         Trie trie;
206.         vector<int> ans(m + 1);
207.         for(int i = 1; i <= n; i++) {
208.                 trie.insert(s[i], i);
209.                 for(auto it : xun[i]) {
210.                         int l = it.l, idx = it.idx;
211.                         auto mxln = maxlen.rangeQuery(l, i).max;
212.                         ans[idx] = fenwick.rangeSum(l, i) * 2 - mxln;
213.                 }
214.         }
215.         for(int i = 1; i <= m; i++)  cout << ans[i] << endl;
221.        
222. }
225. int main(){
226.         std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
227.         int T = 1;
228.         //cin >> T;
229.     // cout << 1 << endl;
230.         while(T--) solve();
232.         return 0;
233. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。