模拟赛
数据范围：
感觉自己的思路非常自然，所以写一下。
一开始读错题了，没弄懂它的 是啥意思，以为只要元素一样就行了不用管顺序。
如果不管顺序，那答案就是 。
但是我们是需要考虑顺序的。
那么我们考虑什么时候是不合法的。
例如 3773，这种情况下是不能把这两个数都选进去的，因为一定无法满足顺序一样。
如果我们把每个数看成一条线段，那么可以发现，这种不合法的情况就是两条线段是包含关系。
然后考虑合法情况。
例如样例里的 1122，可以发现怎么选都是合法的。
不难发现，这种情况是两条线段无交。
再例如 1212，可以发现只有两种情况是合法的，要么都选左端点要么都选右端点。
不难发现，这种情况是两条线段有交且不包含。
但如果是一堆线段怎么办？
如果连续若干条线段有交，可以发现总贡献依旧为 2。
如果连续若干条线段无交，可以发现总贡献为 。
那么考虑 dp。
设 表示第 条线段的贡献，转移为
初始值为 ，因为每条线段都有两种选择。
复杂度是 的。考虑优化。
不难发现，我们可以用前缀和来转移。
但这样会少算一部分和多算一部分。
我们把 dp 值放到每条线段的右端点上，然后用树状数组直接查询就可以了。
复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include"bits/stdc++.h"
#define re register
#define int long long
#define lb(x) (x&(-x))
using namespace std;
const int maxn=3e5+10,mod=998244353,inf=6e5;
int n,ans;
int f[maxn],s[maxn],tr[maxn<<1];
struct line{
int l,r;
inline bool operator < (const line &a)const{
return l<a.l;
}
}t[maxn];
inline void add(int x,int val){while(x<=inf) tr[x]=(tr[x]+val)%mod,x+=lb(x);}
inline int query(int x){int res=0;while(x) res=(res+tr[x])%mod,x-=lb(x);return res;}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("std.out","w",stdout);
#endif
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(re int i=1,x;i<=2*n;++i){
cin>>x;
if(!t[x].l) t[x].l=i;
else t[x].r=i;
}
sort(t+1,t+n+1);
for(re int i=1;i<=n;++i){
f[i]=2;
f[i]=(f[i]+s[i-1])%mod;
f[i]=(f[i]+query(t[i].l))%mod;
f[i]=((f[i]-(query(inf)-query(t[i].r))%mod)%mod+mod)%mod;
add(t[i].r,f[i]);
s[i]=(s[i-1]+f[i])%mod;
}
for(re int i=1;i<=n;++i) ans=(ans+f[i])%mod;
cout<<ans;
return 0;
}
|