【Codeforces 1102E】Monotonic Renumeration

题意

【题解】

会发现如果a[i]=a[j]
那么b[i]~b[j]都是相同的,等于b[i]
而b[i]等于b[i-1]+1或者b[i]
有两种可能
所以对于两个相同的a[i]之间的区间。
只要在区间开始的时候乘个2就行。
如果不在任何一起相等的区间里面的话也乘个2就行,因为每个数字都有两种可能。
这道题只要记录下=a[i]的最大下标就好.
这样在遇到一个a[i]的时候,就获取 =a[i]的最大下标j。
显然i~j是这个区间的最大范围。
只要是这个范围的b[i],显然都是相同的。
看代码可能更容易懂。

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 2e5;

const ll MOD = 998244353;

int n;

int a[N+10];

map<int,int> dic;

ll ans = 1;

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n;

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

        cin >> a[i];

        dic[a[i]] = max(dic[a[i]],i);

    }

    int ma = dic[a[1]];

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

        if (i>ma){//不在任何一个a[i]相等的区间(最长)里面

            ans = ans*2%MOD;

        }

        ma = max(ma,dic[a[i]]);

    }

    cout<<ans<<endl;

	return 0;

}

巴特西

【Codeforces 1102E】Monotonic Renumeration

最新文章

热门文章