CF2106E Wolf

非常基本的二分思路，很考察对二分的理解。

根据二分法的基本原理可知：搜索每一个位置都有且仅有唯一一条搜索的路径。即，对于每一个位置来说，只要搜索到了这个位置，那么所经过的路径就是一定的。

故而，我们可以确定变换后的路径，“引导”着按照这条路径进行二分。

我们记向左搜索的次数为 $l_0$，向右搜索的次数为 $r_0$，小于 $k$ 的数字有 $m$ 个，大于 $k$ 的数字有 $n$ 个。

所以，当且仅当 $l_0 \le n$ 且 $r_0 \le m$ 时有解，否则无解。

交换时，一个比 $k$ 大的数字一定会与一个比 $k$ 小的数字交换，反之亦然。所以，只需要取交换成大数字的次数与交换成小数字的次数的最大值即可。

注意，答案需要乘 $2$。

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
int n;
int a[MAXN],p[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T,q;
    cin>>T;
    while (T--)
    {
        cin>>n>>q;
        for (int i=1;i<=n;i++)
        {
            cin>>a[i];
            p[a[i]]=i;
        }
        int pos;
        while (q--)
        {
            int l,r,k,ans=0;
            cin>>l>>r>>k;
            pos=p[k];
            if (l>pos||r<pos)
            {
                ans=-1;
                printf("%d ",ans);
                continue;
            }
            int mid=(l+r)>>1;
            int lm=0,rm=0,ls=0,rs=0;
            while (l<=r)
            {
                mid=(l+r)>>1;
                if (a[mid]==k)
                {
                    break;
                }
                if (mid<pos)
                {
                    l=mid+1;
                    if (a[mid]>k)
                    {
                        lm++;
                    }
                    ls++;
                }
                else
                {
                    r=mid-1;
                    if (a[mid]<k)
                    {
                        rm++;
                    }
                    rs++;
                }
            }
            ans=max(lm,rm)*2;
            if (ls>k-1||rs>n-k)
            {
                ans=-1;
            }
            printf("%d ",ans);
        }
        printf("\n");
    }
    return 0;
}