Editorial for Bedao Grand Contest 07 - TRIP


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

int fenwick[maxn];
map<int, int> last;

int main() {
  freopen("trip.inp", "r", stdin);
  freopen("trip.out", "w", stdout);
  long long ans = 0;

  int n; cin >> n;
  vector<int> s(n);
  for(int i = 0; i < n; ++i) cin >> s[i];

  for(int i = 1; i <= s.size(); ++i) {
    int c = s[i - 1];
    int prv = (last.count(c) ? last[c] : 0);
    for(int j = i; j > 0; j -= j & -j) ans += fenwick[j];
    for(int j = prv; j > 0; j -= j & -j) ans -= fenwick[j];
    if(prv > 0) for(int j = prv; j < maxn; j += j & -j) fenwick[j]--;
    for(int j = i; j < maxn; j += j & -j) fenwick[j]++;
    last[c] = i;
  }

  cout << ans << endl;

  return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.