当输入操作2时,将i改变为j的操作
只对当前操作之前的数起作用
所以我们可以选择反向遍历一遍原来的数组
新开一个数组p表示当前某个值的更改后的值
如原先p[5] = 5, 但是在操作2 5 3之后, p[5] = 3
#include <iostream>
#include <cstring>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;template<typename T>inline void rd(T &a) {char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};const int N = 5e5+10;
int n;
int type[N], x[N], y[N], p[N];void solve()
{cin >> n;for(int i = 1; i <= n; i ++){cin >> type[i];if(type[i]==1) rd(x[i]);else rd(x[i]), rd(y[i]);}// 预处理p[]for(int i =1; i <= N; i ++) p[i] = i;// 处理答案vector<int> ans;for(int i = n; i >= 1; i --){// type == 1,直接将答案填进ans,但是注意填的是p[x]对应的那个可能被更改过的x'的值if(type[i] == 1) ans.push_back(p[x[i]]);// type == 2,这时将p[x]对应的值x值改为x'// 这里注意 等号右边是p[y[i]],需要用后面2操作更新后的y的值else p[x[i]] = p[y[i]];}// 反向输出结果reverse(ans.begin(), ans.end());for(int i : ans) cout << i << " ";
}int main()
{solve();
}
更多推荐
发布评论