CodeTON Round 4 : F. M-tree

割と面倒だった問題。
https://codeforces.com/contest/1810/problem/F

問題

N要素の整数列Aが与えられる。
N個の葉を持つM分木を考える。
各葉に、AのPermutationとなるよう設定したとき、この木の価値は、各葉における(深さ+設定値)の最小値となる。
Aを1要素更新するクエリが与えられるので、価値をその都度求めよ。

解法

木をM進数として考える。
深さdである葉に値vを格納すると、M^(d+v)が計上されるとして考える。
M^(d+A[v])の総和がM進数で何桁かを考えればそれが解となる。
あとはM進数の値を頑張って加減算しよう。

int T;
ll N,M,Q,D;
ll A[202020];

set<pair<int,int>> C;

void add(int d) {
	auto it=C.lower_bound({d+1,0});
	auto nex=*it;
	auto cur=*--it;
	if(d==cur.first) C.erase(cur);
	if(cur.second==M-1) {
		C.insert({d,0});
		add(nex.first);
	}
	else {
		if(d+1!=nex.first) {
			C.insert({d,cur.second+1});
			C.insert({d+1,cur.second});
		}
		else if(cur.second+1==nex.second) {
			C.erase(nex);
			C.insert({d,cur.second+1});
		}
		else {
			C.insert({d,cur.second+1});
		}
	}
	it=C.lower_bound({d,0});
	if(it->second==prev(it)->second) C.erase(it);
	it=C.lower_bound({d+1,0});
	if(it->second==prev(it)->second) C.erase(it);
}
void sub(int d) {
	auto it=C.lower_bound({d+1,0});
	auto nex=*it;
	auto cur=*--it;
	if(d==cur.first) C.erase(cur);
	if(cur.second==0) {
		C.insert({d,M-1});
		sub(nex.first);
	}
	else {
		if(d+1!=nex.first) {
			C.insert({d,cur.second-1});
			C.insert({d+1,cur.second});
		}
		else if(cur.second-1==nex.second) {
			C.erase(nex);
			C.insert({d,cur.second-1});
		}
		else {
			C.insert({d,cur.second-1});
		}
	}
	it=C.lower_bound({d,0});
	if(it->second==prev(it)->second) C.erase(it);
	it=C.lower_bound({d+1,0});
	if(it->second==prev(it)->second) C.erase(it);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>Q;
		C.clear();
		C={{-1<<20,0},{1<<20,1}};
		
		
		FOR(i,N) {
			cin>>A[i];
			add(A[i]);
		}
		while(Q--) {
			cin>>x>>y;
			x--;
			sub(A[x]);
			A[x]=y;
			add(A[x]);
			
			int ret;
			if(C.size()==4) {
				auto it=C.begin();
				it++;
				auto p=*it;
				auto q=*++it;
				if(q.first-1==p.first&&p.second==1) ret=p.first;
				else ret=q.first;
			}
			else {
				auto it=--C.end();
				it--;
				ret=it->first;
			}
			cout<<ret<<" ";
			
		}
		cout<<endl;
	}
}

まとめ

昔AGCでこんな感じの考え方する問題あったな。