做一个网站app需要多少钱,a做爰网站,个人网站有什么内容,eeworld电子工程世界app正题
题目链接:https://www.luogu.com.cn/problem/CF666E 解题思路
给出一个串SSS和nnn个串TiT_iTi。mmm次询问Sa∼bS_{a\sim b}Sa∼b在Tl∼rT_{l\sim r}Tl∼r中出现的最多次数并且输出这个串的编号。 1≤∣s∣≤5105,∑Ti≤5104,1≤m≤51051\leq |s|\leq 5\times 10^5…正题
题目链接:https://www.luogu.com.cn/problem/CF666E 解题思路
给出一个串SSS和nnn个串TiT_iTi。mmm次询问Sa∼bS_{a\sim b}Sa∼b在Tl∼rT_{l\sim r}Tl∼r中出现的最多次数并且输出这个串的编号。
1≤∣s∣≤5×105,∑Ti≤5×104,1≤m≤5×1051\leq |s|\leq 5\times 10^5,\sum T_i\leq 5\times 10^4,1\leq m\leq 5\times 10^51≤∣s∣≤5×105,∑Ti≤5×104,1≤m≤5×105 解题思路
把SSS和TTT丢一起跑一个广义SAMSAMSAM。
两个串包含当且仅当他们在SAMSAMSAM上对应节点是父子所以直接对于每个节点开一个线段树然后TTT的每个位置对应编号加一。
对于询问SSS子串直接倍增跳到对应位置然后用线段树合并上来的东西求答案就好了。 code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e62e510,S19;
int answ,ansv;
struct SegTree{int cnt,w[N*20],v[N*20],ls[N*20],rs[N*20];void PushUp(int x,int L,int R){w[x]-1;if(w[ls[x]]w[x])w[x]w[ls[x]],v[x]max(v[ls[x]],L);if(w[rs[x]]w[x])w[x]w[rs[x]],v[x]v[rs[x]];return;}void Change(int x,int L,int R,int pos){if(!x)xcnt;if(LR){w[x];v[x]L;return;}int mid(LR)1;if(posmid)Change(ls[x],L,mid,pos);else Change(rs[x],mid1,R,pos);PushUp(x,L,R);return;}void Ask(int x,int L,int R,int l,int r){if(!x){if(answ0)answ0,ansvl;return;}if(LlRr){if(answw[x])answw[x],ansvv[x];return;}int mid(LR)1;if(rmid)Ask(ls[x],L,mid,l,r);else if(lmid)Ask(rs[x],mid1,R,l,r);else Ask(ls[x],L,mid,l,mid),Ask(rs[x],mid1,R,mid1,r);}int Merge(int x,int y,int L,int R){if(!x||!y)return xy;int pcnt;if(LR){w[p]w[x]w[y];v[p]L;return p;}int mid(LR)1; ls[p]Merge(ls[x],ls[y],L,mid);rs[p]Merge(rs[x],rs[y],mid1,R);PushUp(p,L,R);return p;}
}T;
struct node{int to,next;
}a[N];
int n,m,l,tot,f[N][S1],rt[N],ls[N];
int cnt,len[N],ch[N][26],fa[N],pos[N];
char s[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
int Insert(int p,int c){if(ch[p][c]){int qch[p][c];if(len[p]1len[q])return q;else{int nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;return nq;}}int npcnt;len[np]len[p]1;for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{int qch[p][c];if(len[p]1len[q])fa[np]q;else{int nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]fa[np]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return np;
}
void dfs(int x){for(int ils[x];i;ia[i].next){int ya[i].to;f[y][0]x;dfs(y);rt[x]T.Merge(rt[x],rt[y],1,n);}return;
}
int GetPos(int l,int r){int xpos[r];for(int iS;i0;i--)if(len[f[x][i]]r-l1)xf[x][i];return x;
}
int main()
{scanf(%s,s1);lstrlen(s1);cnt1;for(int i1,x1;il;i){xInsert(x,s[i]-a);pos[i]x;}scanf(%d,n);for(int i1;in;i){scanf(%s,s1);int x1,lstrlen(s1);for(int j1;jl;j){xInsert(x,s[j]-a);T.Change(rt[x],1,n,i);}}for(int i2;icnt;i)addl(fa[i],i);dfs(1);for(int j1;jS;j)for(int i1;icnt;i)f[i][j]f[f[i][j-1]][j-1];scanf(%d,m);while(m--){int a,b,l,r;scanf(%d%d%d%d,l,r,a,b);int xGetPos(a,b);answ-1;ansv0;T.Ask(rt[x],1,n,l,r);printf(%d %d\n,ansv,answ);}return 0;
}
