怎么自己编写网站,自己建设购物网站,使用他人商标做网站搜索词,深圳外贸英文网站设计联系电话F. Paper Grading
大佬题解 一般关于前缀的问题基本都是Trie树。
首先将所给字符串建立一棵Trie树#xff0c;Trie能够解决一个字符串在一个字符串集合中出现的次数#xff0c;而查询前缀次数只需要找到Trie树中所给字符末尾的位置#xff0c;那么其子树中打标记的次数即前…F. Paper Grading
大佬题解 一般关于前缀的问题基本都是Trie树。
首先将所给字符串建立一棵Trie树Trie能够解决一个字符串在一个字符串集合中出现的次数而查询前缀次数只需要找到Trie树中所给字符末尾的位置那么其子树中打标记的次数即前缀次数。
由于子树dfs序[L,R]连续于是把字典树按照dfs序标记即变成区间查询问题[l,r]中[L,R]之间数的个数二位偏序问题。
树套树树状数组套下标线段树即可解决要动态开点
#includeiostream
using namespace std;
const int N200010;
char s[N];
int n,q,pos[N];
// Trie树
struct T1
{int tree[N][26],idx;int insert(char s[]){int p0;for(int i0;s[i];i){int ts[i]-a;if(!tree[p][t]) tree[p][t]idx;ptree[p][t];}return p;}int find(char s[],int k){int p0;for(int i0;ik;i){int ts[i]-a;if(!tree[p][t]) return -1;ptree[p][t];}return p;}
}Trie;
// 动态开点线段树
struct T2
{struct node{int l,r;int sz;}tree[N*40];int root[N],cnt;void update(int u,int l,int r,int pos,int x){if(!u) ucnt;tree[u].szx;if(lr) return;int midlr1;if(posmid) update(tree[u].l,l,mid,pos,x);else update(tree[u].r,mid1,r,pos,x);}int query(int u,int l,int r,int L,int R){if(!u) return 0;if(LlrR) return tree[u].sz;int midlr1;int v0;if(Lmid) vquery(tree[u].l,l,mid,L,R);if(Rmid) vquery(tree[u].r,mid1,r,L,R);return v;}
}Segment;
// dfs序转化为区间
int dfn[N],sz[N],timestamp;
void dfs(int u)
{dfn[u]timestamp;sz[u]1;for(int i0;i26;i)if(Trie.tree[u][i]) dfs(Trie.tree[u][i]),sz[u]sz[Trie.tree[u][i]];
}
// 树状数组
int lowbit(int x) {return x-x;}
void add(int k,int pos,int x)
{for(;kn;klowbit(k))Segment.update(Segment.root[k],1,timestamp,pos,x);
}
int sum(int k,int L,int R)
{int res0;for(;k;k-lowbit(k))resSegment.query(Segment.root[k],1,timestamp,L,R);return res;
}
int main()
{cinnq;for(int i1;in;i){cins;pos[i]Trie.insert(s);}dfs(0);for(int i1;in;i)add(i,dfn[pos[i]],1);while(q--){int op;cinop;if(op1){int u,v;cinuv;add(u,dfn[pos[u]],-1);add(v,dfn[pos[v]],-1);add(u,dfn[pos[v]],1);add(v,dfn[pos[u]],1);swap(pos[u],pos[v]);}else{int k,l,r;cins;cinklr;int uTrie.find(s,k);if(u-1) cout0\n;else{int Ldfn[u],Rdfn[u]sz[u]-1;coutsum(r,L,R)-sum(l-1,L,R)\n;}}}return 0;
}cdq分治带修改二维数点把时间轴当作一维即静态三维数点cdq分治树状数组
#includeiostream
#includealgorithm
using namespace std;
const int N200010;
char s[N];
int n,m,pos[N];
// Trie树
struct T1
{int tree[N][26],idx;int insert(char s[]){int p0;for(int i0;s[i];i){int ts[i]-a;if(!tree[p][t]) tree[p][t]idx;ptree[p][t];}return p;}int find(char s[],int k){int p0;for(int i0;ik;i){int ts[i]-a;if(!tree[p][t]) return -1;ptree[p][t];}return p;}
}Trie;
// dfs序转化为区间
int dfn[N],sz[N],timestamp;
void dfs(int u)
{dfn[u]timestamp;sz[u]1;for(int i0;i26;i)if(Trie.tree[u][i]) dfs(Trie.tree[u][i]),sz[u]sz[Trie.tree[u][i]];
}
int ans[N];
struct node
{int op;int a,b,c,cnt;int sign,id;
}q[N*5];
int st[N];
bool cmpb(const node x,const node y)
{return x.by.b||x.by.bx.opy.op;
}
int fw[N];
int lowbit(int x){return x-x;}
void update(int k,int x){for(;ktimestamp;klowbit(k)) fw[k]x;}
int query(int k){int res0;for(;k;k-lowbit(k)) resfw[k];return res;}
void solve(int l,int r)
{if(lr) return;int midlr1;solve(l,mid),solve(mid1,r);int il;for(int jmid1;jr;j){if(q[j].op1) continue;while(imidq[i].bq[j].b){if(q[i].op1) update(q[i].c,q[i].cnt);i;}ans[q[j].id]q[j].sign*query(q[j].c);}while(il){i--;if(q[i].op1) update(q[i].c,-q[i].cnt);}inplace_merge(ql,qmid1,qr1,cmpb);
}
int main()
{cinnm;for(int i1;in;i){cins;pos[i]Trie.insert(s);}dfs(0);int cnt0;for(int i1;in;i)q[cnt]{1,0,i,dfn[pos[i]],1};for(int i1;im;i){int op;cinop;if(op1){int u,v;cinuv;q[cnt]{1,i,u,dfn[pos[u]],-1};q[cnt]{1,i,v,dfn[pos[v]],-1};q[cnt]{1,i,u,dfn[pos[v]],1};q[cnt]{1,i,v,dfn[pos[u]],1};swap(pos[u],pos[v]);}else{st[i]1;int k,l,r;cins;cinklr;int uTrie.find(s,k);if(u-1) ans[i]0;else{int Ldfn[u],Rdfn[u]sz[u]-1;q[cnt]{2,i,r,R,0,1,i};q[cnt]{2,i,l-1,R,0,-1,i};q[cnt]{2,i,r,L-1,0,-1,i};q[cnt]{2,i,l-1,L-1,0,1,i};}}}solve(1,cnt);for(int i1;im;i)if(st[i]) coutans[i]\n;return 0;
}
写代码过程中总是弄不清记得东西每次都是一层一层的想尤其是dfs序问题很迷糊还是要多写多积累要不然训练总是挂机
