Guest User

Untitled

a guest
Jan 17th, 2016
222
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cassert>
  3. #include <tuple>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. const int N = 1 << 19;
  8.  
  9. vector<pair<int, int>> inc[N], dec[N];
  10. int n;
  11. vector<int> pos[N];
  12.  
  13. inline void add_rect(int l1, int r1, int l2, int r2) {
  14.     assert(0 <= l1 && l1 <= r1 && r1 <= l2 && l2 <= r2 && r2 <= n - 1);
  15.     inc[l1].emplace_back(l2, r2);
  16.     dec[r1].emplace_back(l2, r2);
  17. }
  18.  
  19. void process(int x, const vector<int>& pos) {
  20.     for (int i = 0; i + 2 < pos.size(); i++) {
  21.         int l = pos[i] + 1;
  22.         int r = pos[i + 1];
  23.         int l2 = pos[i + 1];
  24.         int r2 = (i + x < pos.size()) ? pos[i + x] - 1 : n - 1;
  25.         if (x != 1)
  26.             add_rect(l, r, l2, r2);
  27.         if (i + x + 2 < pos.size()) {
  28.             int l3 = pos[i + x + 1];
  29.             int r3 = n - 1;
  30.             add_rect(l, r, l3, r3);
  31.         }
  32.     }
  33. }
  34.  
  35. int Tmn[2 * N], Tcnt[2 * N];
  36. int Tadd[2 * N];
  37.  
  38. void add(int l, int r, int x, int L = 0, int R = N - 1, int v = 1) {
  39.     if (r < L || l > R)
  40.         return;
  41.     if (l <= L && R <= r) {
  42.         Tadd[v] += x;
  43.         return;
  44.     }
  45.     add(l, r, x, L, (L + R) / 2, 2 * v);
  46.     add(l, r, x, (L + R) / 2 + 1, R, 2 * v + 1);
  47.     Tmn[v] = min(Tmn[2 * v] + Tadd[2 * v], Tmn[2 * v + 1] + Tadd[2 * v + 1]);
  48.     Tcnt[v] = 0;
  49.     if (Tmn[v] == Tmn[2 * v] + Tadd[2 * v])
  50.         Tcnt[v] += Tcnt[2 * v];
  51.     if (Tmn[v] == Tmn[2 * v + 1] + Tadd[2 * v + 1])
  52.         Tcnt[v] += Tcnt[2 * v + 1];
  53. }
  54.  
  55. pair<int, int> get(int l, int r, int L = 0, int R = N - 1, int v = 1) {
  56.     if (r < L || l > R) {
  57.         return make_pair(N + 42, -42);
  58.     } else if (l <= L && R <= r) {
  59.         return make_pair(Tmn[v] + Tadd[v], Tcnt[v]);
  60.     } else {
  61.         int mn1, cnt1, mn2, cnt2;
  62.         tie(mn1, cnt1) = get(l, r, L, (L + R) / 2, 2 * v);
  63.         tie(mn2, cnt2) = get(l, r, (L + R) / 2 + 1, R, 2 * v + 1);
  64.         int mn = min(mn1, mn2);
  65.         int cnt = 0;
  66.         if (mn == mn1)
  67.             cnt += cnt1;
  68.         if (mn == mn2)
  69.             cnt += cnt2;
  70.         return make_pair(mn + Tadd[v], cnt);
  71.     }
  72. }
  73.  
  74. int main() {
  75.     freopen("segments.in", "r", stdin);
  76.     freopen("segments.out", "w", stdout);
  77.    
  78.     scanf("%d", &n);
  79.     for (int i = N; i < 2 * N; i++)
  80.         Tcnt[i] = 1;
  81.     for (int i = N - 1; i > 0; i--)
  82.         Tcnt[i] = Tcnt[2 * i] + Tcnt[2 * i + 1];
  83.     for (int i = 0; i < n; i++) {
  84.         int x;
  85.         scanf("%d", &x);
  86.         pos[x].push_back(i);
  87.     }
  88.     for (int i = 1; i <= n; i++) {
  89.         if (pos[i].empty())
  90.             continue;
  91.         pos[i].insert(pos[i].begin(), -1);
  92.         pos[i].insert(pos[i].end(), n);
  93.         process(i, pos[i]);
  94.     }
  95.     long long ans = 0;
  96.     for (int x = 0; x < n; x++) {
  97.         for (auto seg : inc[x]) {
  98.             add(seg.first, seg.second, 1);
  99.         }
  100.         int mn, cnt;
  101.         tie(mn, cnt) = get(x, n - 1);
  102.         ans += (mn == 0) ? cnt : 0;
  103.         for (auto seg : dec[x]) {
  104.             add(seg.first, seg.second, -1);
  105.         }
  106.     }
  107.     printf("%lld\n", ans);
  108. }
RAW Paste Data