题解 CF622C 【Not Equal on a Segment】
t162
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)$ 查询即可。
```cpp
//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);
}
}
```