題目鏈接：點(diǎn)擊查看

題目大意：先給出一個長度為n的數(shù)列，然后給出m次詢問，每次詢問的格式是l,r,x，其中[l,r]代表的是數(shù)列的下標(biāo)范圍，要求我們輸出任意一個在區(qū)間[l,r]內(nèi)值不等于x的下標(biāo)

題目分析：我看網(wǎng)上好多人用線段樹維護(hù)區(qū)間最大值和最小值來做的這個題目，我感覺真的有點(diǎn)小題大做了。。這個題目第一眼看上去是有點(diǎn)不知道該怎么辦的，因為我是補(bǔ)題的時候看到的這個題目，能看到題目標(biāo)簽，是數(shù)據(jù)結(jié)構(gòu)，于是我就想，用set，map能不能亂搞一下，發(fā)現(xiàn)沒什么進(jìn)展，想了想并查集呢？好像有那么點(diǎn)意思，然后就想到了用并查集的思想，做一個連接，開一個pre數(shù)組，pre[i]代表的是在下標(biāo)i之前離i最近的一個，不等于a[i]的下標(biāo)，也不能說是并查集吧，有點(diǎn)動態(tài)規(guī)劃的思想，這樣O(n)預(yù)處理出來一個pre數(shù)組之后，就可以O(shè)(1)查詢了，對于輸入的l和r：首先判斷一下a[r]是否等于x，若不等于直接輸出r即可，若等于的話，判斷一下pre[r]是否小于l，若小于l的話，就是無解了，直接輸出-1，否則就直接輸出pre[r]

然后實(shí)現(xiàn)就好了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;int a[N],pre[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",a+i);for(int i=1;i<=n;i++)if(a[i]!=a[i-1])pre[i]=i-1;elsepre[i]=pre[i-1];while(m--){int l,r,x;scanf("%d%d%d",&l,&r,&x);if(a[r]!=x)printf("%d\n",r);else if(pre[r]<l)printf("%d\n",-1);elseprintf("%d\n",pre[r]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 622C Not Equal on a Segment(思维+水题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。