建设银行衡阳市分行网站,组织建设情况怎么写,wordpress 商城,网站建设管理传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个字符串sss#xff0c;有qqq个询问#xff0c;每次给x,yx,yx,y代表取sss的前xxx个字符和后yyy个字符拼接起来得到ttt#xff0c;输出ttt在sss中出现的次数。 n,q≤2e5n,q\le2e5n,q≤2e5
思路思路题意
给你一个字符串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,lx−1][1,x],[l,lx-1][1,x],[l,lx−1]这两段区间一定是相等的这也提示我们可以先预处理kmpkmpkmp数组nenene不断暴跳ne[lx−1]ne[lx-1]ne[lx−1]一直跳到ne[x]ne[x]ne[x]的位置现在我们就有一个n2n^2n2的算法了我们可以对于每一个位置都检查一下是否能跳到[1,x],[n−y1,n][1,x],[n-y1,n][1,x],[n−y1,n]这两段区间即可。 考虑优化暴跳的过程显然我们可以建一颗failfailfail树比赛的时候也想到了但是我很神奇的想反了 不难发现对于xxx节点的子树中的所有点都可以跳到xxx这个点比赛鬼使神差的想成了对于xxx到根的一个链都可以跳到xxx其实当时跟队友商量一下还是能发现问题的但是挂机一下午真的太难受了打的一点斗志都没有。 那么问题就变成了有两棵树我们要找出来两颗子树中满足如下条件的点对数量假设在第一棵子树中的编号为xxx第二棵为yyy那么需要满足x1yx1yx1y此时贡献加一。 所以我们对第一颗树建主席树让后映射一下映射到右边点的dfsdfsdfs序这样查询的时候就可以直接查询右区间子树的dfsdfsdfs序内出现个数即可。 具体细节代码更清楚。。
//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-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];
vectorintv1[N],v2[N];void dfs1(int u,int fa) {in1[u]idx;inv[idx]u;for(auto x:v1[u]) {if(xfa) continue;dfs1(x,u);}out1[u]idx;
}void dfs2(int u,int fa) {in2[u]idx;for(auto x:v2[u]) {if(xfa) 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 i0;itot10;i) tr[i].ltr[i].rtr[i].cnt0;tot0;}void insert(int p,int q,int l,int r,int x) {qtot; tr[q]tr[p]; if(lr) {tr[q].cnt;return;}int mid(lr)1;if(xmid) insert(tr[p].l,tr[q].l,l,mid,x);else insert(tr[p].r,tr[q].r,mid1,r,x);tr[q].cnttr[tr[q].l].cnttr[tr[q].r].cnt;}int query(int p,int q,int l,int r,int ql,int qr) {if(lqlrqr) return tr[q].cnt-tr[p].cnt;int mid(lr)1;int ans0;if(qlmid) ansquery(tr[p].l,tr[q].l,l,mid,ql,qr);if(qrmid) ansquery(tr[p].r,tr[q].r,mid1,r,ql,qr);return ans;}
}tr;int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--) {scanf(%d%d%s,n,q,s1);ne1[1]0;for(int i2,j0;in;i) {while(js[i]!s[j1]) jne1[j];if(s[i]s[j1]) j;ne1[i]j;}ne2[n]n1;for(int in-1,jn1;i1;i--) {while(jns[i]!s[j-1]) jne2[j];if(s[i]s[j-1]) j--;ne2[i]j;}for(int i1;in;i) {v1[ne1[i]].pb(i),v2[ne2[i]].pb(i);}dfs1(0,-1); idx0; dfs2(n1,-1); idx0;for(int i1;in1;i) {tr.insert(root[i-1],root[i],1,n1,in2[inv[i]1]);}while(q--) {int x,y; scanf(%d%d,x,y);yn-y1;printf(%d\n,tr.query(root[in1[x]-1],root[out1[x]],1,n1,in2[y],out2[y]));}for(int i0;in1;i) {ne1[i]ne2[i]0; root[i]0;v1[i].clear(),v2[i].clear();}tr.init();}return 0;
}
/**/
