https://codeforces.com/contest/1102/problem/E
C++版本一
题解:二分
先从前往后找到每个数最先出现的位置,然后从后往前找到最后出现的位置
然后从头开始遍历,如果出现没有访问过的区间,就遍历这个区间,然后这个区间里的每个数也是会有个区间的,而且新出现的这个数的区间只可能是往后重叠,即不存在minn比当前区间的minn的小
只能往后重叠,然后正好是for循环,他的下界会一直向后扩,扩不下去了就cnt++,成为一整个区间
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
#define ll long long
#define pb push_back
#define test printf("here!!!")
using namespace std;
const int mx=2e5+10;
const int mod=998244353;
int a[mx];
int b[mx];
int vis[mx];
struct Node
{
int minn;
int maxn;
}num[mx];
int main()
{
ll res=1;
int ans=0;
int n;
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
int cnt=unique(b+1,b+n+1)-b-1;
for (int i=1;i<=n;++i)
{
int p=lower_bound(b+1,b+cnt+1,a[i])-b;
if (num[p].minn==0)
{
num[p].minn=i;
}
}
for (int i=n;i>=1;--i)
{
int p=lower_bound(b+1,b+cnt+1,a[i])-b;
if (num[p].maxn==0)
{
num[p].maxn=i;
}
}
for (int i=1;i<=n;++i)
{
int p=lower_bound(b+1,b+cnt+1,a[i])-b;
if (!vis[p])
{
vis[p]=1;
for (int j=num[p].minn+1;j<num[p].maxn;++j)
{
int k=lower_bound(b+1,b+cnt+1,a[j])-b;
vis[k]=1;
num[p].maxn=max(num[p].maxn,num[k].maxn);
}
ans++;
}
}
for (int i=2;i<=ans;++i)
{
res=res*2%mod;
}
printf("%I64d\n",res);
}
C++版本二
题解:记录每个元素的最大下标。
如果最大下标等于i那么cnt++;
每个元素的最小下标和最大下标之间必须一样所以,取前缀最大值
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int MOD=998244353;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
int a[N];
int b[N];
char str;
map<int,int>p;
ll poww(ll a, ll b) {
ll ans = 1, base = a;
while (b) {
if (b & 1)
ans = ans*base%MOD;
base = base*base%MOD;
b >>= 1;
}
return ans;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%d",&n);
//scanf("%d",&t);
//while(t--){}
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
p[a[i]]=i;
}
int pos=1;
int cnt=0;
for(int i=1;i<=n;i++){
pos=max(pos,p[a[i]]);
if(pos==i)
cnt++;
}
//ans=max(cnt,ans);
cout << poww(2,cnt-1) << endl;
//cout << "Hello world!" << endl;
return 0;
}