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