Advertisement
999ms

codeforces.com/contest/848/problem/C

Apr 20th, 2019
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 9.31 KB | None | 0 0
  1. import javax.swing.text.Segment;
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class Main {
  6.  
  7.     String fileName = "";
  8.  
  9.     class Query {
  10.         int a, b, c;
  11.  
  12.         Query(int a, int b, int c) {
  13.             this.a = a;
  14.             this.b = b;
  15.             this.c = c;
  16.         }
  17.     }
  18.  
  19.     void solve() throws IOException {
  20.         int n = readInt(), m = readInt();
  21.         int[] arr = new int[n];
  22.  
  23.         for (int i = 0; i < n; i++) {
  24.             arr[i] = readInt() - 1;
  25.         }
  26.         Set<Integer> prexy[] = new TreeSet[n];  //
  27.         Arrays.fill(prexy, new TreeSet<Integer>());
  28.         int[] lastPosition = new int[n];
  29.         for (int i = n - 1; i >= 0; i--) {
  30.             prexy[i].add(Math.max(lastPosition[arr[i]], i));
  31.             lastPosition[arr[i]] = i;
  32.         }
  33.         Query[] queries = new Query[m];
  34.         TreeSet<Integer>[] sets = new TreeSet[n];
  35.         Arrays.fill(sets, new TreeSet<Integer>());
  36.         for (int i = 0; i < n; i++) {
  37.             sets[arr[i]].add(i);
  38.         }
  39.         for (int i = 0; i < m; i++) {
  40.             queries[i] = new Query(readInt() - 1, readInt() - 1, readInt() - 1);
  41.             if (queries[i].a == 0) {
  42.                 int now = queries[i].c;
  43.                 if (sets[now].lower(queries[i].b) != null) {
  44.                     int previous_index = sets[now].lower(queries[i].b);
  45.                     if (sets[now].higher(queries[i].b) != null) {
  46.                         sets[now].add(queries[i].c);
  47.                     }
  48.                     sets[previous_index].add(queries[i].c);
  49.                 }
  50.             }
  51.         }
  52.         int[][] xy = new int[n][];
  53.         for (int i = 0; i < n; i++) {
  54.             xy[i] = new int[sets[i].size()];
  55.             int currentIndex = 0;
  56.             for (int val : sets[i]) {
  57.                 xy[i][currentIndex++] = val;
  58.             }
  59.         }
  60.         for (int i = 0; i < n; i++) {
  61.             sets[i].clear();
  62.         }
  63.         SegmentTree tree = new SegmentTree(xy);
  64.         for (int i = n - 1; i >= 0; i--) {
  65.             sets[arr[i]].add(i);
  66.             tree.update(0, 0, n, i, arr[i], Math.max(i, lastPosition[arr[i]]) - i);
  67.             lastPosition[arr[i]] = i;
  68.         }
  69.  
  70.         for (int index = 0; index < m; index++) {
  71.             if (queries[index].a == 0) {
  72.                 int ind = queries[index].b;
  73.                 int newValue = queries[index].c;
  74.                 int currentValue = arr[ind];
  75.                 if (currentValue == newValue) continue;
  76.                 if (sets[currentValue].lower(ind) != null) {
  77.                     int previousIndex = sets[currentValue].lower(ind);
  78.                     tree.update(0, 0, n, previousIndex, ind, 0);
  79.                     if (sets[currentValue].higher(ind) != null) {
  80.                         int nextIndex = sets[currentValue].higher(ind);
  81.                         tree.update(0, 0, n, previousIndex, nextIndex, nextIndex - previousIndex);
  82.                     }
  83.                 }
  84.  
  85.                 if(sets[newValue].lower(ind) != null){
  86.                     int previousIndex = sets[newValue].lower(ind);
  87.                     if(sets[newValue].higher(ind) != null){
  88.                         int nextIndex = sets[newValue].higher(ind);
  89.                         tree.update(0, 0, n, previousIndex, nextIndex, 0);
  90.                         tree.update(0, 0, n, ind, nextIndex, nextIndex - ind);
  91.                     } else {
  92.                         tree.update(0 ,0, n, previousIndex, ind, ind - previousIndex);
  93.                     }
  94.                 }
  95.  
  96.                 sets[currentValue].remove(ind);
  97.                 sets[newValue].add(ind);
  98.                 arr[ind] = newValue;
  99.             } else {
  100.                 out.print(tree.get(0, 0, n, queries[index].b, queries[index].b, queries[index].c + 1, queries[index].c) + "\n");
  101.             }
  102.         }
  103.  
  104.     }
  105.  
  106.  
  107.     class FenwickTree {
  108.         long[] t;
  109.         int n;
  110.  
  111.         FenwickTree(int n) {
  112.             this.n = n;
  113.             t = new long[n];
  114.         }
  115.  
  116.         void add(int i, int val) {
  117.             while (i < n) {
  118.                 t[i] += val;
  119.                 i = (i + 1) | i;
  120.             }
  121.         }
  122.  
  123.         long get(int i) {
  124.             long ans = 0;
  125.             while (i >= 0) {
  126.                 ans += t[i];
  127.                 i = ((i + 1) & i) - 1;
  128.             }
  129.             return ans;
  130.         }
  131.  
  132.         long get(int l, int r) {
  133.             return get(r) - (l > 0 ? get(l - 1) : 0);
  134.         }
  135.     }
  136.  
  137.     class Node {
  138.         int[] y;
  139.         FenwickTree tree;
  140.  
  141.         Node(int[] y) {
  142.             this.y = y;
  143.             tree = new FenwickTree(this.y.length);
  144.         }
  145.  
  146.         Node(Node l, Node r) {
  147.             TreeSet<Integer> set = new TreeSet<>();
  148.             for (int i : l.y) set.add(i);
  149.             for (int i : r.y) set.add(i);
  150.             this.y = new int[set.size()];
  151.             int currentIndex = 0;
  152.             for (int i : set) {
  153.                 this.y[currentIndex++] = i;
  154.             }
  155.             tree = new FenwickTree(this.y.length);
  156.         }
  157.  
  158.         int getIndex(int value) {
  159.             int left = 0;
  160.             int right = this.y.length - 1;
  161.             int mid;
  162.             int ans = -1;
  163.             while (left <= right) {
  164.                 mid = (left + right) / 2;
  165.                 if (this.y[mid] <= value) {
  166.                     ans = mid;
  167.                     left = mid + 1;
  168.                 } else {
  169.                     right = mid - 1;
  170.                 }
  171.             }
  172.             return ans;
  173.         }
  174.  
  175.         void addValue(int index, int value) {
  176.             tree.add(index, value);
  177.         }
  178.  
  179.         long get(int l, int r) {
  180.             return tree.get(l, r);
  181.         }
  182.     }
  183.  
  184.     class SegmentTree {
  185.         Node[] tree;
  186.         int n;
  187.  
  188.         SegmentTree(int[][] xy) {
  189.             this.n = xy.length;
  190.             tree = new Node[n * 4];
  191.             build(0, 0, n, xy);
  192.         }
  193.  
  194.         void build(int v, int tl, int tr, int[][] xy) {
  195.             if (tl + 1 == tr) {
  196.                 tree[v] = new Node(xy[tl]);
  197.             } else {
  198.                 int tm = (tl + tr) / 2;
  199.                 build(v * 2 + 1, tl, tm, xy);
  200.                 build(v * 2 + 2, tm, tr, xy);
  201.                 tree[v] = new Node(tree[v * 2 + 1], tree[v * 2 + 2]);
  202.             }
  203.         }
  204.  
  205.         void update(int v, int tl, int tr, int x, int y, int val) {
  206.             if (tl + 1 == tr) {
  207.                 tree[v].addValue(y, val);
  208.             } else {
  209.                 int tm = (tl + tr) / 2;
  210.                 if (x < tm) {
  211.                     update(v * 2 + 1, tl, tm, x, y, val);
  212.                 } else {
  213.                     update(v * 2 + 2, tm, tr, x, y, val);
  214.                 }
  215.                 tree[v].addValue(y, val);
  216.             }
  217.         }
  218.  
  219.         long get(int v, int tl, int tr, int x1, int y1, int x2, int y2) {
  220.             if (tl >= x2 || tr <= x1) return 0;
  221.             if (tl >= x1 && tr <= x2) {
  222.                 return tree[v].get(y1, y2);
  223.             } else {
  224.                 int tm = (tl + tr) / 2;
  225.                 return get(v * 2 + 1, tl, tm, x1, y1, x2, y2) +
  226.                         get(v * 2 + 2, tm, tr, x1, y1, x2, y2);
  227.             }
  228.         }
  229.  
  230.     }
  231.  
  232.     public static void main(String[] args) throws NumberFormatException, IOException {
  233.         new Main().run();
  234.     }
  235.  
  236.     void run() throws NumberFormatException, IOException {
  237.         solve();
  238.         out.close();
  239.     }
  240.  
  241.     BufferedReader in;
  242.     PrintWriter out;
  243.  
  244.     StringTokenizer tok;
  245.     String delim = " ";
  246.  
  247.     Main() throws FileNotFoundException {
  248.         try {
  249.             in = new BufferedReader(new FileReader("input.txt"));
  250.             out = new PrintWriter("output.txt");
  251.         } catch (Exception e) {
  252.             if (fileName.isEmpty()) {
  253.                 in = new BufferedReader(new InputStreamReader(System.in));
  254.                 out = new PrintWriter(System.out);
  255.             } else {
  256.                 in = new BufferedReader(new FileReader(fileName + ".in"));
  257.                 out = new PrintWriter(fileName + ".out");
  258.             }
  259.  
  260.         }
  261.         tok = new StringTokenizer("");
  262.     }
  263.  
  264.     String readLine() throws IOException {
  265.         return in.readLine();
  266.     }
  267.  
  268.     String readString() throws IOException {
  269.         while (!tok.hasMoreTokens()) {
  270.             String nextLine = readLine();
  271.             if (null == nextLine) {
  272.                 return null;
  273.             }
  274.  
  275.             tok = new StringTokenizer(nextLine);
  276.         }
  277.         return tok.nextToken(delim);
  278.     }
  279.  
  280.     int readInt() throws NumberFormatException, IOException {
  281.         return Integer.parseInt(readString());
  282.     }
  283.  
  284.     long readLong() throws NumberFormatException, IOException {
  285.         return Long.parseLong(readString());
  286.     }
  287.  
  288.     int[] readIntArray(int n) throws NumberFormatException, IOException {
  289.         int[] a = new int[n];
  290.         for (int i = 0; i < n; ++i) {
  291.             a[i] = readInt();
  292.         }
  293.         return a;
  294.     }
  295.  
  296.     double readDouble() throws NumberFormatException, IOException {
  297.         return Double.parseDouble(readString());
  298.     }
  299.  
  300.     void sortIntArray(int[] a) {
  301.         Integer[] arr = new Integer[a.length];
  302.         for (int i = 0; i < a.length; i++) {
  303.             arr[i] = a[i];
  304.         }
  305.         Arrays.sort(arr);
  306.         for (int i = 0; i < a.length; i++) {
  307.             a[i] = arr[i];
  308.         }
  309.     }
  310.  
  311.  
  312. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement