在哪个网站可以免费做广告,做数据的网站有哪些内容,网页制作与网站建设的发展趋势设想,app开发公司办公室设计Pty loves string 建立Border树后#xff0c;发现可以转化成两个子树中相同点的数量#xff0c;时间戳转化为连续的区间后相当于有两个数组#xff0c;每次给两个区间#xff0c;问区间相同点权的数目。
第一个数组作为区间#xff0c;第二个数组作为权值。将第一个数组建…Pty loves string 建立Border树后发现可以转化成两个子树中相同点的数量时间戳转化为连续的区间后相当于有两个数组每次给两个区间问区间相同点权的数目。
第一个数组作为区间第二个数组作为权值。将第一个数组建立主席树每次插入的是第一个区间位置的权值映射到第二个数组中的权值。然后就是区间查询。
#includebits/stdc.husing namespace std;
const int N200010;
char s[N];
int n,m;
int ne1[N],ne2[N];
vectorint e1[N],e2[N];
int dfn1[N],dfn2[N],sz1[N],sz2[N],timestamp;
int id[N];
struct node
{int l,r,v;
}tree[N*40];
int rt[N],cnt;
void insert(int u,int o,int l,int r,int v)
{tree[ucnt]tree[o];tree[u].v;if(lr) return;int midlr1;if(vmid)insert(tree[u].l,tree[o].l,l,mid,v);elseinsert(tree[u].r,tree[o].r,mid1,r,v);
}
int query(int u,int o,int l,int r,int L,int R)
{if(LlrR) return tree[u].v-tree[o].v;int v0;int midlr1;if(Lmid) vquery(tree[u].l,tree[o].l,l,mid,L,R);if(R mid) vquery(tree[u].r,tree[o].r,mid1,r,L,R);return v;
}
void dfs1(int u)
{sz1[u]1;dfn1[u]timestamp;id[timestamp]u;for(int v:e1[u]){dfs1(v);sz1[u]sz1[v];}
}
void dfs2(int u)
{sz2[u]1;dfn2[u]timestamp;for(int v:e2[u]){dfs2(v);sz2[u]sz2[v];}
}
void init()
{for(int i1;icnt;i) tree[i]{0,0,0};cnt0;for(int i0;in1;i) e1[i].clear(),e2[i].clear();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;i;i--){while(jns[i]!s[j-1]) jne2[j];if(s[i]s[j-1]) j--;ne2[i]j;}
}
void build()
{for(int i1;in;i) e1[ne1[i]].push_back(i),e2[ne2[i]].push_back(i);timestamp0;dfs1(0);timestamp0;dfs2(n1);for(int i1;in1;i) insert(rt[i],rt[i-1],1,n1,dfn2[id[i]1]);
}
int main()
{int Tc;scanf(%d,Tc);while(Tc--){scanf(%d%d%s,n,m,s1);init();build();while(m--){int x,y;scanf(%d%d,x,y);if(xyn) {puts(0);continue;}yn-y1;printf(%d\n,query(rt[dfn1[x]sz1[x]-1],rt[dfn1[x]-1],1,n1,dfn2[y],dfn2[y]sz2[y]-1));}}return 0;
}
