Guest User

Untitled

a guest
Sep 12th, 2017
126
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.         static class FenwickTree {
  2.            
  3.             int size;
  4.             long[] tree;
  5.            
  6.             FenwickTree(int n) {
  7.                 size = n + 1;
  8.                 tree = new long[size + 1];
  9.             }
  10.            
  11.             void inc(int left, int right, long delta) {
  12.                 update(left, delta);
  13.                 update(right + 1, -delta);
  14.             }
  15.            
  16.             void update(int index, long delta) {
  17.                 for (; index < size; index |= (index + 1)) {
  18.                     tree[index] += delta;
  19.                 }
  20.             }
  21.            
  22.             long get(int v) {
  23.                 long sum = 0;
  24.                 for (; v >= 0; v &= (v + 1), --v) {
  25.                     sum += tree[v];
  26.                 }
  27.                 return sum;
  28.             }
  29.         }
  30.        
  31.         static class MainPathProcessor extends AbstractQueryProcessor {
  32.            
  33.             int[] mainPathIndexes;
  34.             long[] mainPathDistances;
  35.             FenwickTree tree;
  36.            
  37.             @Override
  38.             void additionalInit() {
  39.                 dijkstraInit();
  40.                
  41.                 mainPathInit();
  42.                 initUpdates();
  43.             }
  44.            
  45.             void mainPathInit() {
  46.                 this.mainPathIndexes = new int[size];
  47.                 Arrays.fill(mainPathIndexes, -1);
  48.                
  49.                 this.mainPathDistances = new long[size];
  50.                 Arrays.fill(mainPathDistances, INF);
  51.                
  52.                 int start = vertices[0][0], end = vertices[m - 1][n - 1];
  53.                 dijkstra(start, end, START_MODE, size + 1);
  54.                
  55.                 List<Integer> path = new ArrayList<Integer>();
  56.                 for (int cur = end; cur != -1; cur = modeParents[START_MODE][cur]) {
  57.                     path.add(cur);
  58.                 }
  59.                
  60.                 Collections.reverse(path);
  61.                 for (int index = 0; index < path.size(); ++index) {
  62.                     int v = path.get(index);
  63.                     mainPathIndexes[v] = index;
  64.                     mainPathDistances[v] = modeDistances[START_MODE][v];
  65.                 }
  66.                
  67.                 this.tree = new FenwickTree(path.size());
  68.             }
  69.            
  70.             final int START_MODE = 0, END_MODE = 1;
  71.            
  72.             long[][] modeDistances;
  73.             int[][] modeParents;
  74.             int[][] modeSteps;
  75.            
  76.             int[] colorsSeen;
  77.             int[] colorsProcessed;
  78.             int curColor;
  79.            
  80.             Queue<Vertex>[] modeQueues;
  81.            
  82.             final long INF = Long.MAX_VALUE / 2 - 1000L * 1000 * 1000 * 1000 * 1000;
  83.            
  84.             class Vertex implements Comparable<Vertex> {
  85.                 int index;
  86.                 long distance;
  87.                 public Vertex(int index, long distance) {
  88.                     super();
  89.                     this.index = index;
  90.                     this.distance = distance;
  91.                 }
  92.                 @Override
  93.                 public int compareTo(Vertex other) {
  94.                     long iDistance = distance, jDistance = other.distance;
  95.                     return (iDistance < jDistance) ? -1 : ((iDistance > jDistance) ? 1 : 0);
  96.                 }
  97.             }
  98.            
  99.             void dijkstraInit() {
  100.                 this.modeDistances = new long[2][size];
  101.                 this.modeParents = new int[2][size];
  102.                 this.modeSteps = new int[2][size];
  103.                
  104.                 this.colorsSeen = new int[size];
  105.                 this.colorsProcessed = new int[size];
  106.                 this.curColor = 1;
  107.                
  108.                 this.modeQueues = new Queue[2];
  109.                 for (int i = 0; i < 2; ++i) {
  110.                     final int mode = i;
  111.                     modeQueues[mode] = new PriorityQueue<Vertex>(size);
  112.                 }
  113.             }
  114.            
  115.             List<Integer> dijkstra(int start, int end, int mode, int maxSteps) {
  116.                 ++curColor;
  117.                 colorsSeen[start] = curColor;
  118.                
  119.                 long[] distances = modeDistances[mode];
  120.                 distances[start] = 0;
  121.                
  122.                 int[] parents = modeParents[mode];
  123.                 parents[start] = -1;
  124.                
  125.                 int[] steps = modeSteps[mode];
  126.                 steps[start] = 0;
  127.                
  128.                 Queue<Vertex> queue = modeQueues[mode];
  129.                 queue.clear();
  130.                 queue.add(new Vertex(start, 0));
  131.                
  132.                 List<Integer> neighbors = new ArrayList<Integer>();
  133.                 while (queue.size() > 0) {
  134.                    
  135.                     Vertex v = queue.poll();
  136.                     if (colorsProcessed[v.index] == curColor) continue;
  137.                    
  138.                     int from = v.index;
  139.                     neighbors.add(from);
  140.                    
  141.                     if (steps[from] == maxSteps) continue;
  142.                    
  143.                     long fromDistance = distances[from];
  144.                     for (Edge e : graph[from]) {
  145.                         int to = e.to;
  146.                        
  147.                         if (colorsSeen[to] != curColor) {
  148.                             distances[to] = INF;
  149.                             parents[to] = -1;
  150.                             steps[to] = 0;
  151.                             colorsSeen[to] = curColor;
  152.                         }
  153.                        
  154.                         if (distances[to] > fromDistance + e.w) {
  155.                             distances[to] = fromDistance + e.w;
  156.                             parents[to] = from;
  157.                             steps[to] = steps[from] + 1;
  158.                             queue.add(new Vertex(to, distances[to]));
  159.                         }
  160.                     }
  161.                    
  162.                     colorsProcessed[from] = curColor;
  163.                 }
  164.                
  165.                 return neighbors;
  166.             }
  167.            
  168.             int[] updateColors;
  169.             int updateCurColor;
  170.            
  171.             void initUpdates() {
  172.                 this.updateColors = new int[size];
  173.                 this.updateCurColor = 1;
  174.             }
  175.            
  176.             final int UPDATE_DIJKSTRA_MAX_STEPS = 50;
  177.            
  178.             @Override
  179.             void updatePath(int start, int end, long delta) {
  180.                 ++updateCurColor;
  181.                
  182.                 List<Integer> startNeighbors = dijkstra(start, end, START_MODE, UPDATE_DIJKSTRA_MAX_STEPS);
  183.                 List<Integer> endNeighbors = dijkstra(end, start, END_MODE, UPDATE_DIJKSTRA_MAX_STEPS);
  184.                
  185.                 int optimalStartEnd = -1, optimalEndEnd = -1;
  186.                 long optimalDistance = INF;
  187.                
  188.                 for (int startEnd : startNeighbors) {
  189.                     long startDistance = modeDistances[START_MODE][startEnd];
  190.                     int startPathIndex = mainPathIndexes[startEnd];
  191.                    
  192.                     for (int endEnd : endNeighbors) {
  193.                         long endDistance = modeDistances[END_MODE][endEnd];
  194.                         int endPathIndex = mainPathIndexes[endEnd];
  195.                        
  196.                         if (startEnd == endEnd) {
  197.                             if (optimalDistance > startDistance + endDistance) {
  198.                                 optimalDistance = startDistance + endDistance;
  199.                                 optimalStartEnd = startEnd;
  200.                                 optimalEndEnd = endEnd;
  201.                             }
  202.                         } else {
  203.                             if (startPathIndex != -1 && endPathIndex != -1) {
  204.                                 long totalDistance = startDistance + Math.abs(mainPathDistances[startEnd] - mainPathDistances[endEnd]) + endDistance;
  205.                                 if (optimalDistance > totalDistance) {
  206.                                     optimalDistance = totalDistance;
  207.                                     optimalStartEnd = startEnd;
  208.                                     optimalEndEnd = endEnd;
  209.                                 }
  210.                             }
  211.                         }
  212.                     }
  213.                 }
  214.                
  215.                 if (optimalDistance == INF) {
  216.                     throw new UnsupportedOperationException();
  217.                 }
  218.                
  219.                 if (optimalStartEnd == optimalEndEnd) {
  220.                     for (int cur = optimalStartEnd; cur != -1; cur = modeParents[START_MODE][cur]) {
  221.                         if (updateColors[cur] == updateCurColor) continue;
  222.                         updateColors[cur] = updateCurColor;
  223.                         vertexValues[cur] += delta;
  224.                     }
  225.                    
  226.                     for (int cur = optimalEndEnd; cur != -1; cur = modeParents[END_MODE][cur]) {
  227.                         if (updateColors[cur] == updateCurColor) continue;
  228.                         updateColors[cur] = updateCurColor;
  229.                         vertexValues[cur] += delta;
  230.                     }
  231.                 } else {
  232.                     for (int cur = modeParents[START_MODE][optimalStartEnd]; cur != -1; cur = modeParents[START_MODE][cur]) {
  233.                         if (updateColors[cur] == updateCurColor) continue;
  234.                         updateColors[cur] = updateCurColor;
  235.                         vertexValues[cur] += delta;
  236.                     }
  237.                    
  238.                     for (int cur = modeParents[END_MODE][optimalEndEnd]; cur != -1; cur = modeParents[END_MODE][cur]) {
  239.                         if (updateColors[cur] == updateCurColor) continue;
  240.                         updateColors[cur] = updateCurColor;
  241.                         vertexValues[cur] += delta;
  242.                     }
  243.                    
  244.                     int startPathIndex = mainPathIndexes[optimalStartEnd];
  245.                     int endPathIndex = mainPathIndexes[optimalEndEnd];
  246.                    
  247.                     if (startPathIndex > endPathIndex) {
  248.                         int tmp = startPathIndex;
  249.                         startPathIndex = endPathIndex;
  250.                         endPathIndex = tmp;
  251.                     }
  252.                    
  253.                     tree.inc(startPathIndex, endPathIndex, delta);
  254.                 }
  255.             }
  256.            
  257.             @Override
  258.             long getVertexValue(int v) {
  259.                 long value = 0;
  260.                
  261.                 int mainPathIndex = mainPathIndexes[v];
  262.                 if (mainPathIndex != -1) {
  263.                     value = tree.get(mainPathIndex);
  264.                 }
  265.                
  266.                 return value;
  267.             }
  268.         }
  269.        
  270.         interface QueryProcessor {
  271.            
  272.             QueryProcessor init(int m, int n, long[][] down, long[][] right);
  273.            
  274.             void update(int i1, int j1, int i2, int j2, long delta);
  275.             long get(int i, int j);
  276.         }
  277.        
  278.         static abstract class AbstractQueryProcessor implements QueryProcessor {
  279.            
  280.             int m, n;
  281.             long[][] down;
  282.             long[][] right;
  283.            
  284.             int size;
  285.             int[][] vertices;
  286.            
  287.             Edge[][] graph;
  288.            
  289.             long[] vertexValues;
  290.            
  291.             @Override
  292.             public QueryProcessor init(int m, int n, long[][] down, long[][] right) {
  293.                 this.m = m;
  294.                 this.n = n;
  295.                
  296.                 this.down = down;
  297.                 this.right = right;
  298.      
  299.                 this.size = m * n;
  300.                 this.vertices = generateIndexes(m, n);
  301.                 this.graph = generateMatrixGraph(m, n, size, vertices, down, right);
  302.                
  303.                 this.vertexValues = new long[size];
  304.                
  305.                 additionalInit();
  306.                
  307.                 return this;
  308.             }
  309.            
  310.             abstract void additionalInit();
  311.            
  312.             @Override
  313.             public void update(int i1, int j1, int i2, int j2, long delta) {
  314.                 updatePath(vertices[i1][j1], vertices[i2][j2], delta);
  315.             }
  316.            
  317.             abstract void updatePath(int from, int to, long delta);
  318.            
  319.             @Override
  320.             public long get(int i, int j) {
  321.                 int v = vertices[i][j];
  322.                 return vertexValues[v] + getVertexValue(v);
  323.             }
  324.            
  325.             abstract long getVertexValue(int v);
  326.         }
  327.        
  328.        
  329.         static int[][] generateIndexes(int m, int n) {
  330.             int[][] indexes = new int[m][n];
  331.             for (int i = 0, index = 0; i < m; ++i) {
  332.                 for (int j = 0; j < n; ++j, ++index) {
  333.                     indexes[i][j] = index;
  334.                 }
  335.             }
  336.            
  337.             return indexes;
  338.         }
  339.        
  340.        
  341.         static Edge[][] generateMatrixGraph(int m, int n, int size, int[][] vertices, long[][] down, long[][] right) {
  342.             List<Edge>[] edgeLists = new List[size];
  343.             for (int v = 0; v < size; ++v) {
  344.                 edgeLists[v] = new ArrayList<Edge>();
  345.             }
  346.            
  347.             for (int i = 0; i < m - 1; ++i) {
  348.                 for (int j = 0; j < n; ++j) {
  349.                     int from = vertices[i][j];
  350.                     int to = vertices[i + 1][j];
  351.                    
  352.                     long weight = down[i][j];
  353.                    
  354.                     edgeLists[from].add(new Edge(to, weight));
  355.                     edgeLists[to].add(new Edge(from, weight));
  356.                 }
  357.             }
  358.            
  359.             for (int i = 0; i < m; ++i) {
  360.                 for (int j = 0; j < n - 1; ++j) {
  361.                     int from = vertices[i][j];
  362.                     int to = vertices[i][j + 1];
  363.                    
  364.                     long weight = right[i][j];
  365.                    
  366.                     edgeLists[from].add(new Edge(to, weight));
  367.                     edgeLists[to].add(new Edge(from, weight));
  368.                 }
  369.             }
  370.            
  371.             Edge[][] graph = new Edge[size][];
  372.             for (int v = 0; v < size; ++v) {
  373.                 graph[v] = edgeLists[v].toArray(new Edge[0]);
  374.             }
  375.            
  376.             return graph;
  377.         }
RAW Paste Data