我们先考虑如何比较两两的字符串
我们可以用线段树来维护哈希值 在线段树上根据二分的性质来做即可
又考虑到 每颗线段树是在之前的某颗基础上只修改了一个节点 那显然就想到了主席树
另外说说如何pushup 我们考虑这样一个字符串 abcdefg
假设当前节点左儿子是abc 右儿子是defg
由于我们的哈希值用的是unsigned long long 自然溢出大法 也就是说abc的哈希值是a(base^1)+b(base^2)+c(base^3),而defg的哈希值是d(base^1)+...
因此只需要给cefg乘上一个base^3就好了
代码也很好写
#include<bits/stdc++.h> #define N 100005 #define M 100005 #define ull unsigned long long const int base=31; using namespace std; int n,m,tot,len[N],sum[N],p[N],lc[N],rc[N],rt[N]; ull pw[M]; char s[N]; void build(int &now,int l,int r) { now=++tot; len[now]=r-l+1; if(l==r) { sum[now]=s[l]; return; } int m=(l+r)>>1; build(lc[now],l,m); build(rc[now],m+1,r); sum[now]=sum[lc[now]]+sum[rc[now]]*pw[len[lc[now]]]; } inline void copy(int &x,int y) { x=++tot; lc[x]=lc[y]; rc[x]=rc[y]; len[x]=len[y]; sum[x]=sum[y]; } inline void insert(int x,int &y,int l,int r,int p,int v) { copy(y,x); if(l==r) //把x复制一份 给y { sum[y]=v; return; } int m=(l+r)>>1; if(p<=m) insert(lc[x],lc[y],l,m,p,v); else insert(rc[x],rc[y],m+1,r,p,v); sum[y]=sum[lc[y]]+sum[rc[y]]*pw[len[lc[y]]]; } inline int cmp(int x,int y,int l,int r) { if(l==r) { if(sum[x]<sum[y]) return -1; else return 1; } int m=(l+r)>>1; if(sum[lc[x]]!=sum[lc[y]]) return cmp(lc[x],lc[y],l,m); else return cmp(rc[x],rc[y],m+1,r); } inline bool comp(const int &a,const int &b) { if(sum[rt[a]]==sum[rt[b]]) return a<b; return cmp(rt[a],rt[b],1,m)<0; } int main() { cin>>n>>m; scanf("%s",s+1); pw[0]=1; for(int i=1;i<=m;i++) pw[i]=pw[i-1]*base; build(rt[1],1,m); for(int i=2;i<=n;i++) { int who,pos; cin>>who>>pos; scanf("%s",s+1); insert(rt[who],rt[i],1,m,pos,s[1]); //把以i为根的线段树 接到被膜拜的人身上 } for(int i=1;i<=n;i++) p[i]=i; sort(p+1,p+n+1,comp); for(int i=1;i<=n;i++) cout<<p[i]<<" "; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9799343.html
