2025牛客WC3-D-智乃的Notepad(Hard version) · znzryb
## 思路讲解
[2025牛客WC3-C-智乃的Notepad(Easy version)](/2025/01/27/20250127-5c6cbd48) 的结论如下：
> 字典树每次扩充新节点++ans；最后ans就是字典树的节点数量（严格来说是不包含idx=0的节点的数量），当然此时不是答案，根据观察，所有的节点都需要被回退，只有最长的字符串不需要回退，所以答案就是
```cpp
cout<<ans*2-maxLen<<'\n';
```
> 除了最长字符串上的节点，全部都要打一遍，然后再删除掉，故ans*2，然后最长的字符串不需要回退，-maxLen
那么既然就是要求区间快速查询，我们只要查出**这个区间最长的字符串长度是多少** & **这个区间生成的Trie树节点数** 就行了。
当然前者简单，用树状数组~~只会树状数组~~（ST表，线段树，单调栈…..）就行了（前置知识：用树状数组实现RMQ）
后者怎么搞那？（思路参考以下讲解）
[https://www.bilibili.com/video/BV1HzfmYZEje/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675](https://www.bilibili.com/video/BV1HzfmYZEje/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675)
然后还有一个点可能没有点破，就是其实你可以在插入完第R个字符串之后马上处理以第R个为结尾的询问，因为你提前知道所有的询问是吧（又不是强制在线），这也算是一种离线的trick吧
既然我们知道了可以这么玩就好了，我们只需要优先考虑后面插入的字符串就好了，因为后面要的一定要，区间是必定包含后面的，前面要的只有在包含前面是才加入节点数。
具体实现也可以用树状数组维护前缀和来做。
## AC代码
AC
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75252163](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75252163)
```cpp
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = b; i >= a; --i)
#define SZ(x) ((int)x.size())
#define all(x,N) x.begin()+1,x.begin()+N+1
#define all1(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(1e5)+10;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline string reads()
{
string str="";
char ch=getchar();
//处理空格或回车
while(ch==' ' || ch=='\n' || ch=='\r')
{
ch=getchar();
}
//读入
while(ch!=' ' && ch!='\n' && ch!='\r')
{
str+=ch;
ch=getchar();
}
return str;
}
inline void write(int x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
int N,T;
int nex[MAXN*10][28]; // trie树
int color[MAXN*10]; // 颜色
int tr[MAXN]; // 树状数组，用来求区间最长字符串长度
int tree[MAXN]; // 树状数组2，用来记录前缀和
int idx; // trie树用编号
int Len[MAXN];
int Ans[MAXN];
string S[MAXN];
struct Query{
int l,r,id;
bool operator<(const Query &other) const{
return r<other.r;
}
};
vector<Query> que(MAXN);
inline int lowbit(int x){
return x&(-x);
}
inline void add2(int p,int x){
while (p<=N) {
tree[p]+=x;
p+=lowbit(p);
}
}
inline int query2(int p){
int res=0;
while (p>0) {
res+=tree[p];
p-=lowbit(p);
}
return res;
}
inline void add(int p,int x){
while (p<=N) {
tr[p]=x; // 因为只是用来建树，顺序调用，所以这样写没问题
for(int i=1;i<lowbit(p);i*=2){ // 遍历i下面的区间
tr[p]=max(tr[p],tr[p-i]);
}
p+=lowbit(p);
}
}
inline int query(int l,int r){
int res=0;
while (l<=r) {
if(r-lowbit(r)<l){
res=max(Len[r],res);
r-=1;
}else {
res=max(tr[r],res);
r-=lowbit(r);
}
}
return res;
}
inline void buildTree(string &s,int c){
int node=0;
int len=SZ(s);
FOR(i, 0, len-1){
if(nex[node][s[i]-'a']==0){
nex[node][s[i]-'a']=++idx;
node=idx;
add2(c,1);
color[node]=c;
}else{
node=nex[node][s[i]-'a'];
// colCnt[color[node]]-=1;
add2(color[node], -1);
add2(c, 1);
// colCnt[c]+=1;
color[node]=c;
}
}
int begin=lower_bound(all(que,T),(Query){0,c,0})-que.begin();
int end=upper_bound(all(que,T),(Query){MAXN,c,MAXN})-que.begin();
FOR(j, begin, end-1){
int res=query2(que[j].r)-query2(que[j].l-1);
Ans[que[j].id]=res*2-query(que[j].l, que[j].r);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
N=read();T=read();
FOR(i, 1, N){
S[i]=reads();
Len[i]=SZ(S[i]);
// 树状数组操作(RMQ)
add(i,Len[i]);
}
FOR(i, 1, T){
que[i].l=read();
que[i].r=read();
que[i].id=i;
}
sort(all(que,T));
FOR(i, 1, N){
buildTree(S[i], i);
}
FOR(i, 1, T){
write(Ans[i]);
putchar('\n');
}
return 0;
}
/*
3 3
nowcoder
nowdays
now
1 3
1 2
3 3
10 1
agdsjaxbsv
afghdgsgahg
saghjvxbaa
aasagahdb
abnsbdvsbdabvgh
abnsbbzbavba]
aaaasdfxfvax
ytftyfsasdfd
fdsdssddsdx
uufdssdvgd
1 10
*/
```
## 心路历程（WA，TLE，MLE……）
因为用了两个树状数组，这个名字起的也比较重，前面好几次搞混了。还有N，T搞混了，que数组长度是T，我以为是N了，总之最后有惊无险，都搞定了