Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- static class BlockProcessor extends AbstractQueryProcessor {
- static final int BLOCK_SIZE = 250;
- int blockSize;
- int blocksCount;
- int[] blocks;
- int blockSideSize;
- int[][] blockSideVertices;
- int[] blockInnerIndexes;
- boolean[][] blockSideActive;
- boolean[][][] blockSidesPathContains;
- long[][][] blockSidesPathDeltas;
- long[][][] blockSidesPathLengths;
- boolean[][][] blockSidesPathInner;
- int[] blockGlobalVertices;
- int[] blockGlobalIndexes;
- int blockGlobalGraphSize;
- Edge[][] blockGlobalGraph;
- long[][] blockGlobalPathLengths;
- public BlockProcessor() {
- this(BLOCK_SIZE);
- }
- public BlockProcessor(int blockSize) {
- this.blockSize = blockSize;
- }
- @Override
- void additionalInit() {
- this.blockSize = min(blockSize, n);
- this.blocks = generateBlocks(m, n, size, vertices, blockSize);
- this.blocksCount = calculateBlocksCount(blocks);
- this.blockSideSize = 2 * m;
- this.blockSideVertices = generateBlockSideVertices(m, n, vertices, blocks, blocksCount, blockSideSize);
- this.blockInnerIndexes = generateBlockInnerIndexes(size, blockSideVertices);
- prepareBlockSidesPaths();
- prepareBlockGlobalGraph();
- prepareBlockGlobalPaths();
- initUpdates();
- }
- void prepareBlockGlobalPaths() {
- this.blockGlobalPathLengths = new long[blockGlobalGraphSize][blockGlobalGraphSize];
- final long[] distances = new long[blockGlobalGraphSize];
- Queue<Vertex> queue = new PriorityQueue<Vertex>(blockGlobalGraphSize * (blockSideSize + 1));
- int[] blockGlobalColorsSeen = new int[blockGlobalGraphSize];
- int[] blockGlobalColorsProcessed = new int[blockGlobalGraphSize];
- int blockGlobalColor = 1;
- for (int start = 0; start < blockGlobalGraphSize; ++start) {
- ++blockGlobalColor;
- blockGlobalColorsSeen[start] = blockGlobalColor;
- distances[start] = 0;
- queue.add(new Vertex(start, distances[start]));
- while (queue.size() > 0) {
- Vertex v = queue.poll();
- int from = v.index;
- if (blockGlobalColorsProcessed[from] == blockGlobalColor) continue;
- long fromDistance = distances[from];
- for (Edge e : blockGlobalGraph[from]) {
- int to = e.to;
- if (blockGlobalColorsSeen[to] != blockGlobalColor) {
- distances[to] = INF;
- blockGlobalColorsSeen[to] = blockGlobalColor;
- }
- if (distances[to] > fromDistance + e.w) {
- distances[to] = fromDistance + e.w;
- queue.add(new Vertex(to, distances[to]));
- }
- }
- blockGlobalColorsProcessed[from] = blockGlobalColor;
- }
- for (int end = 0; end < blockGlobalGraphSize; ++end) {
- blockGlobalPathLengths[start][end] = distances[end];
- }
- }
- }
- void prepareBlockGlobalGraph() {
- this.blockGlobalVertices = generateBlockGlobalVertices(blocksCount, blockSideSize, blockInnerIndexes);
- this.blockGlobalGraphSize = blockGlobalVertices.length;
- this.blockGlobalIndexes = generateBlockGlobalIndexes(size, blockGlobalVertices);
- List<Edge>[] blockGlobalEdgeLists = new List[blockGlobalGraphSize];
- for (int v = 0; v < blockGlobalGraphSize; ++v) {
- blockGlobalEdgeLists[v] = new ArrayList<Edge>();
- }
- for (int i = 0; i < m; ++i) {
- for (int j = 1; j < n - 1; ++j) {
- int cur = vertices[i][j];
- int next = vertices[i][j + 1];
- int curBlock = blocks[cur], nextBlock = blocks[next];
- if (curBlock != nextBlock) {
- int curGlobalVertex = blockGlobalIndexes[cur], nextGlobalVertex = blockGlobalIndexes[next];
- long weight = right[i][j];
- blockGlobalEdgeLists[curGlobalVertex].add(new Edge(nextGlobalVertex, weight));
- blockGlobalEdgeLists[nextGlobalVertex].add(new Edge(curGlobalVertex, weight));
- }
- }
- }
- for (int block = 0; block < blocksCount; ++block) {
- for (int i = 0; i < blockSideSize; ++i) {
- if (!blockSideActive[block][i]) continue;
- int from = blockSideVertices[block][i];
- int fromGlobalVertex = blockGlobalIndexes[from];
- for (int j = 0; j < blockSideSize; ++j) {
- if (!blockSideActive[block][j]) continue;
- int to = blockSideVertices[block][j];
- if (from == to) continue;
- int toGlobalVertex = blockGlobalIndexes[to];
- long weight = blockSidesPathLengths[block][i][j];
- blockGlobalEdgeLists[fromGlobalVertex].add(new Edge(toGlobalVertex, weight));
- }
- }
- }
- this.blockGlobalGraph = new Edge[blockGlobalGraphSize][];
- for (int v = 0; v < blockGlobalGraphSize; ++v) {
- blockGlobalGraph[v] = blockGlobalEdgeLists[v].toArray(new Edge[0]);
- }
- }
- void prepareBlockSidesPaths() {
- this.blockSideActive = new boolean[blocksCount][blockSideSize];
- for (int v = 0; v < size; ++v) {
- int block = blocks[v];
- int sideIndex = blockInnerIndexes[v];
- if (sideIndex != -1) {
- blockSideActive[block][sideIndex] = true;
- }
- }
- this.blockSidesPathDeltas = new long[blocksCount][blockSideSize][blockSideSize];
- this.blockSidesPathContains = new boolean[blockSideSize][blockSideSize][size];
- this.blockSidesPathLengths = new long[blocksCount][blockSideSize][blockSideSize];
- this.blockSidesPathInner = new boolean[blocksCount][blockSideSize][blockSideSize];
- blockInnerDijkstraInit();
- for (int block = 0; block < blocksCount; ++block) {
- int[] blockSide = blockSideVertices[block];
- for (int start : blockSide) {
- int blockInnerIndexStart = blockInnerIndexes[start];
- blockInnerDijkstra(start, START_MODE);
- for (int end : blockSide) {
- int blockInnerIndexEnd = blockInnerIndexes[end];
- blockSidesPathInner[block][blockInnerIndexStart][blockInnerIndexEnd] = (start != end);
- for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {
- if (blockInnerIndexes[cur] != -1) {
- if (cur != end && cur != start) {
- blockSidesPathInner[block][blockInnerIndexStart][blockInnerIndexEnd] = false;
- break;
- }
- }
- }
- blockSidesPathDeltas[block][blockInnerIndexStart][blockInnerIndexEnd] = 0;
- if (blockSidesPathInner[block][blockInnerIndexStart][blockInnerIndexEnd]) {
- blockSidesPathLengths[block][blockInnerIndexStart][blockInnerIndexEnd] = modeDistances[START_MODE][end];
- for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {
- if (blockInnerIndexes[cur] != -1) continue;
- // we only need really inner vertices
- blockSidesPathContains[blockInnerIndexStart][blockInnerIndexEnd][cur] = true;
- }
- } else {
- blockSidesPathLengths[block][blockInnerIndexStart][blockInnerIndexEnd] = INF;
- }
- }
- }
- }
- }
- final int START_MODE = 0, END_MODE = 1;
- long[][] modeDistances;
- int[][] modeParents;
- int[] colorsSeen;
- int[] colorsProcessed;
- int curColor;
- Queue<Vertex>[] modeQueues;
- final long INF = Long.MAX_VALUE / 2;
- class Vertex implements Comparable<Vertex> {
- int index;
- long distance;
- public Vertex(int index, long distance) {
- super();
- this.index = index;
- this.distance = distance;
- }
- @Override
- public int compareTo(Vertex other) {
- long iDistance = distance, jDistance = other.distance;
- return (iDistance < jDistance) ? -1 : ((iDistance > jDistance) ? 1 : 0);
- }
- }
- void blockInnerDijkstraInit() {
- this.modeDistances = new long[2][size];
- this.modeParents = new int[2][size];
- this.colorsSeen = new int[size];
- this.colorsProcessed = new int[size];
- this.curColor = 1;
- this.modeQueues = new Queue[2];
- for (int i = 0; i < 2; ++i) {
- final int mode = i;
- modeQueues[mode] = new PriorityQueue<Vertex>(size);
- }
- }
- void blockInnerDijkstra(int start, int mode) {
- int block = blocks[start];
- ++curColor;
- colorsSeen[start] = curColor;
- long[] distances = modeDistances[mode];
- distances[start] = 0;
- int[] parents = modeParents[mode];
- parents[start] = -1;
- Queue<Vertex> queue = modeQueues[mode];
- queue.add(new Vertex(start, 0));
- while (queue.size() > 0) {
- Vertex v = queue.poll();
- if (colorsProcessed[v.index] == curColor) continue;
- int from = v.index;
- long fromDistance = distances[from];
- for (Edge e : graph[from]) {
- int to = e.to;
- if (blocks[to] != block) continue;
- if (colorsSeen[to] != curColor) {
- distances[to] = INF;
- parents[to] = -1;
- colorsSeen[to] = curColor;
- }
- if (distances[to] > fromDistance + e.w) {
- distances[to] = fromDistance + e.w;
- parents[to] = from;
- queue.add(new Vertex(to, distances[to]));
- }
- }
- colorsProcessed[from] = curColor;
- }
- }
- int[] updateColors;
- int updateCurColor;
- void initUpdates() {
- this.updateColors = new int[size];
- this.updateCurColor = 1;
- }
- @Override
- void updatePath(int start, int end, long delta) {
- ++updateCurColor;
- blockInnerDijkstra(start, START_MODE);
- blockInnerDijkstra(end, END_MODE);
- int startBlock = blocks[start], endBlock = blocks[end];
- long startEndLength = INF;
- int startOptimalSide = -1, endOptimalSide = -1;
- if (startBlock == endBlock) {
- startEndLength = modeDistances[START_MODE][end];
- }
- for (int startSide = 0; startSide < blockSideSize; ++startSide) {
- if (!blockSideActive[startBlock][startSide]) continue;
- int startSideVertex = blockSideVertices[startBlock][startSide];
- long startSideDistance = modeDistances[START_MODE][startSideVertex];
- int startSideGlobalVertex = blockGlobalIndexes[startSideVertex];
- for (int endSide = 0; endSide < blockSideSize; ++endSide) {
- if (!blockSideActive[endBlock][endSide]) continue;
- int endSideVertex = blockSideVertices[endBlock][endSide];
- long endSideDistance = modeDistances[END_MODE][endSideVertex];
- int endSideGlobalVertex = blockGlobalIndexes[endSideVertex];
- long startEndSideDistance = startSideDistance + blockGlobalPathLengths[startSideGlobalVertex][endSideGlobalVertex] + endSideDistance;
- if (startEndSideDistance < startEndLength) {
- startEndLength = startEndSideDistance;
- startOptimalSide = startSide;
- endOptimalSide = endSide;
- }
- }
- }
- if (startOptimalSide == -1 || endOptimalSide == -1) {
- // inner path
- for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {
- vertexValues[cur] += delta;
- }
- } else {
- int startOptimalVertex = blockSideVertices[startBlock][startOptimalSide];
- int startOptimalGlobalVertex = blockGlobalIndexes[startOptimalVertex];
- int endOptimalVertex = blockSideVertices[endBlock][endOptimalSide];
- int endOptimalGlobalVertex = blockGlobalIndexes[endOptimalVertex];
- for (int cur = startOptimalVertex; cur != -1; cur = modeParents[START_MODE][cur]) {
- if (updateColors[cur] == updateCurColor) continue;
- vertexValues[cur] += delta;
- updateColors[cur] = updateCurColor;
- }
- for (int cur = endOptimalVertex; cur != -1; cur = modeParents[END_MODE][cur]) {
- if (updateColors[cur] == updateCurColor) continue;
- vertexValues[cur] += delta;
- updateColors[cur] = updateCurColor;
- }
- long startEndGlobalDistance = blockGlobalPathLengths[startOptimalGlobalVertex][endOptimalGlobalVertex];
- for (int block = 0; block < blocksCount; ++block) {
- for (int startSide = 0; startSide < blockSideSize; ++startSide) {
- if (!blockSideActive[block][startSide]) continue;
- int startVertex = blockSideVertices[block][startSide];
- int startGlobalVertex = blockGlobalIndexes[startVertex];
- long startGlobalDistance = blockGlobalPathLengths[startOptimalGlobalVertex][startGlobalVertex];
- for (int endSide = 0; endSide < blockSideSize; ++endSide) {
- if (!blockSideActive[block][endSide]) continue;
- if (!blockSidesPathInner[block][startSide][endSide]) continue;
- int endVertex = blockSideVertices[block][endSide];
- int endGlobalVertex = blockGlobalIndexes[endVertex];
- long endGlobalDistance = blockGlobalPathLengths[endGlobalVertex][endOptimalGlobalVertex];
- long startEndInnerDistance = blockSidesPathLengths[block][startSide][endSide];///[startGlobalVertex][endGlobalVertex];
- if (startGlobalDistance + startEndInnerDistance + endGlobalDistance == startEndGlobalDistance) {
- blockSidesPathDeltas[block][startSide][endSide] += delta;
- if (updateColors[startVertex] != updateCurColor) {
- updateColors[startVertex] = updateCurColor;
- vertexValues[startVertex] += delta;
- }
- if (updateColors[endVertex] != updateCurColor) {
- updateColors[endVertex] = updateCurColor;
- vertexValues[endVertex] += delta;
- }
- }
- }
- }
- }
- }
- }
- @Override
- long getVertexValue(int v) {
- long value = 0;
- int block = blocks[v];
- for (int start = 0; start < blockSideSize; ++start) {
- for (int end = 0; end < blockSideSize; ++end) {
- if (blockSidesPathInner[block][start][end] && blockSidesPathContains[start][end][v]) {
- value += blockSidesPathDeltas[block][start][end];
- }
- }
- }
- return value;
- }
- }
- static int[] generateBlockGlobalIndexes(int size, int[] blockGlobalVertices) {
- int[] blockGlobalIndexes = new int[size];
- Arrays.fill(blockGlobalIndexes, -1);
- for (int index = 0; index < blockGlobalVertices.length; ++index) {
- blockGlobalIndexes[blockGlobalVertices[index]] = index;
- }
- return blockGlobalIndexes;
- }
- static int[] generateBlockGlobalVertices(int blocksCount, int blockSideSize, int[] blockInnerIndexes) {
- List<Integer> blockGlobalVertices = new ArrayList<Integer>();
- for (int v = 0; v < blockInnerIndexes.length; ++v) {
- if (blockInnerIndexes[v] != -1) {
- blockGlobalVertices.add(v);
- }
- }
- return castInt(blockGlobalVertices);
- }
- static int[] generateBlockInnerIndexes(int size, int[][] blockSideVertices) {
- int[] blockInnerIndexes = new int[size];
- Arrays.fill(blockInnerIndexes, -1);
- for (int[] blockSide : blockSideVertices) {
- for (int index = 0; index < blockSide.length; ++index) {
- blockInnerIndexes[blockSide[index]] = index;
- }
- }
- return blockInnerIndexes;
- }
- static int[][] generateBlockSideVertices(int m, int n, int[][] vertices, int[] blocks, int blocksCount, int blockSideSize) {
- int[][] blockSideVertices = new int[blocksCount][blockSideSize];
- int[] blockSizes = new int[blocksCount];
- for (int i = 0; i < m; ++i) {
- for (int j = 0; j < n; ++j) {
- int cur = vertices[i][j];
- int curBlock = blocks[cur];
- if (j == 0 || j == n - 1) {
- blockSideVertices[curBlock][blockSizes[curBlock]++] = cur;
- // it is more comfortable to have block sides of length 6 every time, even when n == 1
- if (n - 1 == 0) {
- blockSideVertices[curBlock][blockSizes[curBlock]++] = cur;
- }
- } else {
- int next = vertices[i][j + 1];
- int nextBlock = blocks[next];
- if (curBlock != nextBlock) {
- blockSideVertices[curBlock][blockSizes[curBlock]++] = cur;
- blockSideVertices[nextBlock][blockSizes[nextBlock]++] = next;
- }
- }
- }
- }
- return blockSideVertices;
- }
- static int[] generateBlocks(int m, int n, int size, int[][] vertices, int blockSize) {
- int[] blocks = new int[size];
- for (int i = 0; i < m; ++i) {
- for (int j = 0; j < n; ++j) {
- int v = vertices[i][j];
- blocks[v] = j / blockSize;
- }
- }
- return blocks;
- }
- static int calculateBlocksCount(int[] blocks) {
- return getMinMax(blocks).y + 1;
- }
- interface QueryProcessor {
- QueryProcessor init(int m, int n, long[][] down, long[][] right);
- void update(int i1, int j1, int i2, int j2, long delta);
- long get(int i, int j);
- }
- static abstract class AbstractQueryProcessor implements QueryProcessor {
- int m, n;
- long[][] down;
- long[][] right;
- int size;
- int[][] vertices;
- Edge[][] graph;
- long[] vertexValues;
- @Override
- public QueryProcessor init(int m, int n, long[][] down, long[][] right) {
- this.m = m;
- this.n = n;
- this.down = down;
- this.right = right;
- this.size = m * n;
- this.vertices = generateIndexes(m, n);
- this.graph = generateMatrixGraph(m, n, size, vertices, down, right);
- this.vertexValues = new long[size];
- additionalInit();
- return this;
- }
- abstract void additionalInit();
- @Override
- public void update(int i1, int j1, int i2, int j2, long delta) {
- updatePath(vertices[i1][j1], vertices[i2][j2], delta);
- }
- abstract void updatePath(int from, int to, long delta);
- @Override
- public long get(int i, int j) {
- int v = vertices[i][j];
- return vertexValues[v] + getVertexValue(v);
- }
- abstract long getVertexValue(int v);
- }
- static int[][] generateIndexes(int m, int n) {
- int[][] indexes = new int[m][n];
- for (int i = 0, index = 0; i < m; ++i) {
- for (int j = 0; j < n; ++j, ++index) {
- indexes[i][j] = index;
- }
- }
- return indexes;
- }
- static Edge[][] generateMatrixGraph(int m, int n, int size, int[][] vertices, long[][] down, long[][] right) {
- List<Edge>[] edgeLists = new List[size];
- for (int v = 0; v < size; ++v) {
- edgeLists[v] = new ArrayList<Edge>();
- }
- for (int i = 0; i < m - 1; ++i) {
- for (int j = 0; j < n; ++j) {
- int from = vertices[i][j];
- int to = vertices[i + 1][j];
- long weight = down[i][j];
- edgeLists[from].add(new Edge(to, weight));
- edgeLists[to].add(new Edge(from, weight));
- }
- }
- for (int i = 0; i < m; ++i) {
- for (int j = 0; j < n - 1; ++j) {
- int from = vertices[i][j];
- int to = vertices[i][j + 1];
- long weight = right[i][j];
- edgeLists[from].add(new Edge(to, weight));
- edgeLists[to].add(new Edge(from, weight));
- }
- }
- Edge[][] graph = new Edge[size][];
- for (int v = 0; v < size; ++v) {
- graph[v] = edgeLists[v].toArray(new Edge[0]);
- }
- return graph;
- }
Advertisement
Add Comment
Please, Sign In to add comment