CF622C Not Equal on a Segment

题目链接：

http://codeforces.com/problemset/problem/622/C

题目大意：

给定一个长度为n（n不超过200000）的序列，有m（m不超过200000）次询问，第i次询问一个区间[l_i,r_i]内是否存在一个数不等于一个给定值x。如果存在，就输出这个数的位置，否则输出-1。

解题思路：

预处理一个数组p[n]。p[i]表示从位置i向左一直到位置0,第一个不等于a[i]的数的位置。可以以o(n)的复杂度通过对递推实现。具体来说就是首先令p[0]=-1，然后从左向右递推，若a[i - 1] != a[i],则p[i] = i - 1,否则p[i] = p[i - 1]。

查询的时候首先检查a[r]是否等于x。若不等于则找到一个解r；否则检查p[r]即可。

代码：

 #include <iostream>

 #include <cstdio>

 using namespace std;

 int a[];

 int p[];

 int n, t, l, r, x;

 void init()

 {

     p[] = -;

     for (int i = ; i < n; i++)

     {

         if (a[i] != a[i - ])

             p[i] = i - ;

         else

             p[i] = p[i - ];

     }

 }

 int main()

 {

     cin >> n >> t;

     for (int i = ; i < n; i++)

     {

         scanf("%d", &a[i]);

     }

     init();

     while (t--)

     {

         scanf("%d %d %d", &l, &r, &x);

         l--;

         r--;

         if (a[r] != x)

         {

             printf("%d\n", r + );

         }

         else

         {

             if (p[r] != - && p[r] >= l)

             {

                 printf("%d\n", p[r] + );

             }

             else

             {

                 puts("-1");

             }

         }

     }

     return ;

 }

巴特西

CF622C Not Equal on a Segment

最新文章

热门文章