笔试时间：2023年9月23日 秋招

第一题

题目

小X在一片大陆上探险，有一天他发现了一个洞穴，洞穴里面有n道门，打开每道门都需要对应的钥匙，编号为的钥匙能用于打开第i道门，而且只有在打开了第i道门之后，才能打开第i+1道门，一开始只能打开第1道门。幸运的是，小X在外面探索的途中，每天都能发现一把能打开这n道门中其中一道门的钥匙，每天找完钥匙后他都会去打开所有能打开的门。现在给出他每天找到的钥匙编号，请问每道门分别在哪一天被打开。

输入描述

第一行包合一个正整数n，表示门的数量。

接下来一行包含n个正整数a1，a2，.，an，其中ai表示第i天他找到的钥匙的编号，能够打开第ai道门，数据保证a1-an为1-n的一个排列。

输出描述

输出一行n个数s1，s2，...，sn , 其中si表示第 i 道门在第si天被打开。

样例输入

5

5 3 1 2 4

样例输出

3 4 4 5 5

说明

到第三天时获得的钥匙为1、3、5，能够打开第1道门，到第四天时为1、2、3、5能继续打开第2和3道门，到第五天时获得了全部钥匙，能打开所有剩下的门。

参考题解

双指针模拟，当能开第 i 扇门的时候继续往后开，当天开的门就记录上是哪一天。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    ll n;
    cin >> n;

    vector<ll> arr(n);
    for (ll i = 0; i < n; i++) {
        cin >> arr[i];
    }

    vector<ll> have(n + 1, 0);
    vector<ll> ans(n + 1);

    ll now = 1;
    for (ll i = 0; i < n; i++) {
        have[arr[i]]++;
        while (now <= n && have[now]) {
            ans[now] = i + 1;
            now++;
        }
    }

    cout << ans[1];
    for (ll i = 2; i <= n; i++) {
        cout << ' ' << ans[i];
    }
    cout << '\n';

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long[] arr = new long[(int) n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextLong();
        }

        long[] have = new long[(int) (n + 1)];
        long[] ans = new long[(int) (n + 1)];
        long now = 1;

        for (int i = 0; i < n; i++) {
            have[(int) arr[i]]++;
            while (now <= n && have[(int) now] != 0) {
                ans[(int) now] = i + 1;
                now++;
            }
        }

        System.out.print(ans[1]);
        for (int i = 2; i <= n; i++) {
            System.out.print(" " + ans[i]);
        }
        System.out.println();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
arr = list(map(int, input().split()))
have = [0] * (n + 1)
ans = [0] * (n + 1)
now = 1

for i in range(n):
    have[arr[i]] += 1
    while now <= n and have[now] > 0:
        ans[now] = i + 1
        now += 1

print(ans[1], end='')
for i in range(2, n + 1):
    print(' ' + str(ans[i]), end='')
print()

第二题

题目

有一个长度无限长的自然数序列 A，下标从 0开始。初始时所有数均为0。先进行n次修改，然后进行 m 次查询。每次修改给出三个数l，r，x，将A_l，A_l+1..A_r中的每一个数变成它与x的异或值。每次查询给出一个数字 p表示查询 A_p的值。

输入描述

第一行两个整数n，m，意义如上文所述；

接下来n行3个整数 l，r，x，意义如上文所述；

接下来m行1个整数p，意义如上文所述。

对于所有的数据，1<=n，m<=10^4，l<=r，0<=l, r, p<=10^18，0<=x<=10^9。

输出描述

输出m行每行一个整数，表示答案。

样例输入

2 2

1 5 1

3 7 2

4

6

样例输出

3

2

说明

初始时所有数均为0；

第1次修改A1~A5，x为1，则将A1~A5的值修改为和1的异或值，当前序列的为0、1、1、1、1、1、0、0、......；

第2次修改A3~A7，x为2，则将A3~A7的值修改为和2的异或值，当前序列的为0、1、1、3、3、3、2、2...... 查询A4和A6的值为3和2。

参考题解

起点和x排个序，终点和x排个序，从小到大遍历，然后用三指针，如果起点小于当前查询，那就异或上该操作，如果终点小于当前查询，就再次异或，相当于取消该操作，实际得到的就是当前查询真实的操作，可以借助画线段对比；

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
using namespace std;
using ll = long long;

int main() {
    ll n, m;
    cin >> n >> m;

    vector<array<ll, 3> >