记录编号 | 370764 | 评测结果 | AAAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [HEOI 2016] 字符串 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 8.759 s | ||
提交时间 | 2017-02-14 14:21:26 | 内存使用 | 68.38 MiB | ||
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; const int maxn = 100100; struct Node{ int lch,rch,val; Node(){lch = rch = val = 0;} }t[maxn*50]; int tot = 0,root[maxn]={0},cnt = 0;; int sa[maxn],wa[maxn],wb[maxn],bucket[maxn]; int rank[maxn]={0},height[maxn]={0}; int st[20][maxn]={0},Log2[maxn]={0}; bool Cmp(const int *r,int x,int y,int k) {return r[x] == r[y]&&r[x+k] == r[y+k];} void doubling(const char *r,int n,int m){ int *x=wa,*y=wb,*t,i,j,p; for(i = 0;i <= m;i++)bucket[i] = 0; for(i = 0;i < n;i++)bucket[x[i] = r[i]]++; for(i = 1;i < m;i++)bucket[i] += bucket[i-1]; for(i = n-1;i>=0;i--)sa[--bucket[x[i]]] = i; for(j = 1,p = 1;p < n;j<<=1,m=p){ for(p=0,i=n-j;i<n;i++)y[p++] = i; for(i = 0;i < n;i++)if(sa[i] >= j)y[p++] = sa[i]-j; for(i = 0;i <= m;i++)bucket[i] = 0; for(i = 0;i < n;i++)bucket[x[y[i]]]++; for(i = 1;i <= m;i++)bucket[i]+=bucket[i-1]; for(i = n-1;i>=0;i--)sa[--bucket[x[y[i]]]] = y[i]; for(t=x,x=y,y=t,x[sa[0]] = 0,p=1,i=1;i < n;i++) x[sa[i]] = Cmp(y,sa[i],sa[i-1],j)?p-1:p++; } } void Getheight(const char *r,int n){ int i,j,k = 0; for(i = 0;i <= n;i++)rank[sa[i]] = i; for(i = 0;i <= n;height[rank[i++]] = k) for(k?k--:0,j = sa[rank[i]-1];r[i+k] == r[j+k];k++); } int N,M;char ch[maxn]; void Init(){ memset(st,0x3f,sizeof(st)); Log2[1] = 0; for(int i = 2;i <= N;i++){ Log2[i] = Log2[i-1]; if((1<<Log2[i]+1) == i)Log2[i]++; } memset(st,0x3f,sizeof st); for(int i = 0;i <= N;i++)st[0][i]=height[i+1]; for(int i = 1;i <= Log2[N];i++) for(int j = 0;j <= N;j++){ st[i][j]=st[i-1][j]; if(j+(1<<i-1) <= N)st[i][j] = min(st[i][j],st[i-1][j+(1<<i-1)]); } } int Rmq(int l,int r){ if(l > r)swap(l,r);r--; int len = Log2[r-l+1]; return min(st[len][l],st[len][r-(1<<len)+1]); } void Insert(int last,int &now,int l,int r,int goal){ now = ++tot; t[now] = t[last];t[now].val++; if(l == r)return; int mid = (l+r)>>1; if(goal <= mid)Insert(t[last].lch,t[now].lch,l,mid,goal); else Insert(t[last].rch,t[now].rch,mid+1,r,goal); } int query(int &L,int &R,int l,int r,int x,int y){ if(!L)L = ++tot;if(!R)R = ++tot; if(x <= l&&y >= r)return t[R].val-t[L].val; int mid = (l+r)>>1,ret = 0; if(x <= mid)ret += query(t[L].lch,t[R].lch,l,mid,x,y); if(y > mid)ret += query(t[L].rch,t[R].rch,mid+1,r,x,y); return ret; } #define mid ((l+r)>>1) int Rank(int goal,int l,int r,int L,int R){ int ret = 1; while(l < r){ //if(l == r){printf("goal = %d,l = %d\n",goal,l);break;} if(goal <= mid){ r = mid; L = t[L].lch;R = t[R].lch; } else{ l = mid+1; ret += t[t[R].lch].val-t[t[L].lch].val; L = t[L].rch;R = t[R].rch; } }return ret; } int Kth(int x,int l,int r,int L,int R){ while(l <= r){ if(l == r)return l; int tmp = t[t[R].lch].val-t[t[L].lch].val; if(tmp < x)x -= tmp,L = t[L].rch,R = t[R].rch,l = mid+1; else L = t[L].lch,R = t[R].lch,r = mid; }if(l == 0)puts("NO"); } int Calc(int L,int R,int goal){ int rr = Rank(goal,1,N,root[L],root[R+1]);//cout<<"rr is "<<rr<<endl; int qx=0,qy=0; if(R-L+2!=rr)qy = Kth(rr,1,N,root[L],root[R+1]); qx = Kth(rr-1,1,N,root[L],root[R+1]); // printf("qx = %d,qy = %d goal = %d\n",qx,qy,goal); return max(Rmq(qx,goal),Rmq(qy,goal)); } int main(){ freopen("heoi2016_str.in","r",stdin); freopen("heoi2016_str.out","w",stdout); scanf("%d%d%s",&N,&M,ch); doubling(ch,N+1,200); Getheight(ch,N); Init(); for(int i = 0;i < N;i++)Insert(root[i],root[i+1],1,N,rank[i]); //for(int i = 0;i < N;i++)printf("%d ",rank[i]);printf("\n"); int a,b,c,d; for(int i = 1;i <= M;i++){ scanf("%d%d%d%d",&a,&b,&c,&d);a--;b--;c--;d--; int l = 0,r = min(b-a+1,d-c+1),ans=0; while(l <= r){ if(Calc(a,b-mid+1,rank[c]) >= mid)ans = max(mid,ans),l = mid+1; else r = mid-1; } printf("%d\n",ans); } return 0; }