E. Monotonic Renumeration

本文主要是介绍E. Monotonic Renumeration，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接 : 

Problem - E - Codeforces

思路 : 

区间合并 + 快速幂

对于a[0],那么从第一个a[0],到最后一个a[0]这个区间内所有b值全部为b[0] = 0,以此类推，对于其他值也是一样；

例如对于[1 , 2 , 1 , 2 , 3]

首先b[0] = 0(题目要求) ， 然后因为a[2] = a[0] ,那么b[2]=b[0] = 0;

要求bi+1=bi 或 b[i+1]=b[i]+1 , 那么b[1]夹在两个0之间，只能为0 ， 同理b[3] = b[1] = 0 ;

对于b[4] = b[3] = 0 , 或b[4] = b[3] + 1 ;

依此 : 我们要求一个区间数量，每两个区间要满足无相同值，这里先求出每个值出现的范围，然后左端点排序，然后进行合并 ， 得到区间数量t;

然后ans 等于2的(t-1)次方(由于b[0]已经固定为1,后面一个区间可以取上一个区间+0/+1的值)

代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define int long long 
typedef long long LL;
const LL mod = 998244353;
const int N = 2e5+10;
typedef pair<int, int> PII;LL qmi(LL m, LL k,LL p){LL res = 1 % p, t = m;while (k){if (k&1) res = res * t % p;t = t * t % p;k >>= 1;}return res%p;}void merge(vector<PII> &segs){vector<PII> res;sort(segs.begin(), segs.end());int st = -2e9, ed = -2e9;for (auto seg : segs)if (ed < seg.first){if (st != -2e9) res.push_back({st, ed});st = seg.first, ed = seg.second;}else ed = max(ed, seg.second);if (st != -2e9) res.push_back({st, ed});segs = res;
}inline void solve(){// 详细地址 : https://codeforces.com/contest/1102/submission/259938745 int n ; cin >> n ; vector<int> a(n+1) ; vector<PII> b; set<int> st ; map<int,vector<int>> mp ;for(int i=1;i<=n;i++) cin >> a[i] ,mp[a[i]].push_back(i) ;for(int i=1;i<=n;i++){if(st.count(a[i])) continue ;b.push_back({i,mp[a[i]].back()}) ;st.insert(a[i]) ;}merge(b) ;//区间合并 int t = b.size() - 1 ;LL ans = qmi(2,t,mod) ;//快速幂 cout << ans << endl ;
}signed main(){IOSint _ = 1;while(_ --) solve();return 0;
}

这篇关于E. Monotonic Renumeration的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---