0_0_38550248_29128\Main.java:1: 错误: 无法推断Iterator<E>的类型参数
import java.util.Iterator; public class Main { public static void main(String[] args) { A.main(args); } } class A { public static void main(String[] args) { Input input = new Input(); Output output = new Output(); byte[][] strings = new byte[input.nextInt()][]; for (int i = 0; i < strings.length; i++) strings[i] = input.next(); int length = 0; for (byte[] string: strings) length += string.length; if (length > 2000000) throw new RuntimeException(); for (int i = 0; i < strings.length; i++) { byte[] s = strings[i]; BidirectionalHash hash = new BidirectionalHash(s); SegmentTree_int segmentTree = new SegmentTree_int(new int[s.length], 0, Integer::sum); Heap_Pair heap = new Heap_Pair(s.length, (a, b) -> Integer.compare(a.pos, b.pos), new FieldAccess_Pair_int() { public int get(Pair t) { return t.index; } public void set(Pair t, int v) { t.index = v; } }); long count = 0; for (int j = 0; j < s.length; j++) { int finalJ = j; int radius = Algebra_int.maxBinarySearch(r -> hash.getFront(finalJ - r, finalJ) == hash.getBack(finalJ + 1, finalJ + 1 + r), 0, Math.min(j, s.length - 1 - j)); heap.offer(new Pair(j + radius, j)); segmentTree.set(j, 1); while (heap.size() > 0 && heap.peek().pos < j) segmentTree.set(heap.poll().value, 0); count += segmentTree.get(j - radius, j); } output.append(count).appendNewLine(); } output.flush(); } } class Pair { final int pos; final int value; int index; public Pair(int pos, int value) { this.pos = pos; this.value = value; } } class Algebra_int { private Algebra_int() {} public static int sq(int n) { return (int)n * n; } public static int cb(int n) { return (int)n * n * n; } public static int pow(int a, int b) { int result = 1; for (int i = 0; i < b; i++) result *= a; return result; } public static int gcd(int a, int b) { while (b != 0) { int remainder = a % b; a = b; b = remainder; } return a; } public static int[] gcdex(int a, int b) { int x1 = 1; int x2 = 0; int y1 = 0; int y2 = 1; while (b != 0) { int quotient = a / b; int c = a - quotient * b; a = b; b = c; int x3 = x1 - quotient * x2; x1 = x2; x2 = x3; int y3 = y1 - quotient * y2; y1 = y2; y2 = y3; } return new int[]{x1, y1, a}; } public static int log2(int n) { return Integer.SIZE - 1 - Integer.numberOfLeadingZeros(n); } public static int ceilLog2(int n) { return Integer.SIZE - Integer.numberOfLeadingZeros(n - 1); } public static int minBinarySearch(Function_boolean_int predicate, int lower, int upper) { while (lower < upper) { int mid = lower + upper >> 1; if (predicate.apply(mid)) upper = mid; else lower = mid + 1; } return lower; } public static int maxBinarySearch(Function_boolean_int predicate, int lower, int upper) { while (lower < upper) { int mid = lower + upper + 1 >> 1; if (predicate.apply(mid)) lower = mid; else upper = mid - 1; } return lower; } } class BidirectionalHash { private final LongHash hash; private final int[] frontHashes; private final int[] backHashes; private final int[] powB; public BidirectionalHash(byte[] bytes) { this(new LongHash() { protected int B() { return 263; } protected int M() { return 1080565819; } }, bytes); } public BidirectionalHash(LongHash hash, byte[] bytes) { this.hash = hash; frontHashes = new int[bytes.length + 1]; backHashes = new int[frontHashes.length]; powB = new int[frontHashes.length]; for (int i = 0; i < bytes.length; i++) frontHashes[i + 1] = hash.update(frontHashes[i], bytes[i]); for (int i = bytes.length - 1; i >= 0; i--) backHashes[i] = hash.update(backHashes[i + 1], bytes[i]); powB[0] = 1; for (int i = 1; i <= bytes.length; i++) powB[i] = (int)(powB[i - 1] * (long)hash.B() % hash.M()); } public int getFront(int from, int to) { int frontHash = frontHashes[to] - (int)(frontHashes[from] * (long)powB[to - from] % hash.M()); return frontHash < 0 ? frontHash + hash.M() : frontHash; } public int getBack(int from, int to) { int backHash = backHashes[from] - (int)(backHashes[to] * (long)powB[to - from] % hash.M()); return backHash < 0 ? backHash + hash.M() : backHash; } } interface FieldAccess_Pair_int { int get(Pair t); void set(Pair t, int v); } interface Function_boolean_int { boolean apply(int arg1); } interface Function_int_int_int { int apply(int arg1, int arg2); } interface Function_int_Pair_Pair { int apply(Pair arg1, Pair arg2); } class Heap_Pair implements Iterable<Pair> { private final Pair[] heap; private final Function_int_Pair_Pair comparator; private final FieldAccess_Pair_int index; private int size; public Heap_Pair(int n, Function_int_Pair_Pair comparator, FieldAccess_Pair_int index) { heap = new Pair[Integer.highestOneBit(n) << 1]; this.comparator = comparator; this.index = index; } public int size() { return size; } public Iterator<Pair> iterator() { return new Iterator<>() { private int index; public boolean hasNext() { return index != size; } public Pair next() { return heap[++index]; } }; } public void offer(Pair e) { siftUp(++size, e); } public void decrease(Pair e) { siftUp(index.get(e), e); } private void siftUp(int index, Pair e) { for (int i = index, j = index >> 1; ; i = j, j >>= 1) { if (j == 0 || comparator.apply(heap[j], e) <= 0) { set(i, e); break; } else set(i, heap[j]); } } public Pair poll() { Pair e = heap[1]; siftDown(1, heap[size--]); return e; } public void increase(Pair e) { siftDown(index.get(e), e); } private void siftDown(int index, Pair e) { for (int i = index; ; ) { int left = i << 1; int right = left | 1; if (right > size) { if (left > size || comparator.apply(e, heap[left]) <= 0) set(i, e); else { set(i, heap[left]); set(left, e); } break; } else { if (comparator.apply(heap[left], heap[right]) < 0) { if (comparator.apply(heap[left], e) < 0) { set(i, heap[left]); i = left; } else { set(i, e); break; } } else { if (comparator.apply(heap[right], e) < 0) { set(i, heap[right]); i = right; } else { set(i, e); break; } } } } } private void set(int index, Pair e) { heap[index] = e; this.index.set(e, index); } public Pair peek() { return heap[1]; } public void remove(Pair e) { for (int i = index.get(e), j = i >> 1; j != 0; i = j, j >>= 1) set(i, heap[j]); siftDown(1, heap[size--]); } public void clear() { size = 0; } } class Input { private final byte[] buffer; private int pos; public Input() { try { buffer = new byte[System.in.available() + 1]; buffer[buffer.length - 1] = '\n'; System.in.read(buffer); } catch (Exception ex) { throw new RuntimeException(ex); } } public byte[] next(int n) { while (true) { byte b = buffer[pos++]; if (b != '\n' && b != '\r') { pos--; break; } } byte[] bytes = new byte[n]; System.arraycopy(buffer, pos, bytes, 0, n); pos += n; return bytes; } public byte[] next() { int from; while (true) { byte b = buffer[pos++]; if (b != ' ' && b != '\n' && b != '\r') { from = pos; break; } } byte[] bytes; while (true) { byte b = buffer[pos++]; if (b == ' ' || b == '\n') { bytes = new byte[pos - from]; break; } else if (b == '\r') { bytes = new byte[pos++ - from]; break; } } System.arraycopy(buffer, from - 1, bytes, 0, bytes.length); return bytes; } public byte[] nextLine() { int from = pos; byte[] bytes; while (true) { byte b = buffer[pos++]; if (b == '\n') { bytes = new byte[pos - from - 1]; break; } else if (b == '\r') { bytes = new byte[pos++ - from - 1]; break; } } System.arraycopy(buffer, from, bytes, 0, bytes.length); return bytes; } public byte nextChar() { while (true) { byte b = buffer[pos++]; if (b != ' ' && b != '\n' && b != '\r') return b; } } public int nextInt() { int n; boolean positive; while (true) { byte b = buffer[pos++]; if (b == '-') { positive = false; n = buffer[pos++] - '0'; break; } else if (b >= '0' && b <= '9') { positive = true; n = b - '0'; break; } } while (true) { byte b = buffer[pos++]; if (b >= '0' && b <= '9') n = n * 10 + b - '0'; else { if (b == '\r') pos++; return positive ? n : -n; } } } public long nextLong() { long n; boolean positive; while (true) { byte b = buffer[pos++]; if (b == '-') { positive = false; n = buffer[pos++] - '0'; break; } else if (b >= '0' && b <= '9') { positive = true; n = b - '0'; break; } } while (true) { byte b = buffer[pos++]; if (b >= '0' && b <= '9') n = n * 10 + b - '0'; else { if (b == '\r') pos++; return positive ? n : -n; } } } public double nextDouble() { long n; boolean positive; while (true) { byte b = buffer[pos++]; if (b == '-') { positive = false; n = buffer[pos++] - '0'; break; } else if (b >= '0' && b <= '9') { positive = true; n = b - '0'; break; } } while (true) { byte b = buffer[pos++]; if (b >= '0' && b <= '9') n = n * 10 + b - '0'; else if (b == '.') break; else return positive ? n : -n; } long m = 0; long o = 1; while (true) { byte b = buffer[pos++]; if (b >= '0' && b <= '9') { m = m * 10 + b - '0'; o *= 10; } else { if (b == '\r') pos++; double d = n + (double)m / o; return positive ? d : -d; } } } public int[] nextInts(int n) { int[] ints = new int[n]; for (int i = 0; i < n; i++) ints[i] = nextInt(); return ints; } public long[] nextLongs(int n) { long[] longs = new long[n]; for (int i = 0; i < n; i++) longs[i] = nextLong(); return longs; } } abstract class LongHash { private int significance; protected abstract int B(); protected abstract int M(); public int hash(byte[] bytes) { return hash(bytes, bytes.length); } public int hash(byte[] bytes, int length) { int hash = 0; for (int i = 0; i < length; i++) hash = (int)((hash * (long)B() + bytes[i]) % M()); return hash; } public int hash(byte[] bytes, int offset, int length) { int hash = 0; for (int i = 0; i < length; i++) hash = (int)((hash * (long)B() + bytes[offset + i]) % M()); return hash; } public int update(int hash, byte b) { return (int)((hash * (long)B() + b) % M()); } public int shift(int hash, byte add, byte drop) { hash -= drop * (long)significance % M(); if (hash < 0) hash += M(); return (int)((hash * (long)B() + add) % M()); } public void setLength(int length) { significance = 1; for (long i = 1, j = B(); i <= length - 1; i <<= 1, j = j * j % M()) { if ((i & length - 1) != 0) significance = (int)(significance * j % M()); } } } class Output { private static final int BUFFER_SIZE = 1048576; private static final boolean CRLF = System.lineSeparator().equals("\r\n"); private final byte[] buffer = new byte[BUFFER_SIZE]; private int pos; public Outpu
|
