拉平的分治算法

常规分治

通常，我们的分治是递归地写的，这样好写，比如常见的 cdq 分治写法：

void solveFunc(int l,int r) {
	//解决跨区间问题
}

void divideFunc(int l,int r) {
	if(l==r) return ;		//递归边界
	int mid=(l+r)/2;
	divideFunc(l,mid); 		//处理左半问题
	divideFunc(mid+1,r);	//处理右半问题
	solveFunc(l,r);			//处理跨区间问题
} 

不同的分治在 divideFunc 内的顺序不完全相同，而 solveFunc 则是完全针对题目设计的。

可以知道，若解决的问题长度是 $O(n)$ 的，则 divideFunc 的递归深度是 $O(\log n)$ 的，第 $i$ 层的段长度为 $2^i$。通过这个，就可以计算出整个问题的总复杂度。

比如，若 solveFunc 的复杂度是 $O(n)$ 的，那么整体是 $O(n\log n)$ 的；如果是 $O(n\log n)$ 的，那么整体是 $O(n\log^2 n)$ 的。

拉平分治

通常以上写法已经足够用了。但是假设维护的数据结构有特殊性，这样递归写，复杂度就爆了。

递归查询点的顺序不是有序的，比如序列：$[1,2,3,4,5,6,7,8]$，查询顺序可能是：$[1,8],[1,4],[1,2],[1,1],[2,2],[3,4],[3,3],[4,4]\dots$，

一种解决方法是回滚，就是同时维护加入和删除，以达到想要的区间。这样做，我们得先把 $[1,8]$ 加入，再删除 $[5,8],[3,4],[2,2],[1,1]$，再加入 $[2,2]$，又删掉，等等。这样做，比较复杂。假如删除操作复杂度很大或者不能支持删除，这种方法束手无策，

假如数据结构支持的查询是和前缀有关的（比如前缀前 $k$ 小的和），考虑一种暴力的方法，让我们只用维护加入操作。普通的分治类似于 dfs，我们来做一个 bfs 版的。

struct datatype{};

struct bfs_element {
	int l,r;
	datatype data;
}; 

datatype solveFunc(int l,int r) {}

void bfsDivideFunc(int n) {
	std::queue<bfs_element> Q;
	Q.push({1,n,data});
	while(!Q.empty()) {
		bfs_element now=Q.front(); Q.pop();
		datatype newdata=solveFunc(now.l,now.r);
		if(now.l==now.r) continue;
		int mid=(l+r)>>1;
		Q.push({1,mid,newdata});
		Q.push({mid+1,r,newdata});
	}
}

刚才的遍历顺序变为：$[1,8],[1,4],[5,8],[1,2],[3,4],[5,6],[7,8]\dots$。可以发现，我们的分治变为了 $O(\log n)$ 次的遍历，而对答案没有影响。

那么，我们的数据结构就只需要加入这一个操作。加入遍历完一遍，就直接把数据结构清空或销毁。重新开始即可。复杂度可靠。

例题

给定两个长度为 $n$ 的序列 $A,S$。定义 $f(x,y)$ 为$A_1$ 到 $A_x$ 中前 $y$ 小的数的和。对于每个 $1\leq i\leq n$，求 $\min\limits_{1\leq j\leq i}{\big\{f(j,i)+S_j\big\}}$。

首先发现一个性质，就是若 $i$ 是从 $p_i$ 转移的（也就是对于 $i$ ，$f(p_i,i)+S_{p_i}$ 是它最小的答案），那么 $p$ 单调不减。因此可以分治做，先求出 $p_{mid}$ ，那么分成 $(l,mid,p_l,p_{mid})$ 和 $(mid+1,r,p_{mid},p_r)$ 求解。

有人说，可以用主席树做。没问题。但是这个题也可以用权值线段树做。先将权值线段树离散化（或者动态开点）。然后利用刚才提到的“拉平的 bfs”求解。实现如下：

#define int	long long
#define R	myio::read_int()

const int kS=1e5+5,kRANGE=1000;

struct node {
	int sum,cnt;
	node() {sum=cnt=0;}
	node(int _sum,int _cnt) 
		:sum(_sum),cnt(_cnt) {}
	void clear() {sum=cnt=0;}
};

int n,s[kS],a[kS],ans[kS];

class SegmentTree {
	private:
		node* nodes;
		int range;
		int end;
		void PUSH_UP(int p) {
			nodes[p].sum=nodes[p<<1].sum+nodes[p<<1|1].sum;
			nodes[p].cnt=nodes[p<<1].cnt+nodes[p<<1|1].cnt;
		}
		void INSERT(int X,int l,int r,int p) {
			if(l>=r) {nodes[p].sum+=l,nodes[p].cnt++; return ;}
			int mid=(l+r)>>1;
			if(mid>=X) INSERT(X,l,mid,p<<1);
			else INSERT(X,mid+1,r,p<<1|1);
			PUSH_UP(p);
		}
		int QUERY(int C,int l,int r,int p) {
			if(l==r) return l*C;
			int mid=(l+r)>>1;
			if(C>nodes[p<<1].cnt) return nodes[p<<1].sum
				+QUERY(C-nodes[p<<1].cnt,mid+1,r,p<<1|1);
			return QUERY(C,l,mid,p<<1);
		}
		void CLEAR() {for(int i=0;i<=range*4;i++) nodes[i].clear(); end=0;}
	public:
		SegmentTree(int _range) {
			range=_range; end=0;
			nodes=new node[range*4+1];
		}
		void insert(int x) {
			if(x<end) CLEAR(); 
			for(int i=end+1;i<=x;i++) INSERT(a[i],1,range,1);
			end=x;
		}
		int query(int x) {return QUERY(x,1,range,1);}
		~SegmentTree() {delete []nodes;}
};

struct ques {
	int l,r,pl,pr;
	ques(int _l,int _r,int _pl,int _pr)
		:l(_l),r(_r),pl(_pl),pr(_pr) {}
};

std::queue<ques> Q; 

void tMin(int &x,int y,int &fx,int fy) {if(x>y) x=y,fx=fy;}

signed main() {
	n=R; SegmentTree *segtree=new SegmentTree(kRANGE);
	for(int i=1;i<=n;i++) s[i]=R;
	for(int i=1;i<=n;i++) a[i]=R;
	Q.push(ques(1,n,1,n));
	int nl,nr,npl,npr,mid,res,resp;
	for(int i=1;i<=n;i++) {
		ques now=Q.front(); Q.pop();
		nl=now.l,nr=now.r,npl=now.pl,npr=now.pr;
		mid=(nl+nr)>>1,res=9e18,resp=0;
		for(int j=std::max(npl,mid);j<=npr;j++) 
			segtree->insert(j),tMin(res,segtree->query(mid)+s[j],resp,j);
		ans[mid]=res;
		if(mid>nl) Q.push(ques(nl,mid-1,npl,resp));
		if(mid<nr) Q.push(ques(mid+1,nr,resp,npr));
	}
	myio::print_int(ans+1,ans+1+n,'\n');
	delete segtree;
	return 0;
}