题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4453
询问离线，按R排序。
发现直接用 rk[ ] 的错误情况就是前面的某个位置 j 和自己位置 i 的 LCP 长度大于 i 到当前 R 的长度，这时虽然 rk[ j ] < rk[ i ] ，但答案是 j 。
但是如果 j < i && rk[ j ] > rk[ i ] 的话， j 就总是比 i 优，除非询问的 L 比较靠右。这样有些像单调栈，所以维护一个 rk[ ] 单调递减的单调栈。
这样就要把 j < i && rk[ j ] < rk[ i ] 都弹掉。但是在一定期限内它们也可能是答案。
发现 j < i && rk[ j ] < rk[ i ] 的 j 比 i 优的期限是询问的 R 到 i+LCP( j , i ) 之前。所以把 j 记在 i+LCP( j , i ) 那个位置上，遍历到那个位置的时候就把 j 从答案备选里删去。
要支持这样的删去，考虑用 set 。
发现如果要删去的 j 也有一些 k < j && rk[ k ] < rk[ j ] 的位置 k ，而且此时 k 还没被删去。这样说明 j+LCP( j , k ) > i+LCP( i , j ) ；如果删去 j ，可以发现 i+LCP( i , k ) 一定等于 i+LCP( i , j )，即这些 k 也应该同时被删去。所以把每个 j 记在 i 上，删去 i 的时候遍历一遍 j 把 j 也删了。
这样的话在位置上遍历要删的东西的时候会发现一些已经被删了。用 bool 数组判断一下就行了。不过自己忘了判断了，竟然也没错。看来如果传进去值的话，也可以删不在 set 里的值？
#include<cstdio> #include<cstring> #include<algorithm> #include<set> using namespace std; const int N=1e5+5,K=20; int n,m,hd[N],xnt,to[N],nxt[N],phd[N],pnt,pto[N],pxt[N],ans[N]; int sta[N],top,sa[N],rk[N],tp[N],tx[N],ht[N][K],lg[N],bin[K]; char s[N]; struct Node{ int l,r,id; bool operator< (const Node &b)const {return r<b.r;} }t[N]; set<int> st; int Mn(int a,int b){return a<b?a:b;} int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } void Rsort(int n,int nm) { for(int i=1;i<=nm;i++)tx[i]=0; for(int i=1;i<=n;i++)tx[rk[i]]++; for(int i=2;i<=nm;i++)tx[i]+=tx[i-1]; for(int i=n;i;i--)sa[tx[rk[tp[i]]]--]=tp[i]; } void get_sa(int n) { int nm=150; for(int i=1;i<=n;i++)tp[i]=i,rk[i]=s[i]; Rsort(n,nm); for(int k=1;k<=n;k<<=1) { int tot=0; for(int i=n-k+1;i<=n;i++)tp[++tot]=i; for(int i=1;i<=n;i++) if(sa[i]>k)tp[++tot]=sa[i]-k; Rsort(n,nm);memcpy(tp,rk,sizeof rk);nm=1;rk[sa[1]]=1; for(int i=2,u,v;i<=n;i++) { u=sa[i]+k;v=sa[i-1]+k;if(u>n)u=0;if(v>n)v=0; rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[u]==tp[v])?nm:++nm; } if(nm==n)break; } } void get_ht(int n) { lg[1]=0;for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1; bin[0]=1;for(int i=1;i<=lg[n];i++)bin[i]=bin[i-1]<<1; for(int i=1,k=0,j;i<=n;i++) { for(k?k--:0,j=sa[rk[i]-1];i+k<=n&&j+k<=n&&s[i+k]==s[j+k];k++); ht[rk[i]][0]=k;//rk[i] } for(int j=1;j<=lg[n];j++) for(int i=1;i<=n&&i+bin[j]-1<=n;i++) ht[i][j]=Mn(ht[i][j-1],ht[i+bin[j-1]][j-1]); } int get_lcp(int l,int r) { if(l==r)return n-l+1; l=rk[l]; r=rk[r]; if(l>r)swap(l,r); int d=lg[r-l]; return Mn(ht[l+1][d],ht[r-bin[d]+1][d]);//l+1 } void add_pos(int x,int y){pto[++pnt]=y;pxt[pnt]=phd[x];phd[x]=pnt;} void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;} void ins(int x){st.insert(x);} void del(int x){for(int i=hd[x];i;i=nxt[i])st.erase(to[i]);st.erase(x);} int fnd(int x){return *st.lower_bound(x);} int main() { scanf("%s",s+1);n=strlen(s+1);get_sa(n);get_ht(n); m=rdn(); for(int i=1;i<=m;i++)t[i].l=rdn(),t[i].r=rdn(),t[i].id=i; sort(t+1,t+m+1); int p=1; for(int i=1;i<=n;i++) { while(top&&rk[sta[top]]<rk[i]) { int d=get_lcp(sta[top],i); if(!d){del(sta[top]);top--;continue;} add_pos(i+d,sta[top]); //not -1 add(i,sta[top]);top--; //i to sta[top] } sta[++top]=i;ins(i); for(int j=phd[i];j;j=pxt[j])del(pto[j]); for(;p<=m&&t[p].r==i;p++) ans[t[p].id]=fnd(t[p].l); } for(int i=1;i<=m;i++)printf("%d ",ans[i]); return 0; }