Submission #62275756

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>     // 基本输入输出流
#include <algorithm>    // 通用算法（排序、查找、去重、二分查找等）
#include <vector>       // 动态数组（空间不够会自动扩容）
#include <queue>        // 队列（先进先出）
#include <stack>        // 栈（先进后出）
#include <set>          // 集合（有序不重复）
#include <map>          // 键值对容器（映射）
#include <list>         // 双向链表
#include <math.h>       // 数学函数
#include <functional>   // 通用的函数绑定和调用机制
#define endl '\n'
#define pii pair<int, int>
#define pdd pair<double, double>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define int long long
using namespace std;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>		// 基本输入输出流
#include <algorithm>	// 通用算法（排序、查找、去重、二分查找等）
#include <vector>		// 动态数组（空间不够会自动扩容）
#include <queue>		// 队列（先进先出）
#include <stack>		// 栈（先进后出）
#include <set>			// 集合（有序不重复）
#include <map>			// 键值对容器（映射）
#include <list>			// 双向链表
#include <math.h>		// 数学函数
#include <functional>	// 通用的函数绑定和调用机制

#define endl '\n'
#define pii pair<int, int>
#define pdd pair<double, double>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define int long long
using namespace std;

const int inf = 1e9 + 7;
const int mod = 998244353;
const int N = 2e5 + 10, M = N << 1;
void solve() {
    int n, q;
    cin >> n >> q;

    // 初始化鸽子和巢的状态
    vector<int> p(n + 1);  // p[i] 表示鸽子 i 所在的巢
    vector<int> nst(n + 1, 1); // nst[i] 表示巢 i 中有多少只鸽子
    for (int i = 1; i <= n; i++) {
        p[i] = i;          // 初始时鸽子 i 在巢 i 中
    }

    // 维护有多个鸽子的巢的数量
    int mon = 0;

    while (q--) {
        int t;
        cin >> t;

        if (t == 1) {
            int pp, h;
            cin >> pp >> h;

            int old_nest = p[pp];
            if (--nst[old_nest] == 1) {
                mon--;
            }
            if (++nst[h] == 2) {
                mon++;
            }
            p[pp] = h;
        } else {
            cout << mon << endl;
        }
    }
}

signed main(){
	//重定向输入输出
//    freopen("pow.in", "r", stdin);
//    freopen("pow.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int _ = 1;
//	cin >> _;	// 非多组测试数据请注释该行
    while(_--) solve();
    return 0;
}

Submission Info

Judge Result