0_0_38553994_28392\Main.java:1: ´íÎó: ÀàÖظ´: LazyRangeSegmentTree_Tree_Lazy_long
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(); final int M = 1000000007; int n = input.nextInt(); Tree[] elements = new Tree[n]; for (int i = 0; i < n; i++) { int a = input.nextInt(); int b = input.nextInt(); elements[i] = new Tree(a, b, (int)((long)a * a % M), (int)((long)a * b % M), (int)((long)b * b % M)); } LazyRangeSegmentTree_Tree_Lazy_long segmentTree = new LazyRangeSegmentTree_Tree_Lazy_long(elements, 0, (tree, lazy, from, length) -> new Tree((int)(((long)tree.a * lazy.x1 + (long)tree.b * lazy.x2 + (long)length * lazy.x3) % M), (int)(((long)tree.a * lazy.x4 + (long)tree.b * lazy.x5 + (long)length * lazy.x6) % M), (int)((2 * ((long)tree.a * lazy.x1 % M * lazy.x3 + (long)tree.b * lazy.x2 % M * lazy.x3 + (long)tree.ab * lazy.x1 % M * lazy.x2) + (long)tree.a2 * lazy.x1 % M * lazy.x1 + (long)tree.b2 * lazy.x2 % M * lazy.x2 + (long)length * lazy.x3 % M * lazy.x3) % M), (int)((tree.a * (((long)lazy.x1 * lazy.x6 + (long)lazy.x3 * lazy.x4) % M) + tree.b * (((long)lazy.x2 * lazy.x6 + (long)lazy.x3 * lazy.x5) % M) + tree.ab * (((long)lazy.x1 * lazy.x5 + (long)lazy.x2 * lazy.x4) % M) + (long)tree.a2 * lazy.x1 % M * lazy.x4 + (long)tree.b2 * lazy.x2 % M * lazy.x5 + (long)length * lazy.x3 % M * lazy.x6) % M), (int)((2 * ((long)tree.a * lazy.x4 % M * lazy.x6 + (long)tree.b * lazy.x5 % M * lazy.x6 + (long)tree.ab * lazy.x4 % M * lazy.x5) + (long)tree.a2 * lazy.x4 % M * lazy.x4 + (long)tree.b2 * lazy.x5 % M * lazy.x5 + (long)length * lazy.x6 % M * lazy.x6) % M)), tree -> tree.ab, (x, y) -> new Tree((x.a + y.a) % M, (x.b + y.b) % M, (x.a2 + y.a2) % M, (x.ab + y.ab) % M, (x.b2 + y.b2) % M), (a, b) -> new Lazy((int)(((long)a.x1 * b.x1 + (long)a.x4 * b.x2) % M), (int)(((long)a.x2 * b.x1 + (long)a.x5 * b.x2) % M), (int)(((long)a.x3 * b.x1 + (long)a.x6 * b.x2 + b.x3) % M), (int)(((long)a.x1 * b.x4 + (long)a.x4 * b.x5) % M), (int)(((long)a.x2 * b.x4 + (long)a.x5 * b.x5) % M), (int)(((long)a.x3 * b.x4 + (long)a.x6 * b.x5 + b.x6) % M)), Long::sum); for (int i = input.nextInt(); i > 0; i--) { int type = input.nextInt(); if (type == 1) { int tag = input.nextInt(); int l = input.nextInt() - 1; int r = input.nextInt(); int x = input.nextInt(); segmentTree.update(l, r, tag == 0 ? new Lazy(1, 0, x, 0, 1, 0) : new Lazy(1, 0, 0, 0, 1, x)); } else { int l = input.nextInt() - 1; int r = input.nextInt(); if (type != 4) segmentTree.update(l, r, type == 2 ? new Lazy(3, 2, 0, 3, -2, 0) : new Lazy(0, 1, 0, 1, 0, 0)); else output.append(segmentTree.query(l, r) % M).appendNewLine(); } } output.flush(); } } class Tree { final int a; final int b; final int a2; final int ab; final int b2; public Tree(int a, int b, int a2, int ab, int b2) { this.a = a; this.b = b; this.a2 = a2; this.ab = ab; this.b2 = b2; } } class Lazy { final int x1; final int x2; final int x3; final int x4; final int x5; final int x6; public Lazy(int x1, int x2, int x3, int x4, int x5, int x6) { this.x1 = x1; this.x2 = x2; this.x3 = x3; this.x4 = x4; this.x5 = x5; this.x6 = x6; } } class LazyRangeSegmentTree_Tree_Lazy_long { private final int height; private final Tree[] tree; private final Lazy[] lazy; private final long defaultValue; private final Function_Tree_Tree_Lazy_int_int lazyToTree; private final Function_long_Tree treeToQuery; private final Function_Tree_Tree_Tree treeMerge; private final Function_Lazy_Lazy_Lazy lazyMerge; private final Function_long_long_long queryMerge; public LazyRangeSegmentTree_Tree_Lazy_long(Tree[] elements, long defaultValue, Function_Tree_Tree_Lazy_int_int lazyToTree, Function_long_Tree treeToQuery, Function_Tree_Tree_Tree treeMerge, Function_Lazy_Lazy_Lazy lazyMerge, Function_long_long_long queryMerge) { height = Algebra_int.ceilLog2(elements.length); tree = new Tree[elements.length << 1]; System.arraycopy(elements, 0, tree, elements.length, elements.length); for (int i = elements.length - 1; i > 0; i--) tree[i] = treeMerge.apply(tree[i << 1], tree[i << 1 | 1]); lazy = new Lazy[elements.length]; this.defaultValue = defaultValue; this.lazyToTree = lazyToTree; this.treeToQuery = treeToQuery; this.treeMerge = treeMerge; this.lazyMerge = lazyMerge; this.queryMerge = queryMerge; } public long query(int from, int to) { push(from += lazy.length); push((to += lazy.length) - 1); long result = 0; for (; from < to; from >>= 1, to >>= 1) { if ((from & 1) != 0) result += tree[from++].ab; if ((to & 1) != 0) result += tree[--to].ab; } return result; } public void update(int from, int to, Lazy value) { int left = from += lazy.length; int right = (to += lazy.length) - 1; push(left); push(right); for (int i = 0; from < to; from >>= 1, to >>= 1, i++) { if ((from & 1) != 0) apply(from++, value, i); if ((to & 1) != 0) apply(--to, value, i); } build(left); build(right); } private void push(int index) { for (int i = height; i > 0; i--) { int prefix = index >> i; propagate(prefix, i); } } private void propagate(int index, int scale) { if (lazy[index] != null) { apply(index << 1, lazy[index], scale - 1); apply(index << 1 | 1, lazy[index], scale - 1); lazy[index] = null; } } private void apply(int index, Lazy value, int scale) { mergeToTree(index, value, scale); if (index < lazy.length) lazy[index] = lazy[index] == null ? value : lazyMerge.apply(lazy[index], value); } private void build(int index) { index >>= 1; for (int i = 1; index != 0; index >>= 1, i++) { tree[index] = treeMerge.apply(tree[index << 1], tree[index << 1 | 1]); if (lazy[index] != null) mergeToTree(index, lazy[index], i); } } private void mergeToTree(int index, Lazy value, int scale) { tree[index] = lazyToTree.apply(tree[index], value, (index << scale) - lazy.length, 1 << scale); } } 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; } } interface Function_boolean_int { boolean apply(int arg1); } interface Function_Lazy_Lazy_Lazy { Lazy apply(Lazy arg1, Lazy arg2); } interface Function_long_long_long { long apply(long arg1, long arg2); } interface Function_long_Tree { long apply(Tree arg1); } interface Function_Tree_Tree_Lazy_int_int { Tree apply(Tree arg1, Lazy arg2, int arg3, int arg4); } interface Function_Tree_Tree_Tree { Tree apply(Tree arg1, Tree arg2); } 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[
|
