Advertisement
Guest User

Untitled

a guest
Mar 26th, 2019
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.01 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.StringTokenizer;
  3.  
  4. public class FibonacciMachine {
  5.   static class Solver {
  6.     final int[][] A = new int[][]{{1, 1}, {1, 0}};
  7.     final int[][] I = new int[][]{{1, 0}, {0, 1}};
  8.     final int[][] F1_F0 = new int[][]{{1}, {0}};
  9.     final int[][] ZERO = new int[][]{{0}, {0}};
  10.     final int MOD = (int) 1e9 + 7;
  11.     int n, q;
  12.     int[][][] tree;
  13.     int[] lazy;
  14.  
  15.     // -----------------------------------
  16.  
  17.     int add(int a, int b) {
  18.       return ((a % MOD) + (b % MOD)) % MOD;
  19.     }
  20.  
  21.     int mul(int a, int b) {
  22.       return (int) (((long) (a % MOD) * (b % MOD)) % MOD);
  23.     }
  24.  
  25.     int[][] mul(int[][] a, int[][] b) {
  26.       int[][] result = new int[a.length][b[0].length];
  27.       for (int i = 0; i < a.length; i++) {
  28.         for (int j = 0; j < b[0].length; j++) {
  29.           for (int k = 0; k < b.length; k++) {
  30.             result[i][j] = add(result[i][j], mul(a[i][k], b[k][j]));
  31.           }
  32.         }
  33.       }
  34.       return result;
  35.     }
  36.  
  37.     int[][] pow(int[][] a, int n) {
  38.       if (n == 0) {
  39.         return I;
  40.       } else if (n % 2 == 0) {
  41.         return pow(mul(a, a), n >> 1);
  42.       } else {
  43.         return mul(a, pow(mul(a, a), n >> 1));
  44.       }
  45.     }
  46.  
  47.     // -----------------------------------
  48.  
  49.     void push(int n, int l, int r) {
  50.       if (lazy[n] != 0) {
  51.         tree[n] = mul(pow(A, lazy[n]), tree[n]);
  52.         if (l != r) {
  53.           lazy[n + n] += lazy[n];
  54.           lazy[n + n + 1] += lazy[n];
  55.         }
  56.         lazy[n] = 0;
  57.       }
  58.     }
  59.  
  60.     int[][] combine(int[][] a, int[][] b) {
  61.       return new int[][]{{a[0][0] + b[0][0]}, {a[1][0] + b[1][0]}};
  62.     }
  63.  
  64.     void build(int n, int l, int r) {
  65.       if (l == r) {
  66.         tree[n] = F1_F0;
  67.       } else {
  68.         int m = (l + r) >> 1;
  69.         build(n + n, l, m);
  70.         build(n + n + 1, m + 1, r);
  71.         tree[n] = combine(tree[n + n], tree[n + n + 1]);
  72.       }
  73.     }
  74.  
  75.     int[][] query(int n, int l, int r, int s, int e) {
  76.       push(n, l, r);
  77.       if (l > e || r < s) {
  78.         return ZERO;
  79.       } else if (s <= l && r <= e) {
  80.         return tree[n];
  81.       } else {
  82.         int m = (l + r) >> 1;
  83.         return combine(
  84.           query(n + n, l, m, s, e),
  85.           query(n + n + 1, m + 1, r, s, e)
  86.         );
  87.       }
  88.     }
  89.  
  90.     void update(int n, int l, int r, int s, int e) {
  91.       push(n, l, r);
  92.       if (l > e || r < s) {
  93.       } else if (s <= l && r <= e) {
  94.         tree[n] = mul(A, tree[n]);
  95.         if (l != r) {
  96.           lazy[n + n]++;
  97.           lazy[n + n + 1]++;
  98.         }
  99.       } else {
  100.         int m = (l + r) >> 1;
  101.         update(n + n, l, m, s, e);
  102.         update(n + n + 1, m + 1, r, s, e);
  103.         tree[n] = combine(tree[n + n], tree[n + n + 1]);
  104.       }
  105.     }
  106.  
  107.     // -----------------------------------
  108.  
  109.     void solve() throws Exception {
  110.       n = nextInt();
  111.       q = nextInt();
  112.       tree = new int[4 * n + 5][2][1];
  113.       lazy = new int[4 * n + 5];
  114.       build(1, 1, n);
  115.       while (q-- > 0) {
  116.         if (next().equals("D")) {
  117.           update(1, 1, n, nextInt(), nextInt());
  118.         } else {
  119.           writer.println(query(1, 1, n, nextInt(), nextInt())[1][0]);
  120.         }
  121.       }
  122.     }
  123.   }
  124.  
  125.   // -------------------------------------
  126.  
  127.   static BufferedReader reader;
  128.   static StringTokenizer tokenizer;
  129.   static PrintWriter writer;
  130.  
  131.   static String next() throws Exception {
  132.     while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  133.       tokenizer = new StringTokenizer(reader.readLine());
  134.     }
  135.     return tokenizer.nextToken();
  136.   }
  137.  
  138.   static int nextInt() throws Exception {
  139.     return Integer.parseInt(next());
  140.   }
  141.  
  142.   public static void main(String[] args) throws Exception {
  143.     reader = new BufferedReader(new InputStreamReader(System.in));
  144.     reader = new BufferedReader(new InputStreamReader(new FileInputStream("_in")));
  145.     writer = new PrintWriter(System.out);
  146.     writer = new PrintWriter(new File("_out"));
  147.     Solver solver = new Solver();
  148.     solver.solve();
  149.     reader.close();
  150.     writer.close();
  151.   }
  152. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement