CF1136D Nastya Is Buying Lunch

思路：

1. 最终答案不超过能与Nastya“直接交换”的人数。

2. 对于排在j前面的i，如果i和i～j之间（包括j）的每个人都能“直接交换”，j才能前进一步。

实现：

 #include <bits/stdc++.h>

 using namespace std;

 const int N = ;

 int a[N], p[N], cnt[N];

 vector<int> v[N];

 int main()

 {

     int n, m;

     while (cin >> n >> m)

     {

         for (int i = ; i <= n; i++) v[i].clear();

         memset(cnt, , sizeof cnt);

         int x, y;

         for (int i = ; i <= n; i++) { cin >> a[i]; p[a[i]] = i; }

         for (int i = ; i <= m; i++)

         {

             cin >> x >> y;

             v[y].push_back(x);

         }

         for (int i = n; i >= ; i--)

         {

             for (int j = ; j < v[a[i]].size(); j++)

             {

                 if (p[v[a[i]][j]] < i) cnt[v[a[i]][j]]++;

             }

         }

         vector<pair<int, int>> t;

         for (int i = ; i < v[a[n]].size(); i++)

         {

             int to = v[a[n]][i];

             t.push_back(make_pair(p[to], to));

         }

         sort(t.begin(), t.end());

         int cur = n, ans = ;

         for (int i = t.size() - ; i >= ; i--)

         {

             x = t[i].second;

             if (cnt[x] == cur - t[i].first)

             {

                 ans++; cur--;

                 for (int j = ; j < v[x].size(); j++)

                 {

                     int to = v[x][j]; cnt[to]--;

                 }

             }

         }

         cout << ans << endl;

     }

     return ;

 }