Mr Loser

题解 CF622C 【Not Equal on a Segment】

2020-07-07 20:14:19


这里说一个简单的思路。

我们可以寻找出限定区间内的最大值和最小值,记为 $a_i,b_i$。

下面分类考虑:

  • $a_i=b_i=x_i$ 输出 -1 即可。这是显然的。
  • 其余情况,输出 $a_i,b_i$ 中任意一个不等于 $x_i$ 的数,直接输出即可。这也是显然的。

于是问题转化成了 RMQ。

$O(n\log n)$ 建立两个 ST 表, $O(1)$ 查询即可。

//This code was made by Bambusoideae
#include<cstdio>
#include<algorithm>
long long a[500001],n,m,l,r,x,lg[500001],st[2][500001][20];
long long b(int t,int l,int r){
    int bit=lg[r-l+1];
    if(t)return a[st[1][l][bit]]<a[st[1][r-(1<<bit)+1][bit]]?st[1][r-(1<<bit)+1][bit]:st[1][l][bit];
    return a[st[0][l][bit]]>a[st[0][r-(1<<bit)+1][bit]]?st[0][r-(1<<bit)+1][bit]:st[0][l][bit];
}
int main(){
    lg[1]=0;
    for(int i=2;i<500001;i++)lg[i]=lg[i>>1]+1;
    scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",a+i),st[0][i][0]=st[1][i][0]=i;
    for(int i=1;i<=lg[n];i++)for(int j=1;j+(1<<i)-1<=n;j++)
    st[0][j][i]=a[st[0][j][i-1]]<a[st[0][j+(1<<(i-1))][i-1]]?st[0][j][i-1]:st[0][j+(1<<(i-1))][i-1],
    st[1][j][i]=a[st[1][j][i-1]]>a[st[1][j+(1<<(i-1))][i-1]]?st[1][j][i-1]:st[1][j+(1<<(i-1))][i-1];
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&l,&r,&x);
        int lar=b(1,l,r),sma=b(0,l,r);
        if(a[lar]==a[sma]&&a[lar]==x)puts("-1");
        else printf("%d\n",a[lar]==x?sma:lar);
    }
}