题解：P9599 [JOI Open 2018] 木琴 / Xylophone

· · 题解

比较清新简单的函数式交互，但是题解区一堆乱搞是怎么回事。

本题解尝试展示本题的思维链。

要是我们能求出每个元素比前一个元素大了多少，就可以推出它们的相对大小，但是本题询问只能在询问区间长度为 2 时，返回两个元素差的绝对值。我们先得到所有相邻元素的绝对值，还有 n+1 次操作，我们要考虑在这 n+1 次操作中得到每个二元组符号。

::::info[符号的定义] 定义：当询问 (i,i+1) 中 A_{i+1}-A_i>0 则认为其符号为正，否则认为其符号为负 ::::

观察区间极差的性质，当我们可以构造符号时一个区间极差为 x 时，将构造的符号全部翻转极差仍是 x，因此我们不能直接求出每个二元组的符号。然后，套路地，我们可以尝试判断每个相邻符号是否相同，并枚举第一个符号为正和第一个符号为负两种方案。

问题转化成判断每个 (i,i+1) 和 (i+1,i+2) 的符号是否相同。假设这两个二元组符号相同，即区间 [i,i+2] 单调，那么询问 (i,i+2) 的结果就会等于这两个区间极差之和：

否则，区间 [i,i+2] 不单调，此时区间 [A_i,A_{i+1}] 和 [A_{i+1},A_{i+2}] 一定有一个包含另一个，则询问 (i,i+2) 的答案等于 (i,i+1) 和 (i+1,i+2) 答案的最大值：

由于序列是排列，因此这两个值是不相等的，我们可以直接通过大区间答案进行判断！

::::info[判断的方法] 当且仅当 (i,i+2) 的答案等于 (i,i+1) 和 (i+1,i+2) 答案之和时，(i,i+1) 和 (i+1,i+2) 符号相同。 ::::

接下来，钦定第一个二元组 (1,2) 的符号是正的，判断此时最小值是否在最大值左边。如果在左边，那么这个钦定是对的，钦定最小值的值为 1 进行输出即可。否则，钦定最大值的值为 1、大小翻转后输出。

在询问所有长度为 2 和 3 的区间后，共询问了 2n-3 次，可以通过本题。

下面给出一段较短的代码：

int query(int s, int t);
void answer(int i, int a);
int a[5005],s[5005],p,lst,xyl;
void solve(int n){
    int mini=1,maxi=1;
    s[2]=lst=query(1,2),xyl=1;
    if(s[mini]>s[2])mini=2;
    if(s[maxi]<s[2])maxi=2;
    for(int i=2;i<n;++i){
        p=query(i,i+1);
        if((p+lst)^query(i-1,i+1))xyl=-xyl;
        s[i+1]=s[i]+xyl*p;
        if(s[mini]>s[i+1])mini=i+1;
        if(s[maxi]<s[i+1])maxi=i+1;
        lst=p;
    }
    if(mini<maxi)for(int i=1;i<=n;++i)answer(i,s[i]+1-s[mini]);
    else for(int i=1;i<=n;++i)answer(i,s[maxi]-s[i]+1);
}
/*
巧了，Xylophone 是经典数学中的一个角色，本人特别喜欢 Xylophone，因此很多平台的用户名是 Xylophone，后来随机跳到这题。祭。
*/