Codeforces #757 Div2 : E. Divan and a Cottage

不参加だった回。
https://codeforces.com/contest/1614/problem/E

問題

室温がPのとき、ある日外気温がTなら、PはTに1度だけ近づいた値になる。
以下のクエリに順次答えよ。

N日間の外気温が与えられる。
初日の室温がXの時、N日後の室温は何度になるか。

解法

元の室温が1度差があるとき、最終的な温度は0度または1度異なる。
そこで、温度差が0になる元の室温の位置をTrieで管理しよう。
f(x) := 元の室温がx以下の時、温度差が0になる元の室温の位置の数

とすると、初日室温がPの時、N日後の室温はP+N-f(x)となる。
これで各クエリには容易に答えられる。

また、1日経つごとに、温度差が0になる箇所が2か所生じるが、これは以下の2か所である。
こちらはPを二分探索で求めて行けばよい。

• P+N-f(x)=Tとなる最小の室温Pと室温(P-1)の間
• P+N-f(x)=T+1となる最小の室温Pと室温(P-1)の間

int N;
int T,K,X;

struct BinarySumTrie {
	BinarySumTrie *nex[2];
	ll v;
	BinarySumTrie() {
		nex[0]=nex[1]=NULL;v=0;
	}
	void add(ll s,ll val,int pos=31) {
		v += val;
		if(pos>=0) {
			int c=(s>>pos)&1;
			if(!nex[c]) nex[c]=new BinarySumTrie();
			nex[c]->add(s,val,pos-1);
		}
	}
	ll get(ll s,int pos=31) { // sum [0,s-1]
		if(pos<0) return 0;
		int c=(s>>pos)&1;
		if(c) return (nex[0]?nex[0]->v:0)+(nex[1]?nex[1]->get(s,pos-1):0);
		else return (nex[0]?nex[0]->get(s,pos-1):0);
	}
};
BinarySumTrie bst;
int add;

ll mapto(ll start) {
	return start+add-bst.get(start+1);
}

ll getcur(ll base) {
	//遷移後baseになる最小値
	ll cur=-1;
	int i;
	for(i=30;i>=0;i--) {
		if(mapto(cur+(1<<i))<base) cur+=1<<i;
	}
	return cur+1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int ret=0;
	FOR(i,N) {
		cin>>T>>K;
		T+=1000000;
		ll a=getcur(T);
		ll b=getcur(T+1);
		add++;
		bst.add(a,1);
		bst.add(b,1);
		
		while(K--) {
			cin>>X;
			X=(X+ret)%(1000000001);
			X+=1000000;
			ret=mapto(X)-(1000000);
			cout<<ret<<endl;
			
		}
	}
	
}

まとめ

2750ptのE問題にしては簡単かも。