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.
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