Guest User

Untitled

a guest
Jan 17th, 2016
191
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // supersegments, O(n*sqrt(n)), by Errichto
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int nax = 1e6 + 5;
  6. int n;
  7. #define inf (n+1)
  8. int t[nax]; // input
  9. int tmp[nax];
  10. int nxt[nax]; // nxt[i] = index of the next occurrence of number t[i]
  11. int at_least[nax]; // at_least[i] = the lowest possible index j that interval [i, j] has enough occurrences of number t[i]
  12.  
  13. void calculate_nxt() {
  14.     for(int i = 1; i <= n; ++i) tmp[i] = inf;
  15.     for(int i = n; i >= 1; --i) {
  16.         nxt[i] = tmp[t[i]];
  17.         tmp[t[i]] = i;
  18.     }
  19.     // nxt[inf] = inf; // necessary or not? I'm not sure
  20. }
  21.  
  22. void calculate_at_least() {
  23.     for(int i = 1; i <= n; ++i) tmp[i] = 0;
  24.     for(int i = 1; i <= n; ++i) {
  25.         int x = t[i];
  26.         if(tmp[x] != 0) { // here is the first occurrence of number x
  27.             tmp[x] = nxt[tmp[x]];
  28.             at_least[i] = tmp[x];
  29.         }
  30.         else {
  31.             tmp[x] = i;
  32.             for(int rep = 0; rep < x - 1 && tmp[x] != inf; ++rep)
  33.                 tmp[x] = nxt[tmp[x]];
  34.             at_least[i] = tmp[x];
  35.         }
  36.     }
  37. }
  38.  
  39. int main() {
  40.     freopen("segments.in", "r", stdin);
  41.     freopen("segments.out", "w", stdout);
  42.    
  43.     scanf("%d", &n);
  44.     for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);
  45.     calculate_nxt();
  46.     calculate_at_least();
  47.    
  48.     set<int> first_occurrences;
  49.     long long ans = 0;
  50.     for(int A = n; A >= 1; --A) {
  51.         if(nxt[A] != inf) first_occurrences.erase(nxt[A]);
  52.         first_occurrences.insert(A);
  53.         set<int> :: iterator it = first_occurrences.begin();
  54.         int minB = A; // the minimum index of endpoint B; I increase it when I encounter a new number x - then I must move it to get at least x occurrences of x
  55.         int maxB = n; // the maximum index of endpoing B; I decrease it when I encounter a new number x - I can't get at least x+1 occurrences
  56.         while(it != first_occurrences.end()) {
  57.             int needed = at_least[*it];
  58.             if(needed == inf) break;
  59.             minB = max(minB, needed);
  60.             maxB = min(maxB, nxt[needed] - 1);
  61.             if(minB > maxB) break;
  62.             ++it;
  63.             if(it == first_occurrences.end() || minB < *it) ++ans;
  64.         }
  65.     }
  66.     printf("%lld\n", ans);
  67.     return 0;
  68. }
RAW Paste Data