Codeforces ECR #122 : E. Spanning Tree Queries

Dまではかなりサクサク解いてるんだけどね。
https://codeforces.com/contest/1633/problem/E

問題

N頂点M辺の連結グラフが与えられる。
各辺eにはパラメータW(e)が設定されている。

以下のクエリに順次答えよ。

• クエリとして整数値Xが与えられる。辺eの重みを|W(e)-X|としたときのMSTの重みを答えよ。

解法

解はXに対し折れ線グラフ状になる。
傾きが変化するXは、MSTに残す辺が変化するところなので、2つの辺e1,e2に対し、W(e1)とW(e2)の平均値となる。
よって、各平均値で区切った各区間について、Xが1変化したときの変分をあらかじめ求めておけば、各クエリに高速に応答できる。

int N,M;
int U[303],V[303];
ll W[303];
ll P,K,A,B,C;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

vector<ll> cm,cp;

ll hoge(ll x) {
	UF<55> uf;
	vector<pair<ll,int>> E;
	int i;
	FOR(i,M) E.push_back({abs(W[i]*1000-x),i});
	sort(ALL(E));
	ll ret=0;
	FORR2(c,i,E) {
		if(uf[U[i]]!=uf[V[i]]) {
			ret+=c;
			uf(U[i],V[i]);
		}
	}
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<ll> cand;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>W[i];
		U[i]--;
		V[i]--;
		W[i]*=2;
		cand.push_back(W[i]);
	}
	FOR(x,M) FOR(y,x) cand.push_back((W[x]+W[y])/2);
	
	sort(ALL(cand));
	cand.erase(unique(ALL(cand)),cand.end());
	FORR(c,cand) {
		cm.push_back(hoge(c*1000-1));
		cp.push_back(hoge(c*1000+1));
	}
	cin>>P>>K>>A>>B>>C;
	ll tret=0;
	int R;
	FOR(i,K) {
		ll ret=0;
		if(i<P) {
			cin>>R;
		}
		else {
			R=(1LL*R*A+B)%C;
		}
		R*=2;
		x=lower_bound(ALL(cand),R)-cand.begin();
		if(x==cand.size()) {
			x--;
		}
		else if(x&&cand[x]-R>R-cand[x-1]) {
			x--;
		}
		
		
		
		if(R>=cand[x]) {
			y=cp[x]%1000;
			if(y<500) {
				ret=(cp[x]+500)/1000+(R-cand[x])*y;
			}
			else {
				ret=(cp[x]+500)/1000+(R-cand[x])*(y-1000);
			}
		}
		else {
			y=cm[x]%1000;
			if(y<500) {
				ret=(cm[x]+500)/1000-(cand[x]-R)*(-y);
			}
			else {
				ret=(cm[x]+500)/1000-(cand[x]-R)*(1000-y);
			}
		}
		ret/=2;
		tret^=ret;
		R/=2;
	}
	cout<<tret<<endl;
}

まとめ

後から思えば解法は単純だけど、本番では割と苦戦してるな。