题目背景

译自 ROI 2014 Day1 T3. *Петя и Робот

本题使用的交互库见下文公示。为避免评测出现意外情况，请不要混用多种输入输出。

:::info

#include "testlib.h"
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_QUERIES = 300000;
const int BLOCK_SIZE = 777;
const string SECRET = "Well, contestant made it, just accept it";

class SQRTDecomposition {
private:
    vector<int> array;
    vector<int> block;
    vector<vector<int>> sorted;
    
    int getCountLessForBlock(const vector<int>& a, int value) {
        int l = -1;
        int r = a.size();
        while (l < r - 1) {
            int mid = (l + r) / 2;
            if (a[mid] >= value) r = mid;
            else l = mid;
        }
        return r;
    }
    
public:
    SQRTDecomposition(const vector<int>& a) {
        array = a;
        int n = a.size();
        sorted.resize((n + BLOCK_SIZE - 1) / BLOCK_SIZE);
        block.resize(n);
        
        for (int i = 0, b = 0; i < n; i += BLOCK_SIZE, b++) {
            int to = min(n, i + BLOCK_SIZE);
            for (int k = i; k < to; k++) {
                block[k] = b;
            }
            sorted[b].assign(array.begin() + i, array.begin() + to);
            sort(sorted[b].begin(), sorted[b].end());
        }
    }
    
    void set(int x, int y) {
        int old = array[x];
        array[x] = y;
        vector<int>& curBlock = sorted[block[x]];
        
        bool found = false;
        for (int i = 0; i < curBlock.size(); i++) {
            if (curBlock[i] == old) {
                found = true;
                curBlock[i] = y;
                
                while (i + 1 < curBlock.size() && curBlock[i + 1] < curBlock[i]) {
                    swap(curBlock[i], curBlock[i + 1]);
                    i++;
                }
                while (i - 1 >= 0 && curBlock[i - 1] > curBlock[i]) {
                    swap(curBlock[i], curBlock[i - 1]);
                    i--;
                }
                break;
            }
        }
        
        if (!found) {
            quitf(_fail, "Internal error: element not found in block");
        }
    }
    
    int getCountLess(int l, int r, int value) {
        r--;
        if (l > r) return 0;
        
        int leftBlock = block[l];
        int rightBlock = block[r];
        
        if (leftBlock == rightBlock) {
            int ret = 0;
            while (l <= r) {
                if (array[l] < value) ret++;
                l++;
            }
            return ret;
        }
        
        int ret = 0;
        while (block[l] == leftBlock) {
            if (array[l] < value) ret++;
            l++;
        }
        while (block[r] == rightBlock) {
            if (array[r] < value) ret++;
            r--;
        }
        
        for (int i = leftBlock + 1; i < rightBlock; i++) {
            ret += getCountLessForBlock(sorted[i], value);
        }
        
        return ret;
    }
};

int main(int argc, char* argv[]) {
    registerInteraction(argc, argv);
    
    int group = inf.readInt();
    int n = inf.readInt();
    int shift = inf.readInt();
    
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        p[i] = (inf.readInt() + shift * 239) % n;
    }
    
    vector<int> initialP = p;
    long long countInversions = 0;
    
    vector<int> initArray(n, 0);
    SQRTDecomposition tree(initArray);
    
    for (int i = 0; i < n; i++) {
        countInversions += i - tree.getCountLess(0, i, p[i]);
        tree.set(i, p[i]);
    }
    
    printf("%d %lld\n", n, countInversions);
    fflush(stdout);
    
    int queriesCount = 0;
	bool isExceedMaxquery = false;
    
    while (true) {
        string s = ouf.readToken();
        
        if (s == "answer") {
            vector<int> partyP(n);
            for (int i = 0; i < n; i++) {
                partyP[i] = ouf.readInt() - 1;
            }
            
            for (int i = 0; i < n; i++) {
                if (partyP[i] != initialP[i]) {
                    quitf(_wa, "Incorrect answer, expected %d at position #%d, but found %d (used %d queries)", 
                          initialP[i] + 1, i + 1, partyP[i] + 1, queriesCount);
                }
            }
            if (!isExceedMaxquery)
	            quitf(_ok, "%s (used %d queries)", SECRET.c_str(), queriesCount);
			else
				quitf(_wa, "Correct Answer. (used %d queries, exceeded limit)", queriesCount);
        }
        
        if (s == "swap") {
            queriesCount++;
            if (queriesCount > MAX_QUERIES) {
                isExceedMaxquery = true;
            }
            
            int x = ouf.readInt() - 1;
            int y = ouf.readInt() - 1;
            
            if (x < 0 || x >= n) {
                quitf(_wa, "x = %d, index is out of array bounds", x + 1);
            }
            if (y < 0 || y >= n) {
                quitf(_wa, "y = %d, index is out of array bounds", y + 1);
            }
            if (x == y) {
                quitf(_wa, "swapping element %d with itself", x + 1);
            }
            
            if (x > y) {
                swap(x, y);
            }
            
            int countLess1 = tree.getCountLess(x + 1, y, p[x]);
            int countLess2 = tree.getCountLess(x + 1, y, p[y]);
            countInversions += countLess2 * 2 - countLess1 * 2;
            
            swap(p[x], p[y]);
            tree.set(x, p[x]);
            tree.set(y, p[y]);
            
            if (p[x] < p[y]) {
                countInversions--;
            } else {
                countInversions++;
            }
            
            printf("%lld\n", countInversions);
            fflush(stdout);
        } else {
            quitf(_wa, "Invalid query command: %s", s.c_str());
        }
    }
    
    return 0;
}

