 # 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