前言
拿到题目首先看数据量,n,q都是2e5的数量级,如果是暴力解的话时间复杂度会达到O(m*n)(最差情况 m次询问,每次l和r为1和n),很明显会超时。
这就意味着我们要在线性的时间内完成查询,即每次询问的查询时间保证在O(1)。
题解
准备一个数组b存储该连续相同数字串的起始点,然后我们从左向右遍历数组,对于第i-th的元素我们判断它与i-1 th的元素是否相等,相等b[i]=b[i-1],不相等b[i]=i。
那么我们只需要比较左右边界的b[i]值判断他们是否属于同一串数字串。
Code
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int a[N],b[N]; int main(){ ios::sync_with_stdio(false); int t; cin>>t; while (t--){ memset(b,0,sizeof(b)); int n,q; cin>>n; for (int i=1;i<=n;i++){ cin>>a[i]; if (a[i]!=a[i-1]) b[i]=i; else b[i]=b[i-1]; } cin>>q; for (int i=1;i<=q;i++){ int l,r; cin>>l>>r; if (b[r]==b[l]) cout<<"-1 -1\n"; else cout<<b[r]-1<<" "<<r<<"\n"; } cout<<endl; } return 0; }
标签:Different,int,cin,2e5,Ones,th,Find From: https://www.cnblogs.com/purple123/p/18012640