傳送門
文章目錄
題意：
給你一個字符串sss，有qqq個詢問，每次給x,yx,yx,y代表取sss的前xxx個字符和后yyy個字符拼接起來得到ttt，輸出ttt在sss中出現的次數。
n,q≤2e5n,q\le2e5n,q≤2e5
思路：
考慮每個詢問拼出來的串在sss中出現的位置，假設是[l,r][l,r][l,r]，那么對于[1,x],[l,l+x?1][1,x],[l,l+x-1][1,x],[l,l+x?1]這兩段區間一定是相等的，這也提示我們可以先預處理kmpkmpkmp數組nenene，不斷暴跳ne[l+x?1]ne[l+x-1]ne[l+x?1]，一直跳到ne[x]ne[x]ne[x]的位置，現在我們就有一個n2n^2n2的算法了，我們可以對于每一個位置都檢查一下是否能跳到[1,x],[n?y+1,n][1,x],[n-y+1,n][1,x],[n?y+1,n]這兩段區間即可。
考慮優化暴跳的過程，顯然我們可以建一顆failfailfail樹，比賽的時候也想到了，但是我很神奇的想反了！
不難發現，對于xxx節點的子樹中的所有點，都可以跳到xxx這個點，比賽鬼使神差的想成了對于xxx到根的一個鏈都可以跳到xxx，其實當時跟隊友商量一下還是能發現問題的，但是掛機一下午真的太難受了，打的一點斗志都沒有。
那么問題就變成了有兩棵樹，我們要找出來兩顆子樹中滿足如下條件的點對數量：假設在第一棵子樹中的編號為xxx，第二棵為yyy，那么需要滿足x+1=yx+1=yx+1=y，此時貢獻加一。
所以我們對第一顆樹建主席樹，讓后映射一下，映射到右邊點的dfsdfsdfs序，這樣查詢的時候就可以直接查詢右區間子樹的dfsdfsdfs序內出現個數即可。
具體細節代碼更清楚。。
#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>
#include<random>
#include<cassert>
#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
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,q
;
int ne1
[N
],ne2
[N
];
int in1
[N
],in2
[N
],out1
[N
],out2
[N
],idx
;
int inv
[N
],root
[N
],tot
;
char s
[N
];
vector
<int>v1
[N
],v2
[N
];void dfs1(int u
,int fa
) {in1
[u
]=++idx
;inv
[idx
]=u
;for(auto x
:v1
[u
]) {if(x
==fa
) continue;dfs1(x
,u
);}out1
[u
]=idx
;
}void dfs2(int u
,int fa
) {in2
[u
]=++idx
;for(auto x
:v2
[u
]) {if(x
==fa
) continue;dfs2(x
,u
);}out2
[u
]=idx
;
}struct MainTree
{int tot
;struct Node{int l
,r
;int cnt
;}tr
[N
*40];void init() {for(int i
=0;i
<=tot
+10;i
++) tr
[i
].l
=tr
[i
].r
=tr
[i
].cnt
=0;tot
=0;}void insert(int p
,int &q
,int l
,int r
,int x
) {q
=++tot
; tr
[q
]=tr
[p
]; if(l
==r
) {tr
[q
].cnt
++;return;}int mid
=(l
+r
)>>1;if(x
<=mid
) insert(tr
[p
].l
,tr
[q
].l
,l
,mid
,x
);else insert(tr
[p
].r
,tr
[q
].r
,mid
+1,r
,x
);tr
[q
].cnt
=tr
[tr
[q
].l
].cnt
+tr
[tr
[q
].r
].cnt
;}int query(int p
,int q
,int l
,int r
,int ql
,int qr
) {if(l
>=ql
&&r
<=qr
) return tr
[q
].cnt
-tr
[p
].cnt
;int mid
=(l
+r
)>>1;int ans
=0;if(ql
<=mid
) ans
+=query(tr
[p
].l
,tr
[q
].l
,l
,mid
,ql
,qr
);if(qr
>mid
) ans
+=query(tr
[p
].r
,tr
[q
].r
,mid
+1,r
,ql
,qr
);return ans
;}
}tr
;int main()
{
int _
; scanf("%d",&_
);while(_
--) {scanf("%d%d%s",&n
,&q
,s
+1);ne1
[1]=0;for(int i
=2,j
=0;i
<=n
;i
++) {while(j
&&s
[i
]!=s
[j
+1]) j
=ne1
[j
];if(s
[i
]==s
[j
+1]) j
++;ne1
[i
]=j
;}ne2
[n
]=n
+1;for(int i
=n
-1,j
=n
+1;i
>=1;i
--) {while(j
<=n
&&s
[i
]!=s
[j
-1]) j
=ne2
[j
];if(s
[i
]==s
[j
-1]) j
--;ne2
[i
]=j
;}for(int i
=1;i
<=n
;i
++) {v1
[ne1
[i
]].pb(i
),v2
[ne2
[i
]].pb(i
);}dfs1(0,-1); idx
=0; dfs2(n
+1,-1); idx
=0;for(int i
=1;i
<=n
+1;i
++) {tr
.insert(root
[i
-1],root
[i
],1,n
+1,in2
[inv
[i
]+1]);}while(q
--) {int x
,y
; scanf("%d%d",&x
,&y
);y
=n
-y
+1;printf("%d\n",tr
.query(root
[in1
[x
]-1],root
[out1
[x
]],1,n
+1,in2
[y
],out2
[y
]));}for(int i
=0;i
<=n
+1;i
++) {ne1
[i
]=ne2
[i
]=0; root
[i
]=0;v1
[i
].clear(),v2
[i
].clear();}tr
.init();}return 0;
}
總結
以上是生活随笔為你收集整理的HDU - 7084 Pty loves string kmp + fail树 + 主席树的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
