CF2147F Exchange Queries

You are at a marketplace and there are two traders who are willing to trade on $ n $ different items. Each trader is represented by a permutation that signifies the relative value of the $ n $ items for that trader. Let's denote those two permutations $ p $ and $ s $ . If you have an item $ i $ , you can trade it for an item $ j $ if either $ p_i > p_j $ (using the first trader) or $ s_i > s_j $ (using the second trader). We say that an item $ i $ is at least as valuable as an item $ j $ if you can come to the marketplace with item $ i $ , make some (possibly none) trades, and get item $ j $ . Note that at any moment, you will have exactly one item on hand. Assume that the traders have infinite supplies of any item. Due to the never-ending updates in the market, traders will often reevaluate their views on the item values. You will be given $ q $ queries; each is a swap in one of the permutations. After every update, you should print the number of pairs $ (i, j) $ ( $ 1 \le i, j \le n $ ) such that item $ i $ is at least as valuable as item $ j $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ q $ ( $ 2 \le n \le 10^5 $ , $ 1 \le q \le 10^5 $ ). The next two lines contain the initial permutations $ p $ and $ s $ . The following $ q $ lines each contain three integers $ tp $ , $ i $ , $ j $ ( $ tp \in \{ 1, 2 \} $ , $ 1 \le i, j \le n $ , $ i \ne j $ ). If $ tp=1 $ , swap $ p_i $ with $ p_j $ . If $ tp=2 $ , swap $ s_i $ with $ s_j $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ , and the sum of $ q $ over all test cases does not exceed $ 10^5 $ .

For each test case, output $ q $ lines, the $ k $ -th of them containing a single integer — the number of pairs $ (i, j) $ such that item $ i $ is at least as valuable as item $ j $ after the first $ k $ updates.

In the first test case, after the first update, both permutations are the identity permutations and thus the only valid pairs are $ (1, 1) $ , $ (2, 1) $ , $ (2, 2) $ , $ (3, 1) $ , $ (3, 2) $ , and $ (3, 3) $ . After the second update, it is possible to get any item starting with any item. For instance, you can get item $ 3 $ from item $ 1 $ using the second trader since $ s_1 = 3 > 1 = s_3 $ . After the third update, it is still possible to get any item starting with any item. For instance, if you start with item $ 2 $ and want to get item $ 1 $ , you can first exchange your item $ 2 $ for item $ 3 $ using the second trader, and then exchange item $ 3 $ for item $ 1 $ using the first trader.