fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void fileIO()
  5. {
  6.     ios_base::sync_with_stdio(0);
  7.     cin.tie(0);
  8.     cout.tie(0);
  9. #ifndef ONLINE_JUDGE
  10.     freopen("E:\\Codes\\PS codes\\JUST\\input.txt", "r", stdin);
  11.     freopen("E:\\Codes\\PS codes\\JUST\\output.txt", "w", stdout);
  12. #endif
  13. }
  14.  
  15. struct SparseTable
  16. {
  17.     vector<int> logs;
  18.     vector<vector<int>> table;
  19.     vector<int> powers;
  20.     SparseTable(int n, vector<int> &v)
  21.     {
  22.         logs.resize(n + 2);
  23.         for (int i = 2; i <= n; i++)
  24.         {
  25.             logs[i] = logs[i / 2] + 1;
  26.         }
  27.         int j = 0, val = 1;
  28.         while (j <= logs[n])
  29.         {
  30.             powers.push_back(val);
  31.             j++;
  32.             val *= 2;
  33.         }
  34.         table = vector<vector<int>>(n + 2, vector<int>(logs[n] + 1));
  35.         for (int i = 0; i < n; i++)
  36.         {
  37.             table[i][0] = v[i];
  38.         }
  39.         for (int i = 1; i <= logs[n]; i++)
  40.         {
  41.             for (int f = 0; f + (1ll << i) - 1 < n; f++)
  42.             {
  43.                 table[f][i] = max(table[f][i - 1], table[f + (1ll << (i - 1))][i - 1]);
  44.             }
  45.         }
  46.     }
  47.     int query(const int &l, const int &r)
  48.     {
  49.         int lg = logs[r - l + 1];
  50.         return max(table[l][lg], table[r - (1ll << lg) + 1][lg]);
  51.     }
  52. };
  53. vector<int> ans;
  54. struct segTree
  55. {
  56.     struct Node
  57.     {
  58.         int mxr, l, i;
  59.         Node()
  60.         {
  61.             mxr = l = i = -1;
  62.         }
  63.         Node(array<int, 3> a)
  64.         {
  65.             l = a[0];
  66.             mxr = a[1];
  67.             i = a[2];
  68.         }
  69.         Node operator+(const Node &other) const
  70.         {
  71.             Node ret;
  72.             ret.mxr = max(mxr, other.mxr);
  73.             return ret;
  74.         }
  75.     };
  76.     vector<Node> tree;
  77.     segTree(int n)
  78.     {
  79.         int sz = 1;
  80.         while (sz < n)
  81.             sz *= 2;
  82.         tree.resize(sz * 2);
  83.     }
  84.     void pointUpdate(int node, int st, int en, int idx, array<int, 3> a)
  85.     {
  86.         if (st == en)
  87.         {
  88.             tree[node] = Node(a);
  89.             return;
  90.         }
  91.         int mid = st + en >> 1;
  92.         if (idx <= mid)
  93.             pointUpdate(node * 2, st, mid, idx, a);
  94.         else
  95.             pointUpdate(node * 2 + 1, mid + 1, en, idx, a);
  96.         tree[node] = tree[node * 2] + tree[node * 2 + 1];
  97.     }
  98.     void rangeUpdate(int node, int st, int en, int l, int r, int mxR, int k)
  99.     {
  100.         if (st > r or l > en or tree[node].mxr < mxR)
  101.             return;
  102.         if (st == en)
  103.         {
  104.             ans[tree[node].i] = k;
  105.             tree[node].mxr = -1;
  106.             return;
  107.         }
  108.         int mid = st + en >> 1;
  109.         rangeUpdate(node * 2, st, mid, l, r, mxR, k);
  110.         rangeUpdate(node * 2 + 1, mid + 1, en, l, r, mxR, k);
  111.         tree[node] = tree[node * 2] + tree[node * 2 + 1];
  112.     }
  113. };
  114.  
  115. void Striker()
  116. {
  117.     int n;
  118.     cin >> n;
  119.     vector<int> a(n);
  120.     map<int, vector<int>> mp;
  121.     for (int i = 0; i < n; i++)
  122.     {
  123.         cin >> a[i];
  124.         mp[a[i]].push_back(i);
  125.     }
  126.     SparseTable table(n, a);
  127.     vector<array<int, 3>> all, qu;
  128.     for (auto &[val, v] : mp)
  129.     {
  130.         for (int i = 1; i < v.size(); i++)
  131.         {
  132.             int l = v[i - 1], r = v[i];
  133.             auto res = table.query(l, r);
  134.             if (res <= val)
  135.                 continue;
  136.             all.push_back({res, l, r});
  137.             // cout << l << " " << r << " " << res << "\n";
  138.         }
  139.     }
  140.  
  141.     int q;
  142.     cin >> q;
  143.     for (int i = 0; i < q; i++)
  144.     {
  145.         int l, r;
  146.         cin >> l >> r;
  147.         l--, r--;
  148.         qu.push_back({l, r, i});
  149.     }
  150.  
  151.     sort(all.rbegin(), all.rend());
  152.     sort(qu.begin(), qu.end());
  153.     ans = vector<int>(q + 2);
  154.     int frq[n + 2]{}, sz = n + q;
  155.     sz *= 2;
  156.     segTree tree(sz);
  157.     int cnt = 0;
  158.     for (auto &[l, r, idx] : qu)
  159.     {
  160.         tree.pointUpdate(1, 0, sz - 1, cnt, {l, r, idx});
  161.         frq[l]++;
  162.         cnt++;
  163.     }
  164.     for (int i = 1; i < n; i++)
  165.         frq[i] += frq[i - 1];
  166.     for (auto &[k, l, r] : all)
  167.     {
  168.         tree.rangeUpdate(1, 0, sz - 1, 0, frq[l] - 1, r, k);
  169.     }
  170.     for (int i = 0; i < q; i++)
  171.     {
  172.         cout << ans[i] << "\n";
  173.     }
  174. }
  175.  
  176. signed main()
  177. {
  178.     fileIO();
  179.     int _t = 1;
  180.     cin >> _t;
  181.     for (int i = 0; i < _t; ++i)
  182.     {
  183.         Striker();
  184.     }
  185. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/nzEasQ
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!