P7842 「C.E.L.U-03」探险者笔记 III - 题解

link T3 desu.

怎么都是版题（）

原式子非常难看，不妨令 $w_i=\sum\limits_{k=1}^{sum_i}b_{a_{i_k}}$，原来的 $w$ 改为 $W$。

可以发现这道题本质上是一个三维偏序，能从 $j$ 转移到 $i$ 的条件为：

$$\begin{cases} j<i \\ W+w_j\ge w_i \\ S_j \subseteq S_i \end{cases}$$

那么考虑 CDQ 分治。先按照第一维分治，然后倒着排序第二维，使用双指针同步维护 “$S$ 子集中 dp 的最大值” 即可。

那么现在的问题是如何能维护 $S$，考虑使用经典做法 Apple，在加入时将其前 $9$ 位的超集给更新，查询时枚举后 $9$ 位的子集即可。

总复杂度 $O(m\log m\cdot 2^{\frac{n}{2}})$。

那么转移时就先递归进左边，然后处理跨 mid 的转移，再递归进右边即可。

Code

inline void updatemax(ll &x,ll y){x=max(x,y);}
//高10位为超集，低10位为子集

const int maxsq=(1<<9)+15,sq=(1<<9);
int lowbits,highbits;
ll mx[maxsq][maxsq];
inline void update(int x,ll val){
	lowbits=x&(sq-1);highbits=(x>>9);
	for(int j=highbits;j<sq;j=(j+1)|highbits){
		updatemax(mx[j][lowbits],val);
	}
}
inline void clear(int x){
	lowbits=x&(sq-1);highbits=(x>>9);
	for(int j=highbits;j<sq;j=(j+1)|highbits){
		mx[j][lowbits]=0;
	}
}
inline ll query(int x){
	ll res=0;
	lowbits=x&(sq-1),highbits=(x>>9);
	for(int j=lowbits;;j=(j-1)&lowbits){
		updatemax(res,mx[highbits][j]);
		if(j==0) break;
	}
	return res;
}


void solve(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	solve(l,mid);
	sort(a+l,a+mid+1,[](Node x,Node y){return x.w>y.w;});
	sort(a+mid+1,a+r+1,[](Node x,Node y){return x.w>y.w;});

	int i=l;
	for(int j=mid+1;j<=r;++j){
		ll S=a[j].S;
		while(i<=mid&&a[i].w+w>=a[j].w){
			update(a[i].S,ans[a[i].id]);
			++i;
		}
		ll res=query(S);
		updatemax(ans[a[j].id],res+a[j].val);
	}
	for(int j=l;j<i;++j) clear(a[j].S);

	sort(a+l,a+mid+1,[](Node x,Node y){return x.id<y.id;});
	sort(a+mid+1,a+r+1,[](Node x,Node y){return x.id<y.id;});
	solve(mid+1,r);
}

sub