CF1712C的题解
对于 \(n=1\)，答案显然为 \(0\)。
我们能很清楚一点，因为 \(a_i>0\)，所以当 \(a_x\) 需要改为 \(0\) 时， \(a_1\sim a_{x-1}\) 也都必须改 \(0\)，这样才能使前面的满足 \(a_{i-1}\le a_i\)
那我们首先得先记录每一个数出现的最后一个位置 last[a[i]]，以及最后一个不满足 \(a_{i-1}\le a_i\) 的位置 find。
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
last[a[i]]=i;
if(a[i-1]>a[i]) find=i;
}
if(n==1)
{
printf("0\n");
continue;
}
然后我们用 \(l\) 和 \(r\) 两个指针用类似于双指针的方法来找最后一个需要被改为 \(0\) 的数。
一开始，令 l=1,r=find-1
然后遍历该区间的数，如果其中有一个数最后出现的位置超过了该区间的右端点，那么我们枚举范围就要往后调。
l=1,r=find-1,tmp=0,flag=0;
while(!flag)
{
flag=1;
for(int i=l;i<=r;i++)
{
tmp=max(tmp,last[a[i]]);//找到最右边的数
if(tmp>r) flag=0;//如果超过右端点，则打上标记
}
if(!flag) l=r+1,r=tmp;//如果超过，则更新左右端点，准备下一次枚举
}
最后只需要扫一遍 \(1\sim r\)，找到其中有多少种不一样的数即可。
for(int i=1;i<=r;i++)
if(!b[a[i]])
{
tot++;
b[a[i]]++;
}
\(\text{code}\)
#include<cstdio>
#include<cstring>
int t;
int n;
int a[100010];
int b[100010];
int last[100010];
bool flag;
int tot;
int find;
int tmp;
int l,r;
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(b,0,sizeof(b));
tot=find=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
last[a[i]]=i;
if(a[i-1]>a[i]) find=i;
}
if(n==1)
{
printf("0\n");
continue;
}
l=1,r=find-1,tmp=0,flag=0;
while(!flag)
{
flag=1;
for(int i=l;i<=r;i++)
{
tmp=max(tmp,last[a[i]]);
if(tmp>r) flag=0;
}
if(!flag) l=r,r=tmp;
}
for(int i=1;i<=r;i++)
if(!b[a[i]])
{
tot++;
b[a[i]]++;
}
printf("%d\n",tot);
}
return 0;
}
时间复杂度？
输入的时间复杂度显然为 \(O(n)\)。
\(l\) 和 \(r\) 是以上一个区间的结果来进行移动的，每次枚举的区间都不会重叠，所以 \(i\) 最坏情况下枚举的范围是 \(1\sim n\)，时间复杂度也为 \(O(n)\)。
\(r\) 最坏情况下为 \(n\)，时间复杂度显然也为 \(O(n)\)。
综上，单次询问时间复杂度为 \(O(n)\)，可以通过此题。