题目大意:给定nn个数,mm个操作,每次操作为给出一个数字,从nn个数字中找到这个数字最左边和最右边的位置,将他们之间的数字全部染成操作给定数字,若只有一个则不操作,问最后结果。

题解:观察可以发现,当某个数字被选定过之后,之后进行的操作,要么是跟前面操作区间不相交。要么是包含了前面操作的区间。也就是说对于某一已经操作过的区间。只需要访问一次(因为已经被标记过相同的了,接下来再碰到这个区间的时候可以直接跳) 那我们很显然可以用set来维护每个数的所在下标。

对于每次操作。选出最左边和最右边的所在下标,然后 从左到右开始扫。
那么就会出现两种情况
1、这个数还没有被访问过,那么我们直接将其删去即可。
2、这个数已经被访问过了,那么很显然,所有这个数的下标也必然在这个区间内。那我们将他们全部删去即可。这样保证了每个点必然只会被访问过一次。

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const int INF = 0x3f3f3f3f;
const int N = 3e5 + 5;
set<int> s[N];
int a[N],b[N],n,m;
int vis[N],ans[N];
int main() {
#ifdef INCTRY
    freopen("input.txt", "rt", stdin);
#endif
    
    read(n);
    for(int i = 1; i <= n; i++) {
        read(a[i]); s[a[i]].insert(i);
    }
    read(m);
    //cout << *s[2].begin() << " " << *s[2].rbegin();
    for(int i = 1; i <= m; i++) {
        int x; read(x);
        b[i] = x;
        if(vis[x] || s[x].size() < 2) {
            vis[x] = 1; continue;
        }
        int l = *(s[x].begin()); int r = *(s[x].rbegin());
        for(int j = l + 1; j <= r - 1; j++) {
            s[a[j]].erase(j);
            while(vis[a[j]] && !s[a[j]].empty()) {
                j = *(s[a[j]].begin());
                s[a[j]].erase(j);
            }
        }
        vis[x] = 1;
    }
    mem(vis, 0);
    for(int i = 1; i <= m; i++) {
        int x = b[i];
        if(s[x].size() < 2) continue;
        int l = *(s[x].begin()); int r = *(s[x].rbegin());
        for(int j = l; j <= r; j++) a[j] = x;
    }
    for(int i = 1; i <= n; i++)
        cout << a[i] << " ";
    

#ifdef INCTRY
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}