hdu 5008(2014 ACM/ICPC Asia Regional Xi'an Online ) Boring String Problem(后缀数组&二分)(二)
+1,mid)>=len) ans=mid,low=mid+1; else hi=mid-1; } return ans; } inline ll ReadInt() { char ch = getchar(); if (ch==EOF) return -1; ll data = 0; while (ch < '0' || ch > '9') { ch = getchar(); if (ch==EOF) return -1; } do { data = data*10 + ch-'0'; ch = getchar(); } while (ch >= '0' && ch <= '9'); return data; } inline void putit(int x) { if (x/10>0) putit(x/10); putchar(x%10+'0'); } int main() { int q,lll,rrr; ll kth; prermq(); while(~scanf("%s",txt)) { m=150,n=strlen(txt); n++; getsa(txt); gethe(txt); rmq_init(); n--; build(1,n,1); scanf("%d",&q); le=ri=0; while(q--) { kth=ReadInt(); kth=(le^ri^kth)+1; qu(1,n,1,kth); if(pos==-1) putit(le),putchar(' '),putit(ri),putchar('\n'); else { lll=binl(pos); rrr=binr(pos); le=rmq_id(lll,rrr)+1; ri=le+len-1; putit(le),putchar(' '),putit(ri),putchar('\n'); } } } return 0; }
|