API tools faq
paste
Advertisement
libobil

Untitled

libobil
Jan 17th, 2023
1,094
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 15.33 KB | None | 0 0
raw download clone embed print report
  1. // Was going to write it with treap :)
  2.  
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <limits.h>
  6. #include <numeric>
  7. #include <cassert>
  8. #include <bitset>
  9. #include <vector>
  10. #include <stack>
  11. #include <cmath>
  12.  
  13. typedef long long llong;
  14. const int MAXN = 200000 + 10;
  15. const int MOD = 1000003967;
  16. const int MAXLOG = 18;
  17. const int INF = 1e9;
  18.  
  19. const int TREE_SIZE = MAXN*MAXLOG;
  20. int bracketNum[256];
  21. char opposite[256];
  22. llong base[MAXN];
  23. struct Node
  24. {
  25.     int hash;
  26.     int oppHash;
  27.     int hashSize;
  28.     int active;
  29.     int lazy;
  30.     std::bitset <8> has;
  31.  
  32.     Node()
  33.     {
  34.         hashSize = active = 0;
  35.         hash = oppHash = 0;
  36.         lazy = -1;
  37.     }
  38. };
  39.  
  40.  
  41. int n, q;
  42. int treeCnt;
  43. std::string s;
  44. std::stack <char> st;
  45. Node tree[TREE_SIZE * 4 + 1];
  46. std::vector <int> treePos[4*MAXN];
  47. std::vector <int> popped[4*MAXN];
  48.  
  49. inline Node combine(Node left, Node right)
  50. {
  51.     if (left.hashSize == -1)
  52.     {
  53.         return right;
  54.     }
  55.  
  56.     if (right.hashSize == -1)
  57.     {
  58.         return left;
  59.     }
  60.  
  61.     Node ans;
  62.     ans.hash = (1LL * base[right.hashSize] * left.hash + right.hash) % MOD;
  63.     ans.oppHash = (left.oppHash + 1LL * right.oppHash * base[left.hashSize]) % MOD;
  64.     ans.hashSize = left.hashSize + right.hashSize;
  65.     ans.has = left.has | right.has;
  66.     return ans;
  67. }
  68.  
  69. inline void push(int node, int l, int r)
  70. {
  71.     if (tree[node].lazy == -1)
  72.     {
  73.         return;
  74.     }
  75.  
  76.     assert(tree[node].lazy != 0);
  77.     tree[node].hash = tree[node].oppHash = 0;
  78.     tree[node].hashSize = 0;
  79.     tree[node].active = tree[node].lazy;
  80.     tree[node].has.reset();
  81.  
  82.     if (l != r)
  83.     {
  84.         tree[2*node].lazy = tree[node].lazy;
  85.         tree[2*node + 1].lazy = tree[node].lazy;
  86.     }
  87.  
  88.     tree[node].lazy = -1;
  89. }
  90.  
  91. void updateSegment(int l, int r, int node, int queryPos, char bracket, int active)
  92. {
  93.     push(node, l, r);
  94.     if (queryPos < l || r < queryPos) return;
  95.     // if (queryPos >= 6 && queryPos <= 8) std::cout << "update segment: " << l << ' ' << r << ' ' << node << ' ' << queryPos << ' ' << bracket << ' ' << active << '\n';
  96.     if (l == r)
  97.     {
  98.         if (active == 0)
  99.         {
  100.             tree[node].hash = bracketNum[bracket];
  101.             tree[node].oppHash = bracketNum[opposite[bracket]];
  102.             tree[node].hashSize = 1;
  103.         } else
  104.         {
  105.             tree[node].hash = 0;
  106.             tree[node].oppHash = 0;
  107.             tree[node].hashSize = 0;
  108.         }
  109.  
  110.         tree[node].active = active;
  111.         tree[node].has[bracketNum[bracket]] = 1;
  112.         return;
  113.     }
  114.  
  115.     int mid = (l + r) / 2;
  116.     updateSegment(l, mid, 2*node, queryPos, bracket, active);
  117.     updateSegment(mid + 1, r, 2*node + 1, queryPos, bracket, active);
  118.     tree[node] = combine(tree[2*node], tree[2*node + 1]);
  119. }
  120.  
  121. void updateLazy(int l, int r, int node, int queryL, int queryR, int queryValue)
  122. {
  123.     push(node, l, r);
  124.     if (queryR <  l || r  < queryL) return;
  125.     if (queryL <= l && r <= queryR) return;
  126.     {
  127.         tree[node].lazy = queryValue;
  128.         push(node, l, r);
  129.         return;
  130.     }
  131.  
  132.     int mid = (l + r) / 2;
  133.     updateLazy(l, mid, 2*node, queryL, queryR, queryValue);
  134.     updateLazy(mid + 1, r, 2*node + 1, queryL, queryR, queryValue);
  135.     tree[node] = combine(tree[2*node], tree[2*node + 1]);
  136. }
  137.  
  138. Node queryNodeSegment(int l, int r, int node, int queryL, int queryR)
  139. {
  140.     // std::cout << "here: " << l << ' ' << r << ' ' << queryL << ' ' << queryR << '\n';
  141.     push(node, l, r);
  142.     if (queryL <= l && r <= queryR)
  143.     {
  144.         // std::cout << "in if: " << node << ' ' << 4*TREE_SIZE << "\n";
  145.         return tree[node];
  146.     }
  147.  
  148.     int mid = (l + r) / 2;
  149.     Node ans; ans.hashSize = -1;
  150.     if (queryL <= mid) ans = combine(ans, queryNodeSegment(l, mid, 2*node, queryL, queryR));
  151.     if (mid + 1 <= queryR) ans = combine(ans, queryNodeSegment(mid + 1, r, 2*node + 1, queryL, queryR));
  152.     // std::cout << "done: " << l << ' ' << r << '\n';
  153.     return ans;
  154. }
  155.  
  156. Node searchRight(int l, int r, int node, int queryL, int queryR, int k)
  157. {
  158.     // std::cout << "search right: " << l << ' ' << r << ' ' << node << ' ' << queryL << ' ' << queryR << ' ' << k << '\n';
  159.     assert(k != 0);
  160.     push(node, l, r);
  161.     int mid = (l + r) / 2;
  162.     if (l != r) push(2*node + 1, mid + 1, r);
  163.     if (queryL <= l && r <= queryR)
  164.     {
  165.         if (l == r) return tree[node];
  166.         if (tree[2*node + 1].hashSize >= k) return searchRight(mid + 1, r, 2*node + 1, queryL, queryR, k);
  167.         return combine(searchRight(l, mid, 2*node, queryL, queryR, k - tree[2*node + 1].hashSize), tree[2*node + 1]);
  168.     }
  169.  
  170.     Node ans; ans.hashSize = -1;
  171.     if (mid + 1 <= queryR && tree[2*node + 1].hashSize >= 1)
  172.     {
  173.         Node right = searchRight(mid + 1, r, 2*node + 1, queryL, queryR, k);
  174.         if (right.hashSize == k) return right;
  175.         k -= right.hashSize;
  176.         ans = combine(ans, right);
  177.     }
  178.  
  179.     if (k > 0)
  180.     {
  181.         assert(queryL <= mid);
  182.         Node left = searchRight(l, mid, 2*node, queryL, queryR, k);
  183.         ans = combine(left, ans);
  184.     }
  185.  
  186.     return ans;
  187. }
  188.  
  189. Node searchLeft(int l, int r, int node, int queryL, int queryR, int k)
  190. {
  191.     assert(k != 0);
  192.     push(node, l, r);
  193.     int mid = (l + r) / 2;
  194.     if (l != r) push(2*node, l, mid);
  195.     if (queryL <= l && r <= queryR)
  196.     {
  197.         if (l == r) return tree[node];
  198.         if (tree[2*node].hashSize >= k) return searchLeft(l, mid, 2*node, queryL, queryR, k);
  199.         return combine(tree[2*node], searchLeft(mid + 1, r, 2*node + 1, queryL, queryR, k - tree[2*node].hashSize));
  200.     }
  201.  
  202.     Node ans; ans.hashSize = -1;
  203.     if (queryL <= mid && tree[2*node].hashSize >= 1)
  204.     {
  205.         Node left = searchLeft(l, mid, 2*node, queryL, queryR, k);
  206.         if (left.hashSize == k) return left;
  207.         k -= left.hashSize;
  208.         ans = combine(left, ans);
  209.     }
  210.  
  211.     if (k > 0)
  212.     {
  213.         Node right = searchLeft(mid + 1, r, 2*node + 1, queryL, queryR, k);
  214.         ans = combine(ans, right);
  215.     }
  216.  
  217.     return ans;
  218. }
  219.  
  220. std::pair <int,int> searchRightPos(int l, int r, int node, int queryL, int queryR, int k)
  221. {
  222.     assert(k != 0);
  223.     push(node, l, r);
  224.     if (queryR <  l || r  < queryL) return {-1, 0};
  225.     int mid = (l + r) / 2;
  226.     if (l != r) push(2*node + 1, mid + 1, r);
  227.     if (queryL <= l && r <= queryR)
  228.     {
  229.         if (l == r) return {l, tree[node].hashSize};
  230.         if (tree[2*node + 1].hashSize >= k) return {searchRightPos(mid + 1, r, 2*node + 1, queryL, queryR, k).first, k};
  231.         auto res = searchRightPos(l, mid, 2*node, queryL, queryR, k - tree[2*node + 1].hashSize);
  232.         return {res.first, res.second + tree[2*node + 1].hashSize};
  233.     }
  234.  
  235.     int removed = 0;
  236.     if (mid + 1 <= queryR)
  237.     {
  238.         auto res = searchRightPos(mid + 1, r, 2*node + 1, queryL, queryR, k);
  239.         if (res.second >= k) return res;
  240.         k -= res.second;
  241.         removed = res.second;
  242.     }
  243.  
  244.     auto res = searchRightPos(l, mid, 2*node, queryL, queryR, k);
  245.     return {res.first, res.second + removed};
  246. }
  247.  
  248. std::pair <int,int> searchLeftPos(int l, int r, int node, int queryL, int queryR, int k)
  249. {
  250.     assert(k != 0);
  251.     push(node, l, r);
  252.     if (queryR <  l || r  < queryL) return {-1, 0};
  253.     int mid = (l + r) / 2;
  254.     if (l != r) push(2*node, mid + 1, r);
  255.     // std::cout << "search left: " << l << ' ' << r << ' ' << node << ' ' << queryL << ' ' << queryR << ' ' << k << ' ' << tree[node].hashSize << '\n';
  256.     if (queryL <= l && r <= queryR)
  257.     {
  258.         if (l == r) return {l, tree[node].hashSize};
  259.         if (tree[2*node].hashSize >= k) return {searchLeftPos(l, mid, 2*node, queryL, queryR, k).first, k};
  260.         auto res = searchLeftPos(mid + 1, r, 2*node + 1, queryL, queryR, k - tree[2*node].hashSize);
  261.         return {res.first, res.second + tree[2*node].hashSize};
  262.     }
  263.  
  264.     int removed = 0;
  265.     if (queryL <= mid)
  266.     {
  267.         auto res = searchLeftPos(l, mid, 2*node, queryL, queryR, k);
  268.         if (res.second >= k) return res;
  269.         k -= res.second;
  270.         removed = res.second;
  271.     }
  272.  
  273.     auto res = searchLeftPos(mid + 1, r, 2*node + 1, queryL, queryR, k);
  274.     return {res.first, res.second + removed};
  275. }
  276.  
  277. void buildTree(int l, int r, int node)
  278. {
  279.     if (l != r)
  280.     {
  281.         int mid = (l + r) / 2;
  282.         buildTree(l, mid, 2*node);
  283.         buildTree(mid + 1, r, 2*node + 1);
  284.     }
  285.  
  286.     treePos[node].resize(r - l + 1);
  287.     popped[node].resize(r - l + 1);
  288.     while (!st.empty()) st.pop();
  289.     for (int i = l ; i <= r ; ++i)
  290.     {
  291.         treePos[node][i - l] = ++treeCnt;
  292.         if (!st.empty() && s[st.top()] == opposite[(int)s[i]])
  293.         {
  294.             popped[node][st.top() - l] = 2;
  295.             popped[node][i - l] = 1;
  296.             st.pop();
  297.         } else st.push(i);
  298.     }
  299.  
  300.     for (int i = l ; i <= r ; ++i)
  301.     {
  302.         // if (treePos[node][i - l] >= 6 && treePos[node][i - l] <= 8) std::cout << "update here: " << i << ' ' << treePos[node][i - l] << ' ' << popped[node][i - l] << '\n';
  303.         updateSegment(1, TREE_SIZE, 1, treePos[node][i - l], s[i], popped[node][i - l]);
  304.     }
  305. }
  306.  
  307. struct stackElement
  308. {
  309.     int l, r;
  310. };
  311.  
  312. std::vector <stackElement> queryNodes;
  313. std::vector <stackElement> nodeStack;
  314. void query(int l, int r, int node, int queryL, int queryR)
  315. {
  316.     // std::cout << "node: " << l << ' ' << r << ' ' << queryL << ' ' << queryR << '\n';
  317.     if (queryL <= l && r <= queryR)
  318.     {
  319.         // std::cout << "in if!!!\n" << std::flush;
  320.         // std::cout << "push: " << treePos[node].size() << ' ' << std::flush << ' ' << treePos[node][0] << ' ' << treePos[node].back() << '\n' << std::flush;
  321.         queryNodes.push_back({treePos[node][0], treePos[node].back()});
  322.         return;
  323.     }
  324.  
  325.     int mid = (l + r) / 2;
  326.     if (queryL <= mid) query(l, mid, 2*node, queryL, queryR);
  327.     if (mid + 1 <= queryR) query(mid + 1, r, 2*node + 1, queryL, queryR);
  328. }
  329.  
  330. inline std::string answerQuery(int l, int r)
  331. {
  332.     while (!queryNodes.empty())
  333.     {
  334.         queryNodes.pop_back();
  335.     }
  336.  
  337.     while (!nodeStack.empty())
  338.     {
  339.         nodeStack.pop_back();
  340.     }
  341.  
  342.     // std::cout << "before query\n";
  343.     query(1, n, 1, l, r);
  344.     // std::cout << "done query\n" << std::flush;
  345.     for (int i = 0 ; i < queryNodes.size() ; ++i)
  346.     {
  347.         Node res = queryNodeSegment(1, TREE_SIZE, 1, queryNodes[i].l, queryNodes[i].r); // std::cout << "done with query\n" << std::flush;
  348.         // std::cout << "hereerere: " << queryNodes[i].l << ' ' << queryNodes[i].r << ' ' << res.hashSize << ' ' << res.hash << ' ' << res.oppHash << '\n';
  349.         if (res.hashSize == 0) continue;
  350.         // std::cout << "after query node: " << nodeStack.size() << "\n" << std::flush;
  351.         while (!nodeStack.empty() && queryNodes[i].l <= queryNodes[i].r)
  352.         {
  353.             Node toPush = queryNodeSegment(1, TREE_SIZE, 1, queryNodes[i].l, queryNodes[i].r);
  354.             Node curr = queryNodeSegment(1, TREE_SIZE, 1, nodeStack.back().l, nodeStack.back().r);
  355.             if (toPush.hashSize < curr.hashSize) break;
  356.             Node left = searchLeft(1, TREE_SIZE, 1, queryNodes[i].l, queryNodes[i].r, curr.hashSize);
  357.             // std::cout << "lefttt issss: " << queryNodes[i].l << ' ' << queryNodes[i].r << ' ' << toPush.hashSize << ' ' << left.hash << ' ' << left.oppHash << ' ' << curr.hash << '\n' << std::flush;
  358.             if (curr.hash != left.oppHash) break;
  359.             std::pair <int,int> leftSearch = searchLeftPos(1, TREE_SIZE, 1, queryNodes[i].l, queryNodes[i].r, curr.hashSize + 1);
  360.             // std::cout << "searched left: " << leftSearch.first << ' ' << leftSearch.second << ' ' << queryNodes[i].l << ' ' << queryNodes[i].r << ' ' << toPush.hashSize << '\n';
  361.             if (curr.hashSize + 1 <= toPush.hashSize) queryNodes[i].l = leftSearch.first;
  362.             else queryNodes[i].l = INF;
  363.             assert(queryNodes[i].l != -1);
  364.             // std::cout << "heeere\n";
  365.             nodeStack.pop_back();
  366.         }
  367.  
  368.         // std::cout << "here size: " << nodeStack.size() << ' ' << queryNodes[i].l << ' ' << queryNodes[i].r << '\n' << std::flush;
  369.         if (queryNodes[i].l > queryNodes[i].r) continue;
  370.         if (nodeStack.empty()) nodeStack.push_back(queryNodes[i]);
  371.         else
  372.         {
  373.             // std::cout << "in else\n" << std::flush;
  374.             int ll = 0, rr = std::min(queryNodeSegment(1, TREE_SIZE, 1, nodeStack.back().l, nodeStack.back().r).hashSize, queryNodeSegment(1, TREE_SIZE, 1, queryNodes[i].l, queryNodes[i].r).hashSize) + 1, mid;
  375.             while (ll < rr - 1)
  376.             {
  377.                 mid = (ll + rr) / 2;
  378.                 // std::cout << "binaryy: " << ll << ' ' << rr << '\n' << std::flush;
  379.                 Node leftHash = searchRight(1, TREE_SIZE, 1, nodeStack.back().l, nodeStack.back().r, mid);
  380.                 // std::cout << "done right\n" << std::flush;
  381.                 Node rightHash = searchLeft(1, TREE_SIZE, 1, queryNodes[i].l, queryNodes[i].r, mid);
  382.                 // std::cout << "done queries\n" << std::flush;
  383.                 if (leftHash.oppHash == rightHash.hash) ll = mid;
  384.                 else rr = mid;
  385.             }
  386.  
  387.             // std::cout << "done binary: " << ll << ' ' << rr << '\n';
  388.             if (rr <= queryNodeSegment(1, TREE_SIZE, 1, nodeStack.back().l, nodeStack.back().r).hashSize) nodeStack.back().r = searchRightPos(1, TREE_SIZE, 1, nodeStack.back().l, nodeStack.back().r, rr).first;
  389.             else nodeStack.pop_back();
  390.             assert(nodeStack.back().r != -1);
  391.             if (rr <= queryNodeSegment(1, TREE_SIZE, 1, queryNodes[i].l, queryNodes[i].r).hashSize)
  392.             {
  393.                 queryNodes[i].l = searchLeftPos(1, TREE_SIZE, 1, queryNodes[i].l, queryNodes[i].r, rr).first;
  394.                 nodeStack.push_back(queryNodes[i]);
  395.             }
  396.         }
  397.     }
  398.  
  399.     if (nodeStack.empty()) return "Yes";
  400.     return "No";
  401. }
  402.  
  403. void solve()
  404. {
  405.     base[0] = 1;
  406.     for (int i = 1 ; i <= n ; ++i)
  407.     {
  408.         base[i] = (base[i - 1] * 9) % MOD;
  409.     }
  410.  
  411.     buildTree(1, n, 1);
  412.     int qType, l, r;
  413.     for (int i = 1 ; i <= q ; ++i)
  414.     {
  415.         std::cin >> qType;
  416.         if (qType == 2)
  417.         {
  418.             std::cin >> l >> r;
  419.             std::cout << answerQuery(l, r) << '\n';
  420.             continue;
  421.         }
  422.        
  423.         int pos;
  424.         char symbol;
  425.         std::cin >> pos >> symbol;
  426.     }
  427. }
  428.  
  429. void read()
  430. {
  431.     std::cin >> n;
  432.     std::cin >> s; s = ' ' + s;
  433.     std::cin >> q;
  434. }
  435.  
  436. void fastIO()
  437. {
  438.     std::ios_base :: sync_with_stdio(0);
  439.     std::cout.tie(nullptr);
  440.     std::cin.tie(nullptr);
  441. }
  442.  
  443. void initialize()
  444. {
  445.     opposite['('] = ')'; bracketNum['('] = 1;
  446.     opposite[')'] = '('; bracketNum[')'] = 2;
  447.     opposite['{'] = '}'; bracketNum['{'] = 3;
  448.     opposite['}'] = '{'; bracketNum['}'] = 4;
  449.     opposite['['] = ']'; bracketNum['['] = 5;
  450.     opposite[']'] = '['; bracketNum[']'] = 6;
  451.     opposite['<'] = '>'; bracketNum['<'] = 7;
  452.     opposite['>'] = '<'; bracketNum['>'] = 8;
  453. }
  454.  
  455. int main()
  456. {
  457.     srand(584068701);
  458.     initialize();
  459.     // fastIO();
  460.     read();
  461.     solve();
  462.  
  463.     return 0;
  464. }
  465.  
  466.  
  467. /*
  468. 10
  469. >())(][<}{
  470. 45
  471. 2 1 1
  472. 2 1 2
  473. 2 1 3
  474. 2 1 4
  475. 2 1 5
  476. 2 1 6
  477. 2 1 7
  478. 2 1 8
  479. 2 1 9
  480. 2 1 10
  481. 2 2 2
  482. 2 2 3
  483. 2 2 4
  484. 2 2 5
  485. 2 2 6
  486. 2 2 7
  487. 2 2 8
  488. 2 2 9
  489. 2 2 10
  490. 2 3 3
  491. 2 3 4
  492. 2 3 5
  493. 2 3 6
  494. 2 3 7
  495. 2 3 8
  496. 2 3 9
  497. 2 3 10
  498. 2 4 4
  499. 2 4 5
  500. 2 4 6
  501. 2 4 7
  502. 2 4 8
  503. 2 4 9
  504. 2 4 10
  505. 2 5 5
  506. 2 5 6
  507. 2 5 7
  508. 2 5 8
  509. 2 5 9
  510. 2 5 10
  511. 2 6 6
  512. 2 6 7
  513. 2 6 8
  514. 2 6 9
  515. 2 6 10
  516. 2 7 7
  517. 2 7 8
  518. 2 7 9
  519. 2 7 10
  520. 2 8 8
  521. 2 8 9
  522. 2 8 10
  523. 2 9 9
  524. 2 9 10
  525. 2 10 10
  526. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!