Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // supersegments, O(n*sqrt(n)), by Errichto
- #include<bits/stdc++.h>
- using namespace std;
- const int nax = 1e6 + 5;
- int n;
- #define inf (n+1)
- int t[nax]; // input
- int tmp[nax];
- int nxt[nax]; // nxt[i] = index of the next occurrence of number t[i]
- int at_least[nax]; // at_least[i] = the lowest possible index j that interval [i, j] has enough occurrences of number t[i]
- void calculate_nxt() {
- for(int i = 1; i <= n; ++i) tmp[i] = inf;
- for(int i = n; i >= 1; --i) {
- nxt[i] = tmp[t[i]];
- tmp[t[i]] = i;
- }
- // nxt[inf] = inf; // necessary or not? I'm not sure
- }
- void calculate_at_least() {
- for(int i = 1; i <= n; ++i) tmp[i] = 0;
- for(int i = 1; i <= n; ++i) {
- int x = t[i];
- if(tmp[x] != 0) { // here is the first occurrence of number x
- tmp[x] = nxt[tmp[x]];
- at_least[i] = tmp[x];
- }
- else {
- tmp[x] = i;
- for(int rep = 0; rep < x - 1 && tmp[x] != inf; ++rep)
- tmp[x] = nxt[tmp[x]];
- at_least[i] = tmp[x];
- }
- }
- }
- int main() {
- freopen("segments.in", "r", stdin);
- freopen("segments.out", "w", stdout);
- scanf("%d", &n);
- for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);
- calculate_nxt();
- calculate_at_least();
- set<int> first_occurrences;
- long long ans = 0;
- for(int A = n; A >= 1; --A) {
- if(nxt[A] != inf) first_occurrences.erase(nxt[A]);
- first_occurrences.insert(A);
- set<int> :: iterator it = first_occurrences.begin();
- 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
- 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
- while(it != first_occurrences.end()) {
- int needed = at_least[*it];
- if(needed == inf) break;
- minB = max(minB, needed);
- maxB = min(maxB, nxt[needed] - 1);
- if(minB > maxB) break;
- ++it;
- if(it == first_occurrences.end() || minB < *it) ++ans;
- }
- }
- printf("%lld\n", ans);
- return 0;
- }
Add Comment
Please, Sign In to add comment