fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. struct Query
  9. {
  10.     int mobius, id, l, r;
  11.  
  12.     Query(int mobius = 0, int id = 0, int l = 0, int r = 0) :
  13.         mobius(mobius), id(id), l(l), r(r) {};
  14. };
  15. struct Segment_Tree
  16. {
  17.     vector<ll> tree, lazy;
  18.  
  19.     Segment_Tree(int n = 0)
  20.     {
  21.         tree.assign(4 * n + 10, 0);
  22.         lazy.assign(4 * n + 10, 0);
  23.     }
  24.     void push(int id, int l, int r)
  25.     {
  26.         if (lazy[id] == 0)
  27.             return ;
  28.         int m = l + r >> 1;
  29.         tree[id << 1] += (m - l + 1) * lazy[id];
  30.         tree[id << 1 | 1] += (r - m) * lazy[id];
  31.         lazy[id << 1] += lazy[id];
  32.         lazy[id << 1 | 1] += lazy[id];
  33.         lazy[id] = 0;
  34.     }
  35.     void update(int id, int l, int r, int u, int v, int val)
  36.     {
  37.         if (r < u || l > v)
  38.             return ;
  39.         if (u <= l && r <= v)
  40.         {
  41.             tree[id] += val * (r - l + 1);
  42.             lazy[id] += val;
  43.             return ;
  44.         }
  45.         int m = l + r >> 1;
  46.         push(id, l, r);
  47.         update(id << 1, l, m, u, v, val);
  48.         update(id << 1 | 1, m + 1, r, u, v, val);
  49.         tree[id] = tree[id << 1] + tree[id << 1 | 1];
  50.     }
  51.     ll get(int id, int l, int r, int u, int v)
  52.     {
  53.         if (r < u || l > v)
  54.             return 0;
  55.         if (u <= l && r <= v)
  56.             return tree[id];
  57.         int m = l + r >> 1;
  58.         push(id, l, r);
  59.         return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
  60.     }
  61. };
  62.  
  63. const int maxn = 1e6;
  64. const int INF = 1e9;
  65.  
  66. int n, q, l[maxn + 10], r[maxn + 10], pre[maxn + 10], a[maxn + 10], ql[maxn + 10], qr[maxn + 10];
  67. vector<int> st;
  68. vector<Query> qrs[maxn + 10];
  69. ll ans[maxn + 10];
  70. Segment_Tree smt;
  71.  
  72. int main()
  73. {
  74.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  75.     if (fopen("BAI2.INP", "r"))
  76.     {
  77.         freopen("BAI2.INP", "r", stdin);
  78.         freopen("BAI2.OUT", "w", stdout);
  79.     }
  80.  
  81.     cin >> n >> q;
  82.     smt= Segment_Tree(n);
  83.     for (int i = 1; i <= n; i++)
  84.         cin >> a[i];
  85.     st.push_back(0);
  86.     a[0] = INF;
  87.     for (int i = 1; i <= n; i++)
  88.     {
  89.         while (a[st.back()] < a[i])
  90.             st.pop_back();
  91.         l[i] = st.back() + 1;
  92.         st.push_back(i);
  93.     }
  94.     st.clear();
  95.     a[n + 1] = INF;
  96.     st.push_back(n + 1);
  97.     for (int i = n; i >= 1; i--)
  98.     {
  99.         while (a[st.back()] < a[i])
  100.             st.pop_back();
  101.         r[i] = st.back() - 1;
  102.         st.push_back(i);
  103.     }
  104.     for (int i = 1; i <= q; i++)
  105.         cin >> ql[i];
  106.     for (int i = 1; i <= q; i++)
  107.         cin >> qr[i];
  108.     for (int i = 1; i <= q; i++)
  109.     {
  110.         qrs[ql[i] - 1].push_back(Query(-1, i, ql[i], qr[i]));
  111.         qrs[qr[i]].push_back(Query(1, i, ql[i], qr[i]));
  112.     }
  113.     for (int i = 1; i <= n; i++)
  114.     {
  115.         smt.update(1, 1, n, l[i], r[i], 1);
  116.         for (Query x : qrs[i])
  117.             ans[x.id] += x.mobius * smt.get(1, 1, n, x.l, x.r);
  118.     }
  119.     for (int i = 1; i <= q; i++)
  120.         cout << ans[i] << ' ';
  121. }
  122.  
Success #stdin #stdout 0.01s 30296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dKAs11
language:
C++14 (gcc 8.3)
created:
133 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!