CodeForces 622C Not Equal on a Segment

预处理p[i],p[i]表示:【p[i],i】这段闭区间上所有数字都是a[i]

询问的时候,如果xi==a[ri]并且p[ri]<=li,一定无解

剩下的情况都是有解的,如果xi!=a[ri],那么输出ri,否则输出p[ri]-1。

另外,看到有大牛博客说可以用线段树,大致是这样的:

线段树保存区间最大值与最小值,

如果询问的区间上最小值==最大值,那么无解;

剩下的情况都是有解;如果xi不等于最小值,那么输出最小值位置;如果xi不等于最大值,那么输出最大值位置。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
#include <vector>
using namespace std; const int maxn=+;
int a[maxn],p[maxn];
int n,m; int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
p[]=;
for(int i=;i<=n;i++)
{
if(a[i]==a[i-]) p[i]=p[i-];
else p[i]=i;
} //p[i]表示,【p[i],i】这段闭区间上所有数字都是a[i] for(int i=;i<=m;i++)
{
int li,ri,xi;
scanf("%d%d%d",&li,&ri,&xi);
if(xi==a[ri]&&p[ri]<=li) printf("-1\n");
else
{
if(xi!=a[ri]) printf("%d\n",ri);
else printf("%d\n",p[ri]-);
}
} return ;
}
上一篇:C# 3种方法连接MySql


下一篇:使用Python的列表推导式计算笛卡儿积