Guest User

Untitled

a guest
Oct 20th, 2017
116
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package xenia.and.bit.operations;
  2.  
  3. import java.util.ArrayDeque;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  6.  
  7. public class Main {
  8.  
  9.     private static Segment[] LEAF;
  10.  
  11.     private static int n, q;
  12.  
  13.     private static Segment TREE_ROOT;
  14.  
  15.     public static void main(String[] args) {
  16.  
  17.         // Taking Input
  18.         Scanner scanner = new Scanner(System.in);
  19.         n = scanner.nextInt();
  20.         q = scanner.nextInt();
  21.  
  22.         LEAF = new Segment[n + 1];
  23.  
  24.         for (int i = 1; i <= n; i++) {
  25.             int ai = scanner.nextInt();
  26.             LEAF[i] = new Segment(i, i, getDigits(ai), null, null);
  27.         }
  28.         // Build the Segment tree and Store the root
  29.         TREE_ROOT = buildSegmentTree(1, n);
  30.  
  31.         // Serve the query of type 1 and type 2
  32.         for (int i = 0; i < q; i++) {
  33.             int queryType = scanner.nextInt();
  34.             if (queryType == 2) {
  35.                 // SUM query
  36.                 int left = scanner.nextInt();
  37.                 int right = scanner.nextInt();
  38.                 long sum = segmentQuery(TREE_ROOT, left, right);
  39.                 System.out.println(sum);
  40.             } else if (queryType == 1) {
  41.                 // Update Query
  42.                 int l = scanner.nextInt();
  43.                 int r = scanner.nextInt();
  44.                 int x = scanner.nextInt();
  45.                 int y = scanner.nextInt();
  46.                 SegmentAlter alter = new SegmentAlter(l, r, x, y);
  47.                 TREE_ROOT.addAlter(alter);
  48.                 segmentUpdtae(TREE_ROOT);
  49.             }
  50.         }
  51.         scanner.close();
  52.     }
  53.  
  54.     private static Segment buildSegmentTree(int left, int right) {
  55.         if (left == right) {
  56.             return LEAF[left];
  57.         }
  58.         // Build left segment
  59.         Segment leftSegment = buildSegmentTree(left, (left + right) / 2);
  60.         // Build right segment
  61.         Segment rightSegment = buildSegmentTree((left + right) / 2 + 1, right);
  62.         int digits[][] = new int[10][10];
  63.         for (int i = 0; i < 10; i++) {
  64.             for (int j = 0; j < 10; j++) {
  65.                 digits[i][j] = leftSegment.digits[i][j] + rightSegment.digits[i][j];
  66.             }
  67.         }
  68.         Segment segment = new Segment(left, right, digits, leftSegment, rightSegment);
  69.         return segment;
  70.     }
  71.  
  72.     private static long segmentQuery(Segment segment, int left, int right) {
  73.         if (left > right || segment == null) {
  74.             return 0;
  75.         }
  76.         if ((right < segment.left || left > segment.right)) {
  77.             return 0;
  78.         }
  79.         if (left <= segment.left && right >= segment.right) {
  80.             segment.settleDownAlters();
  81.             return segment.getSum();
  82.         }
  83.         if (segment.hasAlters()) {
  84.             segment.settleDownAlters();
  85.         }
  86.         // Calculate the left child
  87.         long leftSum = segmentQuery(segment.leftChild, left, right);
  88.         // Calculate the right child
  89.         long rightSum = segmentQuery(segment.rightChild, left, right);
  90.         return leftSum + rightSum;
  91.     }
  92.  
  93.     private static int[][] segmentUpdtae(Segment segment) {
  94.         if (!segment.hasAlters()) {
  95.             return segment.digits;
  96.         }
  97.         SegmentAlter recentAlter = segment.lazyAlters.getLast();
  98.         if (segment.left >= recentAlter.left && segment.right <= recentAlter.right) {
  99.             segment.settleDownAlters();
  100.             return segment.digits;
  101.         }
  102.         // Push the alters to both the children
  103.         segment.pushDownAlters();
  104.         // Update left segment
  105.         int[][] leftDigitis = segmentUpdtae(segment.leftChild);
  106.         // Update right segment
  107.         int[][] rightDigitis = segmentUpdtae(segment.rightChild);
  108.         // Update digit of current segment
  109.         int[][] newDigits = new int[10][10];
  110.         for (int i = 0; i < 10; i++) {
  111.             for (int j = 0; j < 10; j++)
  112.                 newDigits[i][j] = leftDigitis[i][j] + rightDigitis[i][j];
  113.         }
  114.         segment.digits = newDigits;
  115.         return newDigits;
  116.     }
  117.  
  118.     private static int[][] getDigits(int number) {
  119.         int[][] digits = new int[10][10];
  120.         for (int i = 0; i < 10 && number != 0; i++) {
  121.             int digit = number % 10;
  122.             digits[i][digit]++;
  123.             number /= 10;
  124.         }
  125.         return digits;
  126.     }
  127.  
  128.     static class Segment {
  129.  
  130.         private static final long MULTIPLIER[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,
  131.                 1000000000 };
  132.  
  133.         // Defines the bound of this segment
  134.         public int left, right;
  135.         // Stores the digit counts of 0~9, for different places
  136.         public int[][] digits = new int[10][10];
  137.         // Stores the alter query affecting this node.
  138.         ArrayDeque<SegmentAlter> lazyAlters = new ArrayDeque<>();
  139.  
  140.         public Segment leftChild, rightChild;
  141.  
  142.         public Segment(int left, int right, int[][] digits, Segment leftChild, Segment rightChild) {
  143.             this.left = left;
  144.             this.right = right;
  145.             this.digits = digits;
  146.             this.leftChild = leftChild;
  147.             this.rightChild = rightChild;
  148.         }
  149.  
  150.         public boolean isLeaf() {
  151.             return left == right;
  152.         }
  153.  
  154.         public void addAlter(SegmentAlter alter) {
  155.             if (this.left > alter.right || this.right < alter.left) {
  156.                 return;
  157.             }
  158.             this.lazyAlters.add(alter);
  159.         }
  160.  
  161.         public void addAlters(Queue<SegmentAlter> alters) {
  162.             alters.forEach(alter -> addAlter(alter));
  163.         }
  164.  
  165.         public void clearAlters() {
  166.             this.lazyAlters.clear();
  167.         }
  168.  
  169.         public boolean hasAlters() {
  170.             return !this.lazyAlters.isEmpty();
  171.         }
  172.  
  173.         public void settleDownAlters() {
  174.             // Apply the alters on the current Node
  175.             this.lazyAlters.forEach(alter -> {
  176.                 for (int i = 0; i < 10; i++) {
  177.                     digits[i][alter.alterTo] += digits[i][alter.alterfrom];
  178.                     digits[i][alter.alterfrom] = 0;
  179.                 }
  180.             });
  181.             if (!isLeaf()) {
  182.                 this.leftChild.addAlters(this.lazyAlters);
  183.                 this.rightChild.addAlters(this.lazyAlters);
  184.             }
  185.             this.clearAlters();
  186.         }
  187.  
  188.         public void pushDownAlters() {
  189.             if (!isLeaf()) {
  190.                 this.leftChild.addAlters(this.lazyAlters);
  191.                 this.rightChild.addAlters(this.lazyAlters);
  192.             }
  193.             this.clearAlters();
  194.         }
  195.  
  196.         public long getSum() {
  197.             long sum = 0;
  198.             for (int i = 0; i < 10; i++) {
  199.                 for (int j = 0; j < 10; j++) {
  200.                     sum += j * MULTIPLIER[i] * digits[i][j];
  201.                 }
  202.             }
  203.             return sum;
  204.         }
  205.     }
  206.  
  207.     static class SegmentAlter {
  208.         // Defines the left and right of digit alter
  209.         public int left, right;
  210.         public int alterfrom, alterTo;
  211.  
  212.         public SegmentAlter(int left, int right, int alterfrom, int alterTo) {
  213.             this.left = left;
  214.             this.right = right;
  215.             this.alterfrom = alterfrom;
  216.             this.alterTo = alterTo;
  217.         }
  218.     }
  219.  
  220. }
RAW Paste Data