Submission #1271566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271566		thuhienne	Heavy Light Decomposition (CCO24_day2problem2)	C++20	25 / 25	600 ms	36928 KiB

Main

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

const int mod = 1e6 + 3;

int n,arr[500009];

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

void findrange() {
	//odd
	int pt = 1;
	for (int i = 1;i <= n;i++) {
		freq[arr[i]]++;
		if (i % 2 != 0) {
			while (freq[arr[i]] > 1) {
				freq[arr[pt]]--;
				if (pt % 2 != 0) dmm[arr[pt]] = 0;
				pt++;
			}
			dmm[arr[i]] = 1;
		} else {
			while (dmm[arr[i]]) {
				freq[arr[pt]]--;
				if (pt % 2 != 0) dmm[arr[pt]] = 0;
				pt++;
			}
		}
		odd[i] = pt;
	}
	//even
	for (int i = 1;i <= n;i++) freq[i] = dmm[i] = 0;
	pt = 1;
	for (int i = 1;i <= n;i++) {
		freq[arr[i]]++;
		if (i % 2 == 0) {
			while (freq[arr[i]] > 1) {
				freq[arr[pt]]--;
				if (pt % 2 == 0) dmm[arr[pt]] = 0;
				pt++;
			}
			dmm[arr[i]] = 1;
		} else {
			while (dmm[arr[i]]) {
				freq[arr[pt]]--;
				if (pt % 2 == 0) dmm[arr[pt]] = 0;
				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
		if (i > 1 && arr[i] != arr[i - 1]) {
			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[i] << " ";
	}
	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: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 6 / 6
• Subtask 5: 7 / 7