题目链接:Codeforces Round #546 (Div. 2) D. Nastya Is Buying Lunch

题意

给出一个长度为n的置换,再给出m组 代表如果ui在vi前面并且相邻时,两者可以交换。问置换中最后一个元素 P[n] 可以最多向前移动几格。

数据范围:


思路

先进行化简,我们的目标等价于找到从n-1开始连续最长的能够被P[n]度过的子串

正向思考超级复杂,
逆向思考就非常简单了

正向思路:维护一个dp[n],复杂度

逆向思路:从后往前扫,如果当前点可以放到那个连续的子串中,就将子串的长度加一,否则找到所有能够到达当前点的u,将他的C数组加一,

C[i]数组所代表的含义是在这i点以后,i点能够穿过多少非P[n]点。
如果当前点能够穿过所有的非连续序列的点,就将这个点++
复杂度 O(n+m),完美


代码

#include <bits/stdc++.h>
using namespace std;
int N,M,P[1000006],C[1000006],x,y,r;
vector<int> g[1000006];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>N>>M;
    for(int i=0;i<N;i++)
        cin>>P[i];
    for(int i=0;i<M;i++){
        cin>>x>>y;
        g[y].push_back(x);
    }
    for(int i=N-1;i>=0;i--)
        if(C[P[i]]==N-1-i-r && i!=N-1)r++;
        else for(int f:g[P[i]])C[f]++;
    cout<<r;
}