Advertisement
Guest User

Untitled

a guest
Oct 28th, 2016
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.99 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <string>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <set>
  10. #include <map>
  11. #include <cmath>
  12. #include <ctime>
  13. #include <functional>
  14. #include <sstream>
  15. #include <fstream>
  16. #include <valarray>
  17. #include <complex>
  18. #include <queue>
  19. #include <cassert>
  20. #include <bitset>
  21.  
  22. #include <unordered_map>
  23.  
  24. using namespace std;
  25.  
  26. #ifdef LOCAL
  27. #define debug_flag 1
  28. #else
  29. #define debug_flag 0
  30. #endif
  31.  
  32. template <class T1, class T2 >
  33. std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p)
  34. {
  35.     os << "[" << p.first << ", " << p.second << "]";
  36.     return os;
  37. }
  38.  
  39. template <class T >
  40. std::ostream& operator << (std::ostream& os, const std::vector<T>& v)
  41. {
  42.     os << "[";
  43.     bool first = true;
  44.     for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
  45.     {
  46.         if (!first)
  47.             os << ", ";
  48.         first = false;
  49.         os << *it;
  50.     }
  51.     os << "]";
  52.     return os;
  53. }
  54.  
  55. template <class T >
  56. std::ostream& operator << (std::ostream& os, const std::vector<vector<T>>& v)
  57. {
  58.  
  59.     os << "[" << endl;
  60.     bool first = true;
  61.     for (typename std::vector<vector<T>>::const_iterator it = v.begin(); it != v.end(); ++it)
  62.     {
  63.         os << *it << endl;
  64.     }
  65.     os << "]" << endl;
  66.     return os;
  67. }
  68.  
  69. typedef long long int int64;
  70.  
  71. const int N = (int)4e5 + 100;
  72. const int LOGN = 20;
  73. const int INF = (int)1e9;
  74. const int mod = (int)1e9 + 7;
  75.  
  76. const int PLUS = 0;
  77. const int MUL = 1;
  78. const int NUMBER = 2;
  79.  
  80. int mod_add(int a, int b)
  81. {
  82.     a += b;
  83.     if (a >= mod)
  84.         a -= mod;
  85.     return a;
  86. }
  87.  
  88. int mod_sub(int a, int b)
  89. {
  90.     a -= b;
  91.     if (a < 0)
  92.         a += mod;
  93.     return a;
  94. }
  95.  
  96. int mod_mul(int a, int b)
  97. {
  98.     return (int64)a * b % mod;
  99. }
  100.  
  101. struct SparseTable
  102. {
  103.     int min_val[N][LOGN];
  104.     int max_pow2[N];
  105.  
  106.     SparseTable()
  107.     {
  108.  
  109.     }
  110.  
  111.     void init(int n, int arr[])
  112.     {
  113.         fill(max_pow2, max_pow2 + N, 0);
  114.  
  115.         for (int i = 2; i < N; i *= 2)
  116.             max_pow2[i] = 1;
  117.  
  118.         for (int i = 1; i < N; i++)
  119.             max_pow2[i] += max_pow2[i - 1];
  120.  
  121.         for (int i = 0; i < N; i++)
  122.         {
  123.             if (i < n)
  124.                 min_val[i][0] = arr[i];
  125.             else
  126.                 min_val[i][0] = INF;
  127.         }
  128.  
  129.         for (int st = 1; st < LOGN; st++)
  130.         {
  131.             for (int i = 0; i + (1 << (st - 1)) < N; i++)
  132.             {
  133.                 min_val[i][st] = min(min_val[i][st - 1], min_val[i + (1 << (st - 1))][st - 1]);
  134.             }
  135.         }
  136.     }
  137.  
  138.     int get_min(int a, int b)
  139.     {
  140.         assert(0 <= a);
  141.         assert(a <= b);
  142.         assert(b < N);
  143.  
  144.         int len = b - a + 1;
  145.         int p = max_pow2[len];
  146.         return min(min_val[a][p], min_val[b - (1 << p) + 1][p]);
  147.     }
  148. };
  149.  
  150. bool not_inter(int l, int r, int a, int b)
  151. {
  152.     return l > b || r < a;
  153. }
  154.  
  155. bool is_in(int l, int r, int a, int b)
  156. {
  157.     return a <= l && r <= b;
  158. }
  159.  
  160. struct SumTree
  161. {
  162.     int pow2;
  163.     vector<int> sum;
  164.  
  165.     SumTree()
  166.     {
  167.  
  168.     }
  169.  
  170.     void init(int n)
  171.     {
  172.         pow2 = 1;
  173.         while (pow2 < n)
  174.             pow2 *= 2;
  175.  
  176.         sum.resize(pow2 * 2);
  177.     }
  178.  
  179.     void set(int pos, int val)
  180.     {
  181.         pos += pow2;
  182.         sum[pos] = val;
  183.         pos /= 2;
  184.  
  185.         while (pos >= 1)
  186.         {
  187.             sum[pos] = mod_add(sum[pos * 2], sum[pos * 2 + 1]);
  188.             pos /= 2;
  189.         }
  190.     }
  191.  
  192.     int get_sum(int a, int b)
  193.     {
  194.         assert(0 <= a);
  195.         assert(a <= b);
  196.         assert(b < N);
  197.  
  198.         return get_sum(1, 0, pow2 - 1, a, b);
  199.     }
  200.  
  201.     int get_sum(int v, int l, int r, int a, int b)
  202.     {
  203.         if (not_inter(l, r, a, b))
  204.             return 0;
  205.         if (is_in(l, r, a, b))
  206.             return sum[v];
  207.         int m = (l + r) / 2;
  208.         return mod_add(get_sum(v * 2, l, m, a, b),
  209.             get_sum(v * 2 + 1, m + 1, r, a, b));
  210.     }
  211. };
  212.  
  213. struct MulTree
  214. {
  215.     int pow2;
  216.     vector<int> mul;
  217.  
  218.     MulTree()
  219.     {
  220.  
  221.     }
  222.  
  223.     void init(int n)
  224.     {
  225.         pow2 = 1;
  226.         while (pow2 < n)
  227.             pow2 *= 2;
  228.  
  229.         mul.resize(pow2 * 2, 1);
  230.     }
  231.  
  232.     void set(int pos, int val)
  233.     {
  234.         pos += pow2;
  235.         mul[pos] = val;
  236.         pos /= 2;
  237.  
  238.         while (pos >= 1)
  239.         {
  240.             mul[pos] = mod_mul(mul[pos * 2], mul[pos * 2 + 1]);
  241.             pos /= 2;
  242.         }
  243.     }
  244.  
  245.     int get_mul(int a, int b)
  246.     {
  247.         assert(0 <= a);
  248.         assert(a <= b);
  249.         assert(b < N);
  250.  
  251.         return get_mul(1, 0, pow2 - 1, a, b);
  252.     }
  253.  
  254.     int get_mul(int v, int l, int r, int a, int b)
  255.     {
  256.         if (not_inter(l, r, a, b))
  257.             return 1;
  258.         if (is_in(l, r, a, b))
  259.             return mul[v];
  260.         int m = (l + r) / 2;
  261.         return mod_mul(get_mul(v * 2, l, m, a, b),
  262.             get_mul(v * 2 + 1, m + 1, r, a, b));
  263.     }
  264. };
  265.  
  266. struct BracketsChecker
  267. {
  268.     int n;
  269.     int bal[N];
  270.     SparseTable sparse_table;
  271.  
  272.     BracketsChecker()
  273.     {
  274.  
  275.     }
  276.  
  277.     void init(string exp)
  278.     {
  279.         n = (int)exp.length();
  280.         int cur_bal = 0;
  281.  
  282.         for (int i = 0; i < n; i++)
  283.         {
  284.             if (exp[i] == '(')
  285.                 cur_bal++;
  286.             if (exp[i] == ')')
  287.                 cur_bal--;
  288.             bal[i] = cur_bal;
  289.         }
  290.  
  291.         sparse_table.init(n, bal);
  292.     }
  293.  
  294.     bool is_correct(int a, int b)
  295.     {
  296.         assert(0 <= a);
  297.         assert(a <= b);
  298.         assert(b < N);
  299.  
  300.         int a_bal = 0;
  301.         if (a != 0)
  302.             a_bal = bal[a - 1];
  303.  
  304.         int min_bal = sparse_table.get_min(a, b);
  305.  
  306.         int b_bal = bal[b];
  307.  
  308.         return a_bal == min_bal && min_bal == b_bal;
  309.     }
  310. };
  311.  
  312. struct DigitItem
  313. {
  314.     int value;
  315.     int pow10;
  316.  
  317.     DigitItem() : value(), pow10() {}
  318.     DigitItem(int _value, int _pow10) : value(_value), pow10(_pow10) {}
  319.  
  320.     DigitItem merge(const DigitItem &other) const
  321.     {
  322.         int new_value = mod_add(other.value, mod_mul(value, other.pow10));
  323.         int new_pow10 = mod_mul(pow10, other.pow10);
  324.         return DigitItem(new_value, new_pow10);
  325.     }
  326. };
  327.  
  328. struct DigitTree
  329. {
  330.     int pow2;
  331.     vector<DigitItem> tree;
  332.  
  333.     DigitTree()
  334.     {
  335.  
  336.     }
  337.  
  338.     void init(string expr)
  339.     {
  340.         int n = (int)expr.size();
  341.  
  342.         pow2 = 1;
  343.         while (pow2 < n)
  344.             pow2 *= 2;
  345.  
  346.         tree.resize(pow2 * 2);
  347.         for (int i = 0; i < pow2; i++)
  348.         {
  349.             if (i < n && isdigit(expr[i]))
  350.                 tree[pow2 + i] = DigitItem(expr[i] - '0', 10);
  351.             else
  352.                 tree[pow2 + i] = DigitItem(0, 1);
  353.         }
  354.  
  355.         for (int i = pow2 - 1; i >= 1; i--)
  356.             tree[i] = tree[i * 2].merge(tree[i * 2 + 1]);
  357.     }
  358.  
  359.     DigitItem get(int a, int b)
  360.     {
  361.         return get(1, 0, pow2 - 1, a, b);
  362.     }
  363.  
  364.     DigitItem get(int v, int l, int r, int a, int b)
  365.     {
  366.         if (not_inter(l, r, a, b))
  367.             return DigitItem(0, 1);
  368.  
  369.         if (is_in(l, r, a, b))
  370.             return tree[v];
  371.  
  372.         int m = (l + r) / 2;
  373.         return get(v * 2, l, m, a, b).merge(get(v * 2 + 1, m + 1, r, a, b));
  374.     }
  375. };
  376.  
  377. DigitTree digit_tree;
  378.  
  379. struct Token
  380. {
  381.     int type;
  382.     int value;
  383.     int real_a, real_b;
  384.  
  385.     Token() : type(), value(), real_a(), real_b() {}
  386.  
  387.     Token(int _type, int _value, int _real_a, int _real_b) :
  388.         type(_type), value(_value), real_a(_real_a), real_b(_real_b) {}
  389.  
  390.     int solve(int a, int b)
  391.     {
  392.         if (a == real_a && b == real_b)
  393.             return value;
  394.         DigitItem digit_item = digit_tree.get(a, b);
  395.         return digit_item.value;
  396.     }
  397. };
  398.  
  399. int get_pos(const vector<int> &real_a_list, int a)
  400. {
  401.     return upper_bound(real_a_list.begin(), real_a_list.end(), a) - real_a_list.begin() - 1;
  402. }
  403.  
  404.  
  405. struct PlusItem
  406. {
  407.     int value;
  408.     int real_a, real_b;
  409.     MulTree mul_tree;
  410.     vector<Token> tokens;
  411.     vector<int> real_a_list;
  412.  
  413.     PlusItem()
  414.     {
  415.  
  416.     }
  417.  
  418.     PlusItem(vector<Token> _tokens)
  419.     {
  420.         assert(!_tokens.empty());
  421.         assert(_tokens[0].type == NUMBER);
  422.         assert(_tokens.back().type == NUMBER);
  423.  
  424.         real_a = _tokens[0].real_a;
  425.         real_b = _tokens.back().real_b;
  426.  
  427.         tokens = vector<Token>();
  428.         real_a_list = vector<int>();
  429.         value = 1;
  430.         for (Token token : _tokens)
  431.         {
  432.             if (token.type == NUMBER)
  433.             {
  434.                 real_a_list.push_back(token.real_a);
  435.                 tokens.push_back(token);
  436.                 value = mod_mul(value, token.value);
  437.             }
  438.             else
  439.                 assert(token.type == MUL);
  440.         }
  441.  
  442.         mul_tree.init((int)tokens.size());
  443.         for (int i = 0; i < (int)tokens.size(); i++)
  444.             mul_tree.set(i, tokens[i].value);
  445.     }
  446.  
  447.     int solve(int a, int b)
  448.     {
  449.         int block_a = get_pos(real_a_list, a);
  450.         int block_b = get_pos(real_a_list, b);
  451.  
  452.         if (block_a == block_b)
  453.             return tokens[block_a].solve(a, b);
  454.  
  455.         int mid = 1;
  456.         if (block_a + 1 <= block_b - 1)
  457.             mid = mul_tree.get_mul(block_a + 1, block_b - 1);
  458.  
  459.         int val_a = tokens[block_a].solve(a, tokens[block_a].real_b);
  460.         int val_b = tokens[block_b].solve(tokens[block_b].real_a, b);
  461.  
  462.         int ans = mod_mul(mid, mod_mul(val_a, val_b));
  463.  
  464.         return ans;
  465.     }
  466. };
  467.  
  468. struct BracketItem
  469. {
  470.     int value;
  471.     int real_a, real_b;
  472.     SumTree sum_tree;
  473.     vector<PlusItem> plus_items;
  474.     vector<int> real_a_list;
  475.  
  476.     BracketItem()
  477.     {
  478.  
  479.     }
  480.  
  481.     BracketItem(vector<Token> _tokens)
  482.     {
  483.         assert(!_tokens.empty());
  484.         assert(_tokens[0].type == NUMBER);
  485.         assert(_tokens.back().type == NUMBER);
  486.  
  487.         real_a = _tokens[0].real_a;
  488.         real_b = _tokens.back().real_b;
  489.  
  490.         value = 0;
  491.         plus_items = vector<PlusItem>();
  492.         real_a_list = vector<int>();
  493.  
  494.         _tokens.push_back(Token(PLUS, 0, 0, 0));
  495.         vector<Token> cur_tokens;
  496.  
  497.         for (Token token : _tokens)
  498.         {
  499.             if (token.type == PLUS)
  500.             {
  501.                 PlusItem plus_item = PlusItem(cur_tokens);
  502.                 cur_tokens.clear();
  503.                 plus_items.push_back(plus_item);
  504.                 value = mod_add(value, plus_item.value);
  505.                 real_a_list.push_back(plus_item.real_a);
  506.             }
  507.             else
  508.             {
  509.                 cur_tokens.push_back(token);
  510.             }
  511.         }
  512.  
  513.         sum_tree.init(plus_items.size());
  514.         for (int i = 0; i < (int)plus_items.size(); i++)
  515.             sum_tree.set(i, plus_items[i].value);
  516.     }
  517.  
  518.     int solve(int a, int b)
  519.     {
  520.         int block_a = get_pos(real_a_list, a);
  521.         int block_b = get_pos(real_a_list, b);
  522.  
  523.         if (block_a == block_b)
  524.             return plus_items[block_a].solve(a, b);
  525.  
  526.         int mid = 0;
  527.         if (block_a + 1 <= block_b - 1)
  528.             mid = sum_tree.get_sum(block_a + 1, block_b - 1);
  529.  
  530.         int val_a = plus_items[block_a].solve(a, plus_items[block_a].real_b);
  531.         int val_b = plus_items[block_b].solve(plus_items[block_b].real_a, b);
  532.  
  533.         int ans = mod_add(mid, mod_add(val_a, val_b));
  534.        
  535.         return ans;
  536.     }
  537. };
  538.  
  539. string read_string()
  540. {
  541.     char buf[N];
  542.     scanf("%s", buf);
  543.     return string(buf);
  544. }
  545.  
  546. string expr;
  547. BracketsChecker brackets_checker;
  548. int r_bracket[N];
  549. int cover_bracket[N];
  550. BracketItem bracket_items[N];
  551.  
  552. void match_brackets()
  553. {
  554.     vector<int> open_brackets;
  555.     for (int i = 0; i < (int)expr.length(); i++)
  556.     {
  557.         char c = expr[i];
  558.        
  559.         if (c == '(')
  560.             open_brackets.push_back(i);
  561.  
  562.         if (c == ')')
  563.         {
  564.             assert(!open_brackets.empty());
  565.             r_bracket[open_brackets.back()] = i;
  566.             open_brackets.pop_back();
  567.         }
  568.     }
  569.  
  570.     assert(open_brackets.empty());
  571. }
  572.  
  573. Token parse(int l, int r)
  574. {
  575.     assert(expr[l] == '(');
  576.     assert(expr[r] == ')');
  577.  
  578.     vector<Token> token_list;
  579.  
  580.     int ptr = l + 1;
  581.     while (ptr < r)
  582.     {
  583.         if (expr[ptr] == '+')
  584.         {
  585.             cover_bracket[ptr] = l;
  586.             token_list.push_back(Token(PLUS, 0, ptr, ptr));
  587.             ptr++;
  588.         }
  589.         else if (expr[ptr] == '*')
  590.         {
  591.             cover_bracket[ptr] = l;
  592.             token_list.push_back(Token(MUL, 0, ptr, ptr));
  593.             ptr++;
  594.         }
  595.         else if (expr[ptr] == '(')
  596.         {
  597.             int to_l = ptr;
  598.             int to_r = r_bracket[ptr];
  599.             Token token = parse(to_l, to_r);
  600.             token_list.push_back(token);
  601.             ptr = to_r + 1;
  602.  
  603.             cover_bracket[to_l] = l;
  604.             cover_bracket[to_r] = l;
  605.         }
  606.         else
  607.         {
  608.             assert(isdigit(expr[ptr]));
  609.            
  610.             int value = 0;
  611.             int old_ptr = ptr;
  612.  
  613.             while (ptr < r && isdigit(expr[ptr]))
  614.             {
  615.                 cover_bracket[ptr] = l;
  616.  
  617.                 value = mod_mul(value, 10);
  618.                 value = mod_add(value, expr[ptr] - '0');
  619.                 ptr++;
  620.             }
  621.  
  622.             token_list.push_back(Token(NUMBER, value, old_ptr, ptr - 1));
  623.         }
  624.     }
  625.  
  626.     BracketItem bracket_item = BracketItem(token_list);
  627.     bracket_item.real_a = l;
  628.     bracket_item.real_b = r;
  629.     bracket_items[l] = bracket_item;
  630.  
  631.     return Token(NUMBER, bracket_item.value, bracket_item.real_a, bracket_item.real_b);
  632. }
  633.  
  634. int solve(int a, int b)
  635. {
  636.     if (!brackets_checker.is_correct(a, b))
  637.         return -1;
  638.  
  639.     if (expr[a] == '+' || expr[a] == '*')
  640.         return -1;
  641.  
  642.     if (expr[b] == '+' || expr[b] == '*')
  643.         return -1;
  644.  
  645.     int l_br = cover_bracket[a];
  646.     int r_br = cover_bracket[b];
  647.    
  648.     assert(l_br == r_br);
  649.  
  650.     int ans = bracket_items[l_br].solve(a, b);
  651.    
  652.     return ans;
  653. }
  654.  
  655. void solve()
  656. {
  657.     expr = read_string();
  658.     expr = "(" + expr + ")";
  659.  
  660.     brackets_checker.init(expr);
  661.  
  662.     match_brackets();
  663.  
  664.     digit_tree.init(expr);
  665.  
  666.     parse(0, (int)expr.length() - 1);
  667.  
  668.     int q;
  669.     scanf("%d", &q);
  670.  
  671.     for (int it = 0; it < q; it++)
  672.     {
  673.         int a, b;
  674.         scanf("%d%d", &a, &b);
  675.         int ans = solve(a, b);
  676.         printf("%d\n", ans);
  677.     }
  678. }
  679.  
  680. int main()
  681. {
  682. #ifdef LOCAL
  683.     freopen("input.txt", "r", stdin);
  684.     //freopen("output.txt", "w", stdout);
  685. #endif
  686.  
  687.     solve();
  688.  
  689.     return 0;
  690. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement