제출 #1271556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271556		thuhienne	Heavy Light Decomposition (CCO24_day2problem2)	C++20	0 / 25	436 ms	36260 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int n,arr[500009];

int odd[500009],even[500009];
int freq[500009];

void findrange() {
	//odd
	int pt = 1;
	for (int i = 1;i <= n;i++) {
		if (i % 2 == 0) {
			odd[i] = pt;
			continue;
		}
		freq[arr[i]]++;
		while (freq[arr[i]] > 1) {
			if (pt % 2 != 0) freq[arr[pt]]--;
			pt++;
		}
		odd[i] = pt;
	}
	//even
	for (int i = 1;i <= n;i++) freq[i] = 0;
	pt = 1;
	for (int i = 1;i <= n;i++) {
		if (i % 2 != 0) {
			even[i] = pt;
			continue;
		}
		freq[arr[i]]++;
		while (freq[arr[i]] > 1) {
			if (pt % 2 == 0) freq[arr[pt]]--;
			pt++;
		}
		even[i] = pt;
	}
}

int dp[500009],predp[500009];
int sumdp(int l,int r) {
	l--,r--;
	if (l == 0) return predp[r];
	return (predp[r] - predp[l - 1] + mod)%mod;
}


//segment tree
pair <int,int> st[2][500009 * 4];
//.first: co bn segment phu doan l,r
//.second: tong cac dp duoc phu boi it nhat 1 doan trong doan l,r

void changeseg(int id,int l,int r,int u,int v,int val,pair <int,int> st[]) {
	if (l > v || r < u) return;
	if (l >= u && r <= v) {
		st[id].first += val;
		if (st[id].first > 0) st[id].second = sumdp(l,r);
		else if (l == r) st[id].second = 0;
		else st[id].second = (st[id*2].second + st[id*2+1].second)%mod;
		return;
	}
	int mid = (l + r) >> 1;
	changeseg(id*2,l,mid,u,v,val,st);
	changeseg(id*2+1,mid+1,r,u,v,val,st);
	if (st[id].first > 0) st[id].second = sumdp(l,r);
	else st[id].second = (st[id*2].second + st[id*2+1].second)%mod;
}
void updatevalue(int id,int l,int r,int pos) {
	if (l > pos || r < pos) return;
	if (l == r) {
		if (st[0][id].first > 0) st[0][id].second = sumdp(l,r);
		else st[0][id].second = 0;
		if (st[1][id].first > 0) st[1][id].second = sumdp(l,r);
		else st[1][id].second = 0;
		return;
	}
	int mid = (l + r) >> 1;
	
	updatevalue(id*2,l,mid,pos);
	updatevalue(id*2+1,mid+1,r,pos);
	
	if (st[0][id].first > 0) st[0][id].second = sumdp(l,r);
	else st[0][id].second = (st[0][id*2].second + st[0][id*2+1].second)%mod;
	
	if (st[1][id].first > 0) st[1][id].second = sumdp(l,r);
	else st[1][id].second = (st[1][id*2].second + st[1][id*2+1].second)%mod;
}
int get(int id,int l,int r,int u,int v,pair <int,int> st[]) {
	if (l > v || r < u) return 0;
	if (st[id].first > 0) return sumdp(max(l,u),min(r,v));
	if (l >= u && r <= v) return st[id].second;
	int mid = (l + r) >> 1;
	return (get(id*2,l,mid,u,v,st) + get(id*2+1,mid+1,r,u,v,st))%mod;
}


int prevodd[500009],preveven[500009];
int prevodd2[500009],preveven2[500009];

void caldp() {
	dp[0] = 1;
	predp[0] = 1;
	for (int i = 1;i <= n;i++) {
		int l,r;
		//Range 1: a[i] la phan tu light
		l = (i % 2 == 0 ? even[i] : odd[i]),r = i;
		
		//tong cach tao ra dp i la so cach tao ra dp x (x thuoc [l - 1,r - 1])
		//tru di nhung thang nao ma [x + 1,i] co 1 thang khac tinh cl vs i
		//la light
		dp[i] = (dp[i] + sumdp(l,r))%mod;
		dp[i] = (dp[i] - (i % 2 == 0 ? get(1,1,n,l,r,st[1]) : get(1,1,n,l,r,st[0])) + mod)%mod;
		
		//update range prev ai, ai
		if (i % 2 == 0) {
			if (preveven[arr[i]] == 0) {
				changeseg(1,1,n,1,i,1,st[0]);
				preveven[arr[i]] = i;
			}
			else {
				changeseg(1,1,n,preveven2[arr[i]] + 1,preveven[arr[i]],-1,st[0]);
				changeseg(1,1,n,preveven[arr[i]] + 1,i,1,st[0]);
				preveven2[arr[i]] = preveven[arr[i]];
				preveven[arr[i]] = i;
			}
		} else {
			if (prevodd[arr[i]] == 0) {
				changeseg(1,1,n,1,i,1,st[1]);
				prevodd[arr[i]] = i;
			}
			else {
				changeseg(1,1,n,prevodd2[arr[i]] + 1,prevodd[arr[i]],-1,st[1]);
				changeseg(1,1,n,prevodd[arr[i]] + 1,i,1,st[1]);
				prevodd2[arr[i]] = prevodd[arr[i]];
				prevodd[arr[i]] = i;
			}
		}
		//Range 2: a[i] la phan tu heavy -> a[i - 1] la light
		l = (i % 2 == 0 ? odd[i - 1] : even[i - 1]),r = (i % 2 == 0 ? even[i] : odd[i]) - 1;
		if (l <= r) {
			dp[i] = (dp[i] + sumdp(l,r))%mod;
			dp[i] = (dp[i] - (i % 2 == 0 ? get(1,1,n,l,r,st[0]) : get(1,1,n,l,r,st[1])) + mod)%mod;
		}
		predp[i] = (predp[i - 1] + dp[i])%mod;
		updatevalue(1,1,n,i + 1);
	}
	cout << dp[n];
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	//freopen(".inp","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> arr[i];
	findrange();
	caldp();
}

/*
  Nho doi vai em gay
			  co gai ay ngoi duoi goc pho nen tho ...
*/

• Subtask 1: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 5
• Subtask 4: 0 / 6
• Subtask 5: 0 / 7