Submission #40440122

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=1e6+10,mod=998244353,INF=1e8;
void add(ll& x,ll y){x=(x+y)%mod;}
void sub(ll& x,ll y){x=(x-y+mod)%mod;}
void tomax(ll& x,ll y){x=max(x,y);}
void tomin(ll& x,ll y){x=min(x,y);}
//
ll n,a[MAXN];
typedef vector<ll> vec;

struct D{ //离散化
	vec a;
	int tot;
	void add(int x){a.push_back(x);}
	void pr(){
		sort(a.begin(),a.end());
		auto ed=unique(a.begin(),a.end());
		while(a.end() != ed)a.pop_back();
		tot=a.size();
	}
	int qry(int x){return upper_bound(a.begin(),a.end(),x)-a.begin();}
}d[MAXN];
struct BIT{ 
	vec t;int n;
	void reset(int n){t.resize(n+1);fill(t.begin(),t.end(),0);this->n=n;}
	void mdf(int x,int v){for(;x<=n;x+=lowbit(x))add(t[x],v);}
	int qry(int x,ll S=0){for(;x;x-=lowbit(x))add(S,t[x]);return S;}
}t[2][MAXN];

vector<int>mdf[MAXN]; 

namespace Pre{
	int F(int x,int v){return 2*v+x;}
	int F2(int x,int v){return 2*v-x;}

	ll cnt[MAXN],suf[MAXN],key[MAXN];

	struct comp{
		bool operator()(const int x,const int y)const{
			if(key[x] != key[y])return key[x] > key[y];
			else return x > y;
		}
	};
	set<int,comp>S;

	void solve(){
		rep(i,1,n)suf[i]=INF,key[i]=-INF;
		rep(i,1,n)S.insert(i);

		per(i,n,1){
			tomin(suf[a[i]],F(i+1,cnt[a[i]]));
			S.erase(a[i]);
			cnt[a[i]]++;
			key[a[i]] = F(i,cnt[a[i]]) - i - suf[a[i]];
			S.insert(a[i]);
			for(auto u:S){
				if(key[u] <= -i)break;
				mdf[i].push_back(u);
			}
		}
	
		memset(cnt,0,sizeof cnt);
		rep(i,0,n-1){
			for(auto u:mdf[i+1]){
				d[u].add(F2(i,cnt[u]));
			}
			cnt[a[i+1]]++;
		}

	}
};
namespace CFM{
	int F(int x,int v){return 2*v-x;}

	ll dp[MAXN],cnt[MAXN],pre[MAXN],key[MAXN];
	struct comp{
		bool operator()(const int x,const int y)const{
			if(key[x] != key[y])return key[x] > key[y];
			else return x > y;
		}
	};
	set<int,comp>S;

	ll sum[2];
	void ensure(int i){

		for(auto u:mdf[i+1]){
			int pos=d[u].qry(F(i,cnt[u]));

			t[i&1][u].mdf(pos,dp[i]);
		}
		add(sum[i&1],dp[i]);
	}
	void solve(){
		rep(i,1,n)pre[i]=INF,key[i]=-INF;
		rep(i,1,n)S.insert(i);

		dp[0]=1;
		ensure(0);

		rep(i,1,n){
			tomin(pre[a[i]],F(i-1,cnt[a[i]]));
			S.erase(a[i]);
			cnt[a[i]]++;
			key[a[i]] = F(i,cnt[a[i]]) + i - pre[a[i]];
			S.insert(a[i]);

			dp[i] = sum[(i&1)];
			for(auto u:S){
				if(key[u] <= i)break;

				int lim=F(i,cnt[u]); // < lim
				int val=t[(i&1)][u].qry(d[u].qry(lim-1));
				sub(dp[i],val);
			}
			//
			ensure(i);
		}
	}
};

int main(){
	ios::sync_with_stdio(false);
	
	cin>>n;n*=2;
	rep(i,1,n)cin>>a[i];

	Pre::solve();
	rep(i,1,n){
		d[i].pr();
		t[0][i].reset(d[i].tot);
		t[1][i].reset(d[i].tot);
	}

	CFM::solve();

	cout<<CFM::dp[n]<<endl;

    return 0;
}

Submission Info

Judge Result