:::

题目描述

彼佳（Petya）的书架上摆放着 $n$ 本记录了他所有创意的笔记本。每本笔记本的编号是从 1 到 $n$ 的互不相同的整数。他有一种自己习惯的笔记本摆放顺序（不一定是 1 到 $n$ 的顺序），并且他不喜欢别人移动它们。

为了保存这个顺序并计算其“混乱程度”，彼佳买了一个特别的机器人。机器人可以记住当前笔记本的顺序，并计算其中的“混乱数”。

如果一对笔记本中，编号较小的笔记本出现在编号较大的笔记本的右边，那么这对笔记本就形成一个混乱对。例如，在排列 $(2,~1,~5,~3,~4)$ 中，有三对混乱对：$(2,1)$、$(5,3)$、$(5,4)$，因此混乱数为 $3$。

打扫房间后，彼佳忘记了自己习惯的笔记本顺序，现在想要将其恢复。机器人记住了这个顺序，但它只能告诉彼佳当前顺序中的混乱数。

彼佳还可以让机器人执行如下操作：

• 交换当前排列中的任意两本笔记本的位置。

交换后，机器人会保存新的排列，并告知其混乱数。彼佳可以不断进行这种询问，直到觉得自己获得了足够的信息从而确定原始排列。

你的任务是编写一个程序，通过与机器人交互，恢复原始笔记本的顺序。

交互格式（Interaction）

这是一个交互式问题。你的程序需要通过标准输入/输出，与评测程序（模拟机器人）进行交互。

首先，你的程序应读入两个整数：

• $n$ —— 笔记本的数量；
• $m$ —— 原始排列中的混乱数。

接下来，你的程序与评测程序的交互规则如下：

• 若要交换两本笔记本的位置，请输出：$\tt{swap}$ $i$ $j$

  其中 $i$ 和 $j$ 是笔记本当前排列中的位置编号（$1 \le i, j \le n$, 且 $i \ne j$）。随后需读取一个整数——交换后的排列的混乱数。你的程序最多可以发出 $300 000$ 次这样的交换请求。

• 当你已经确定了原始的排列，应输出：$\tt{answer}$ $p$

  其中 $p$ 是长度为 $n$ 的一个排列，表示最终恢复的顺序（数值为 1 到 $n$，互不重复）。输出后程序应立即结束。

所有输出行都必须以换行符结束，并刷新输出缓冲区，例如使用：

• Pascal：flush(output)
• C/C++：fflush(stdout) 或 cout.flush()

3 2
1
0

swap 1 3
swap 3 2
answer 2 3 1

提示

数据范围

本题共四个子任务。子任务 $1$ 需要全部通过才能得分；子任务 $2\sim 4$ 各自独立计分。

子任务	分值	限制
1	30	$1 \le n \le 100$
2	20	$1 \le n \le 8000$
3	30	$1 \le n \le 60\,000$
4	20	$1 \le n \le 100\,000$