Codeforces #576 Div1 B. Welfare State

これも問題文ややこしいなぁ。
https://codeforces.com/contest/1198/problem/B

問題

N人の市民がおり、それぞれ金銭をA[i]ずつ持っている。
以下の全クエリを実行後、各人の所持金を答えよ。

• i番の所持金をxにする
• x未満の所持金の人を、一律xだけ持たせる。

解法

priority_queueで所持金の少ない順リストを作り、後者のクエリがあった場合は以降それ以下の金額の人はUnion-Findとまとめて考えるようにする。
前者のクエリで所持金が増え、後者の一律所持金増組から外れる場合があるが、Union-Findで分離はできないため、i番目として新たな人が入ってきた、と考えるとよい。

int N,Q;
int ID[505050];
int A[505050];
int T,P,X;

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;
priority_queue<pair<int,int>> C;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	int ON=N;
	FOR(i,N) {
		scanf("%d",&A[i]);
		ID[i]=i;
		C.push({-A[i],i});
	}
	scanf("%d",&Q);
	FOR(i,Q) {
		scanf("%d",&T);
		if(T==1) {
			scanf("%d%d",&P,&X);
			ID[P-1]=N;
			A[N]=X;
			C.push({-A[N],N});
			N++;
		}
		else {
			scanf("%d",&X);
			while(C.size() && -C.top().first<X) {
				x=C.top().second;
				C.pop();
				uf(x,N);
			}
			A[uf[N]]=X;
			C.push({-A[uf[N]],uf[N]});
			N++;
		}
	}
	
	FOR(i,ON) _P("%d ",A[uf[ID[i]]]);
	
	
}

まとめ

問題の内容はともかく、問題文はなんかすんなり頭に入らないんだよな。