Berstagram

Created by LXC on Tue Mar 5 17:11:46 2024

https://codeforces.com/problemset/problem/1250/A

ranting: 1400

tag: implementation

problem

给定两个序列 $a=[a_1,a_2,\dots,a_m]$ 和 $b=[b_1,b_2,\dots,b_n]$，其中 $b_i$ 的初始值为 $i$，$a_i$ 的初始值将由键盘读入。对于每个 $a_i$，若 $b_j=a_i$，则将 $b_j$ 与 $b_{j-1}$ 的值调换（若 $j=1$，则序列不变）。

第一行两个整数 $n$ 和 $m$，意义如上所述。

第二行包含 $m$ 个整数 $a_i$（$1\le i\le m$），表示序列 $a$。

输出共 $n$ 行，每行包含两个整数。第 $i$ 行的两个数分别表示数字 $i$ 在序列 $b$ 中出现过的所有位置中最靠前的一个与最靠后的一个。

序列 $b$ 经过每一次操作后的变化：

初始：$[1,2,3]$；
第一次操作后：$[1,3,2]$；
第二次操作后：$[1,2,3]$；
第三次操作后：$[1,2,3]$；
第四次操作后：$[1,3,2]$；
第五次操作后：$[3,1,2]$。

当中，$1$ 出现过的位置有 $1$ 和 $2$，最靠前的是 $1$，最靠后的是 $2$；$2$出现过的位置有 $2$ 和 $3$，最靠前的是 $2$，最靠后的是 $3$；$3$出现过的位置有 $1$，$2$ 和 $3$，最靠前的是 $1$，最靠后的是 $3$。

solution

哈希记录每个数的位置，然后模拟，维护每个数位置的最大值和最小值就行。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), mp(n), mx(n), mn(n);
    iota(a.begin(), a.end(), 0);
    iota(mp.begin(), mp.end(), 0);
    iota(mx.begin(), mx.end(), 0);
    iota(mn.begin(), mn.end(), 0);
    for (int i=0; i<m; i++) {
        int x;
        cin >> x;
        x--;
        if (mp[x] != 0) {
            int p1 = mp[x]-1, p2 = mp[x];
            int v1 = a[mp[x]-1], v2 = a[mp[x]];
            swap(a[p1], a[p2]);
            mp[v2] = p1;
            mp[v1] = p2;
            mn[v2] = min(mn[v2], mp[v2]);
            mx[v1] = max(mx[v1], mp[v1]);
        }
    }
    for (int i=0; i<n; i++) {
        cout << mn[i]+1 << " " << mx[i]+1 << "\n";
    }

}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}