Skip to content

Instantly share code, notes, and snippets.

@amanCoder110599

amanCoder110599/CLUNQUE.java Secret

Created Jul 14, 2020
Embed
What would you like to do?
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Scanner;
class CLUNIQUE {
static int[] suffixArray(String S) {
int n = S.length();
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++)
order[i] = n - 1 - i;
Arrays.sort(order, (a, b) -> Character.compare(S.charAt(a), S.charAt(b)));
int[] sa = new int[n];
int[] classes = new int[n];
for (int i = 0; i < n; i++) {
sa[i] = order[i];
classes[i] = S.charAt(i);
}
for (int len = 1; len < n; len <<= 1) {
int[] c = classes.clone();
for (int i = 0; i < n; i++)
classes[sa[i]] = i > 0 && c[sa[i - 1]] == c[sa[i]] && sa[i - 1] + len < n
&& c[sa[i - 1] + (len >> 1)] == c[sa[i] + (len >> 1)] ? classes[sa[i - 1]] : i;
int[] cnt = new int[n];
for (int i = 0; i < n; i++)
cnt[i] = i;
int[] s = sa.clone();
for (int i = 0; i < n; i++) {
int s1 = s[i] - len;
if (s1 >= 0)
sa[cnt[classes[s1]]++] = s1;
}
}
return sa;
}
static int[] lcp(int[] sa, String s) {
int n = sa.length;
int[] rank = new int[n];
for (int i = 0; i < n; i++)
rank[sa[i]] = i;
int[] lcp = new int[n - 1];
for (int i = 0, h = 0; i < n; i++) {
if (rank[i] < n - 1) {
for (int j = sa[rank[i] + 1]; Math.max(i, j) + h < s.length()
&& s.charAt(i + h) == s.charAt(j + h); ++h)
;
lcp[rank[i]] = h;
if (h > 0)
--h;
}
}
return lcp;
}
public static void main(String[] args) throws IOException {
int i, j;
FastReader in = new FastReader(System.in);
StringBuilder sb = new StringBuilder();
int t = in.nextInt();
if(t>1e5)
System.out.println(1/0);
int sumn=0,sumq=0;
while (t-- > 0) {
int n = in.nextInt();
String s = in.next();
int q=in.nextInt();
sumn+=n;
sumq+=q;
if(n<=1 || n>5e5 || q>5e5 || s.length()!=n || q<1){
System.out.println(1/0);
}
int suffixArray[] = suffixArray(s);
int lcp[] = lcp(suffixArray, s);
int inv[] = new int[n];
int next[] = new int[n];
int x;
for (i = 0; i < n; i++) {
if (i == 0)
x = lcp[i];
else if (i != n - 1)
x = Math.max(lcp[i - 1], lcp[i]);
else
x = lcp[i - 1];
next[suffixArray[i]] = suffixArray[i] + x;
inv[suffixArray[i]] = i;
}
Integer ind[] = new Integer[n];
for (i = 0; i < n; i++)
ind[i] = i;
Arrays.sort(ind, (a, b) -> Integer.compare(next[a], next[b]));
Integer indq[] = new Integer[q];
int query[][] = new int[q][3];
for (i = 0; i < q; i++) {
indq[i] = i;
query[i][0] = in.nextInt() - 1;
query[i][1] = in.nextInt() - 1;
query[i][2] = in.nextInt();
if(query[i][0]>query[i][1] || query[i][1]>=n || query[i][0]<=-1)
System.out.println(1/0);
if(query[i][2]<1 || query[i][2]>query[i][1]-query[i][0]+1)
System.out.println(1/0);
}
SegmentTreeUNIQUE st = new SegmentTreeUNIQUE(n);
int ans[][] = new int[q][2];
Arrays.sort(indq, (a, b) -> Integer.compare(query[a][1], query[b][1]));
int queryind = 0, nextind = 0;
for (i = 0; i < n; i++) {
while (nextind < n && next[ind[nextind]] == i) {
st.update(ind[nextind], ind[nextind], inv[nextind]);
nextind++;
}
while (queryind < q && query[indq[queryind]][1] == i) {
int z = st.query(query[indq[queryind]][0],
query[indq[queryind]][1] - query[indq[queryind]][2] + 1);
int l = -2, r = -2;
if (z != Integer.MAX_VALUE) {
l = suffixArray[z];
r = Math.max(next[l], l + query[indq[queryind]][2] - 1);
}
ans[indq[queryind]][0] = l + 1;
ans[indq[queryind]][1] = r + 1;
queryind++;
}
}
for (i = 0; i < q; i++)
sb.append(ans[i][0]).append(" ").append(ans[i][1]).append("\n");
}
if(sumn>5e5 || sumq>5e5)
System.out.println(1/0);
System.out.print(sb);
}
}
class SegmentTreeUNIQUE {
int tree[];
int N;
public SegmentTreeUNIQUE(int n) {
N = 1;
while (N<n)
N = N * 2;
tree = new int[2 * N - 1];
Arrays.fill(tree, Integer.MAX_VALUE);
}
public int query(int l, int r) {
return query(0, 0, N - 1, Math.min(l, r), Math.max(l, r));
}
public int query(int i, int s, int e, int l, int r) {
if (l > e || r < s || s > e)
return Integer.MAX_VALUE;
if (s >= l && e <= r) {
return tree[i];
}
int mid = (s + e) / 2;
return Math.min(query(2 * i + 1, s, mid, l, r) ,
query(2 * i + 2, mid + 1, e, l, r));
}
public void update(int l, int r, int v) {
update(0, 0, N - 1, Math.min(l, r), Math.max(l, r), v);
}
public void update(int i, int s, int e, int l, int r, int v) {
if (l > e || r < s || s > e)
return;
if (s >= l && e <= r) {
tree[i]=Math.min(tree[i],v);
return;
}
int mid = (s + e) / 2;
update(2 * i + 1, s, mid, l, r, v);
update(2 * i + 2, mid + 1, e, l, r, v);
tree[i]=Math.min(tree[2*i+1],tree[2*i+2]);
}
}
class FastReader {
byte[] buf = new byte[2048];
int index, total;
InputStream in;
FastReader(InputStream is) {
in = is;
}
int scan() throws IOException {
if (index >= total) {
index = 0;
total = in.read(buf);
if (total <= 0) {
return -1;
}
}
return buf[index++];
}
String next() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c > 32; c = scan()) {
sb.append((char) c);
}
return sb.toString();
}
int nextInt() throws IOException {
int c, val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
long nextLong() throws IOException {
int c;
long val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment