fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <unistd.h>
  3. using namespace std;
  4.  
  5. #define mp make_pair
  6. #define pb push_back
  7. #define MOD 1000000007LL
  8. #define F first
  9. #define S second
  10. #define ll long long
  11.  
  12. typedef pair<int, int> pii;
  13. typedef pair<ll, ll> pll;
  14.  
  15. ll gcd(ll a, ll b)
  16. {
  17.     if(a == 0LL)
  18.         return b;
  19.     return gcd(b, a%b);
  20. }
  21.  
  22. const int N = 500005;
  23. int A[N], fst[N], lst[N], prev1[N], dp[N], id[N];
  24.  
  25. map<int, int> M[N];
  26.  
  27. struct Node{
  28.     int mn_fst, mx_lst, xorsum, mn_ind;
  29.  
  30.     void merge(Node& left, Node& right)
  31.     {
  32.         mn_fst = min(left.mn_fst, right.mn_fst);
  33.         mx_lst = max(left.mx_lst, right.mx_lst);
  34.         xorsum = left.xorsum^right.xorsum;
  35.         mn_ind = min(left.mn_ind, right.mn_ind);
  36.  
  37.         return;
  38.     }
  39.  
  40.     void assign(int a, int b, int c, int d)
  41.     {
  42.         mn_fst = a;
  43.         mx_lst = b;
  44.         xorsum = c;
  45.         mn_ind = d;
  46.  
  47.         return;
  48.     }
  49.  
  50. }tree[N<<2];
  51.  
  52. Node query(int node, int l, int r, int a, int b)
  53. {
  54.     if(l == a && r == b)
  55.         return tree[node];
  56.  
  57.     int mid = (l+r)>>1;
  58.     int left = node<<1;
  59.     int right = left + 1;
  60.  
  61.     if(b<=mid)
  62.         return query(left, l, mid, a, b);
  63.     else if(a>mid)
  64.         return query(right, mid+1, r, a, b);
  65.  
  66.     Node ans;
  67.     Node L, R;
  68.     L = query(left, l, mid, a, mid);
  69.     R = query(right, mid+1, r, mid+1, b);
  70.     ans.merge(L, R);
  71.  
  72.     return ans;
  73. }
  74.  
  75. void update(int node, int l, int r, int ind, Node val)
  76. {
  77.     if(l == r)
  78.     {
  79.         tree[node] = val;
  80.         return;
  81.     }
  82.  
  83.     int mid = (l+r)>>1;
  84.     int left = node<<1;
  85.     int right = left + 1;
  86.  
  87.     if(ind<=mid)
  88.         update(left, l, mid, ind, val);
  89.     else
  90.         update(right, mid+1, r, ind, val);
  91.  
  92.     tree[node].merge(tree[left], tree[right]);
  93.  
  94.     return;
  95. }
  96.  
  97. int main()
  98. {
  99.     // ios::sync_with_stdio(false);
  100.     // cin.tie(0);
  101.  
  102.     // freopen("in6.in", "r", stdin);
  103.     // freopen("out6.out", "w", stdout);
  104.  
  105.     // clock_t clk;
  106.     // clk = clock();
  107.  
  108.     int n, l, r;
  109.     scanf("%d", &n);
  110.     // cin >> n;
  111.  
  112.     for(int i = 0; i<N; i++)
  113.     {
  114.         fst[i] = n+1;
  115.         lst[i] = 0;
  116.         M[i].clear();
  117.     }
  118.  
  119.     for(int i = 1; i<=n; i++)
  120.     {
  121.         scanf("%d", &A[i]);
  122.         // cin >> A[i];
  123.         fst[A[i]] = min(fst[A[i]], i);
  124.         prev1[i] = lst[A[i]];
  125.         lst[A[i]] = i;
  126.     }
  127.  
  128.     Node temp, now;
  129.     id[0] = 1;
  130.  
  131.     for(int i = 1; i<=n; i++)
  132.     {
  133.         dp[i] = dp[i-1];
  134.  
  135.         if(prev1[i])
  136.         {
  137.             temp.assign(fst[A[i]], lst[A[i]], 0, MOD);
  138.             update(1, 1, n, prev1[i], temp);
  139.         }   
  140.  
  141.         temp.assign(fst[A[i]], lst[A[i]], A[i], MOD);
  142.         update(1, 1, n, i, temp);
  143.  
  144.         if(lst[A[i]] == i) // Necessary Condition for Valid Subarray
  145.         {
  146.             l = fst[A[i]];
  147.             r = lst[A[i]];
  148.  
  149.             now = query(1, 1, n, l, r);
  150.  
  151.             while(now.mx_lst == i)
  152.             {
  153.                 if(now.mn_fst == l)
  154.                     break;
  155.  
  156.                 // l = min(now.mn_fst, now.mn_ind);
  157.  
  158.                 l = now.mn_fst;
  159.  
  160.                 now = query(1, 1, n, l, r);
  161.             }
  162.  
  163.             // l = min(now.mn_fst, now.mn_ind);
  164.  
  165.             l = now.mn_fst;
  166.  
  167.             temp.assign(fst[A[i]], lst[A[i]], A[i], l);
  168.             update(1, 1, n, i, temp);
  169.  
  170.             if(now.mx_lst == i) // Valid Subarray
  171.             {
  172.                 id[i] = id[l-1];
  173.                 now = query(1, 1, n, id[i], i);
  174.  
  175.                 if(M[id[i]][now.xorsum] != 0)
  176.                     dp[i] = max(dp[i], dp[M[id[i]][now.xorsum]] + 1);
  177.                 else if(now.xorsum == 0)
  178.                     dp[i] = max(dp[i], dp[id[i]-1] + 1);
  179.  
  180.                 M[id[i]][now.xorsum] = i;
  181.             }
  182.             else
  183.                 id[i] = i+1;
  184.         }
  185.         else
  186.             id[i] = i+1;
  187.     }
  188.  
  189.     // cout << dp[n] << "\n";
  190.     printf("%d\n", dp[n]);
  191.  
  192.     // clk = clock() - clk;
  193.     // cout << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
  194.     // printf("Time: %lf\n", ((double)clk)/CLOCKS_PER_SEC);
  195.  
  196.     return 0;
  197. }
Success #stdin #stdout 0.02s 30596KB
comments (?)
stdin
copy 
6
1 1 2 3 3 2
stdout
copy 
1
https://ideone.com/RPNdnP
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!