P8671 [蓝桥杯 2018 国 AC] 约瑟夫环 题解

约瑟夫环有 \(\mathcal O(n)\) 做法相信大家都知道。这里就不在介绍了，这里给出一个不知道这个结论的 \(\mathcal O(n\log n)\) 简单做法。
考虑直接模拟题意，每次循环往后数 \(k\) 个然后把这个数给删掉，如果采用链表的话找 \(k\) 个是要超时的，考虑换个数据结构比如平衡树，支持 \(\mathcal O(\log n)\) 求排名，插入或删除。于是就打了个平衡树上去。

#include<ext/pb_ds/assoc_container.hpp>
namespace pbds=__gnu_pbds;
pbds::tree<int,pbds::null_type,std::less<>,pbds::rb_tree_tag,pbds::tree_order_statistics_node_update>s;
int n,k;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>k;
	for(int i=1;i<=n;i++)s.insert(i);
	for(int i=1;--n;){
		i=(i+k-2)%(n+1)+1;
		s.erase(s.find_by_order(i-1));
	}
	cout<<*s.begin();
	return 0;
}

发现 pbds 的平衡树跑不过去，难道是太慢超时了？这该怎么办呢？众所周知基础平衡树的所有题都可以离线下来用树状数组去解决，那这里 find_by_order 这个操作就要用到树状数组上二分这个做法去实现。
代码：

constexpr int N=2e6+1;
int n,k;
struct{
	int d[N];
	void add(int x){for(;x<N;x+=x&-x)d[x]++;}
	void del(int x){for(;x<N;x+=x&-x)d[x]--;}
	int kth(int x){
		int p=1<<std::__lg(N);
		for(int i=std::__lg(N)-1;~i;i--)
			if(d[p-(1<<i)]>=x)p-=(1<<i);
			else x-=d[p-(1<<i)];
		return p;
	}
}s;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>k;
	for(int i=1;i<=n;i++)s.add(i);
	for(int i=1;--n;){
		i=(i+k-2)%(n+1)+1;
		s.del(s.kth(i));
	}
	cout<<s.kth(1);
	return 0;
}

这里简单介绍一下树状数组上二分这个算法：先把当前位置调整成整个数组总和的位置（也就是 1..0000，这样才能保证 \([1,n]\) 都被 \(p\) 包含，为了方便，空间开两倍），从高位向低位考虑，如果左儿子比 \(k\) 大表示答案一定在左儿子，进入左儿子就行了，否则就在右儿子里面，把排名 \(k\) 减去左儿子的总和就行了。
CF1354D 这题也是采取树状数组去代替平衡树，也要用到树状数组上二分这个办法，可以去做一做。