collecting_numbers_ii.cpp (1218B)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 using ui = unsigned int; 6 using l = long; 7 using ul = unsigned long; 8 using ll = long long; 9 using ull = unsigned long long; 10 11 using vi = vector<int>; 12 using vui = vector<ui>; 13 using vl = vector<l>; 14 using vul = vector<ul>; 15 using vll = vector<ll>; 16 using vull = vector<ull>; 17 18 void solve() 19 { 20 int n, m; 21 cin >> n >> m; 22 int pos[n]; 23 int val[n]; 24 25 for (int i = 0; i < n; i++) { 26 int tmp; 27 cin >> tmp; 28 pos[tmp-1] = i; 29 val[i] = tmp-1; 30 }; 31 32 long res = 1; 33 for (int i = 0; i < n-1; i++) { 34 res += (pos[i] > pos[i+1]); 35 } 36 37 int a, b; 38 39 set<pair<int, int>> u; 40 for (int i = 0; i < m; i++) { 41 cin >> a >> b; 42 u.clear(); 43 if (val[a-1] > 0) { 44 u.insert({val[a-1]-1, val[a-1]}); 45 } 46 if (val[a-1] < n-1) { 47 u.insert({val[a-1], val[a-1]+1}); 48 } 49 if (val[b-1] > 0) { 50 u.insert({val[b-1]-1, val[b-1]}); 51 } 52 if (val[b-1] < n-1) { 53 u.insert({val[b-1], val[b-1]+1}); 54 } 55 for (auto x : u) { 56 res -= pos[x.first] > pos[x.second]; 57 } 58 59 swap(val[a-1], val[b-1]); 60 pos[val[a-1]] = a-1; 61 pos[val[b-1]] = b-1; 62 63 for (auto x : u) { 64 res += pos[x.first] > pos[x.second]; 65 } 66 67 cout << res << "\n"; 68 } 69 } 70 71 int main() 72 { 73 ios::sync_with_stdio(0); 74 cin.tie(0); 75 solve(); 76 }