生活随笔
收集整理的這篇文章主要介紹了
Prefix HDU - 5790 字典树 + 主席树
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
傳送門
文章目錄
題意：
給你nnn個(gè)串，每次詢問一個(gè)區(qū)間，返回這個(gè)區(qū)間的串的不同的前綴個(gè)數(shù)，強(qiáng)制在線。
思路：
碰到字符串前綴的問題，我們自然的想到用字典樹來解決。
對(duì)于每個(gè)串，我們將其插入字典樹的時(shí)候記一下當(dāng)前串的每個(gè)前綴的ididid，我們可以將問題就轉(zhuǎn)化成詢問區(qū)間內(nèi)出現(xiàn)數(shù)字的個(gè)數(shù)(即出現(xiàn)的ididid)，因?yàn)橐獜?qiáng)制在線，我們考慮用主席樹維護(hù)歷史信息。
對(duì)于維護(hù)區(qū)間內(nèi)出現(xiàn)數(shù)字的個(gè)數(shù)，這是個(gè)經(jīng)典問題了，維護(hù)前綴出現(xiàn)的最后一個(gè)位置即可。查詢的時(shí)候直接查詢第rrr棵樹的區(qū)間和即可。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=200110,mod
=1e9+7,INF
=0x3f3f3f3f;
const int P
=131;
const double eps
=1e-6;int n
,m
;
int root
[N
],tot
;
int idx
,num
[N
*5],tree
[N
][26],id
,st
[N
*5];
int pre
[N
*5];
char s
[N
];
struct Node
{int l
,r
;int cnt
;
}tr
[N
*40];int newnode()
{idx
++;for(int i
=0;i
<26;i
++) tree
[idx
][i
]=0;num
[idx
]=0;return idx
;
}void add()
{int p
=0;for(int i
=0;s
[i
];i
++){int now
=s
[i
]-'a';if(!tree
[p
][now
]) tree
[p
][now
]=newnode();p
=tree
[p
][now
];if(!num
[p
]) num
[p
]=++id
;st
[i
]=num
[p
];}
}void insert(int p
,int &q
,int l
,int r
,int pos
,int x
)
{q
=++tot
; tr
[q
]=tr
[p
];tr
[q
].cnt
+=x
;if(l
==r
) return;int mid
=l
+r
>>1;if(pos
<=mid
) insert(tr
[p
].l
,tr
[q
].l
,l
,mid
,pos
,x
);else insert(tr
[p
].r
,tr
[q
].r
,mid
+1,r
,pos
,x
);
}int query(int u
,int l
,int r
,int ql
,int qr
)
{if(!u
) return 0;if(l
>=ql
&&r
<=qr
) return tr
[u
].cnt
;int ans
=0,mid
=l
+r
>>1;if(ql
<=mid
) ans
+=query(tr
[u
].l
,l
,mid
,ql
,qr
);if(qr
>mid
) ans
+=query(tr
[u
].r
,mid
+1,r
,ql
,qr
);return ans
;
}int main()
{
memset(pre
,-1,sizeof(pre
));while(scanf("%d",&n
)!=EOF){memset(tree
,0,sizeof(tree
));idx
=tot
=id
=0;for(int i
=1;i
<=n
;i
++){scanf("%s",s
);add();root
[i
]=root
[i
-1];for(int j
=0;s
[j
];j
++){if(pre
[st
[j
]]==-1) insert(root
[i
],root
[i
],1,n
,i
,1);else{insert(root
[i
],root
[i
],1,n
,pre
[st
[j
]],-1);insert(root
[i
],root
[i
],1,n
,i
,1);}pre
[st
[j
]]=i
;}}scanf("%d",&m
);int ans
=0;while(m
--){int ll
,rr
; scanf("%d%d",&ll
,&rr
);int l
=min((ll
+ans
)%n
,(rr
+ans
)%n
)+1;int r
=max((ll
+ans
)%n
,(rr
+ans
)%n
)+1;printf("%d\n",ans
=query(root
[r
],1,n
,l
,r
));}for(int i
=1;i
<=id
;i
++) pre
[i
]=-1;}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的Prefix HDU - 5790 字典树 + 主席树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
