请确认你要搜索的关键词不是DP里面的背包问题而是一道叫做“背包问题”的数据结构题再来看。

简要题意：

你有$m$个背包容量为$t_i$，你有$n$个物品，重量为$W_i$，权值为$V_i$。

请你求出满足如下限制的最长的物品序列$p$，假设长度为$len$。

对于$\forall 1\le i<len$，$W_{p_i}\le W_{p_{i+1}}$对于$\forall 1\le i<len$，$V_{p_i}\le V_{p_{i+1}}$存在一个长度为$len$的背包序列$q$，满足$\forall 1\le i\le len$，$W_{p_i}\le t_{q_i}$

由于有多组数据，复杂度为$O(n{\log }^{2}n)$的做法无法通过，要求复杂度为$O(n\log n)$

题解：

考虑一个满足前两个限制的序列$p$，然后拿出最大的$len$个背包，如果这个都装不了那肯定gg。否则肯定是类似$LIS$该怎么搞怎么搞。

按照$W$排序后，考虑用权值线段树维护结尾为$V$的最长序列。

问题在于哪些可以拿来更新，显然长度为$len$必须在考虑了前$len$个背包之后才能用于更新其他位置的答案，记录一下哪些更改需要在什么时候执行即可。

---

代码（其实应该用树状数组，失智用了ZKW线段树，懒得改了）：

#include<bits/stdc++.h> #define ll long long #define re register #define cs const namespace IO{ inline char gc(){ static cs int Rlen=1<<22|1; static char buf[Rlen],*p1,*p2; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; } template<typename T>inline T get(){ char c;T num; while(!isdigit(c=gc()));num=c^48; while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48); return num; } inline int gi(){return get<int>();} } using namespace IO; using std::cerr; using std::cout; typedef std::pair<int,int> pii; #define fi first #define se second cs int N=1e5+7; namespace SGT{ cs int N=1<<18|7; int mx[N];int M; inline void build(int n){ for(M=1;M<=n+1;M<<=1); memset(mx,0,sizeof mx); } inline void ins(int p,int v){ if(mx[p+M]>=v)return ; for(mx[p+=M]=v,p>>=1;p;p>>=1)mx[p]=std::max(mx[p<<1],mx[p<<1|1]); } inline int query(int l,int r){ int ans(0); for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){ if(~l&1)ans=std::max(ans,mx[l^1]); if(r&1) ans=std::max(ans,mx[r^1]); }return ans; } } int n,m,tot; int t[N],b[N],f[N]; pii a[N]; std::vector<int> vec[N]; void solve(){ n=gi(); for(int re i=1;i<=n;++i){ a[i].fi=gi(),a[i].se=gi(); b[i]=a[i].se; } std::sort(b+1,b+n+1); tot=std::unique(b+1,b+n+1)-b-1; for(int re i=1;i<=n;++i){ a[i].se=std::lower_bound(b+1,b+tot+1,a[i].se)-b; } SGT::build(tot);m=gi(); for(int re i=1;i<=m;++i)t[i]=gi(); std::sort(t+1,t+m+1); std::sort(a+1,a+n+1); std::reverse(t+1,t+m+1); std::reverse(a+1,a+n+1); int ans=0; for(int re i=1,lst=0;i<=n;++i){ while(lst<m&&a[i].fi<=t[lst+1]){ for(int re j:vec[lst]) SGT::ins(a[j].se,f[j]); ++lst; } if(a[i].fi<=t[lst]){ f[i]=SGT::query(a[i].se,tot)+1; ans=std::max(ans,f[i]); if(f[i]<lst)SGT::ins(a[i].se,f[i]); else vec[f[i]+1].push_back(i); } } for(int re i=1;i<=n+1;++i)vec[i].clear(),f[i]=0; cout<<ans<<"\n"; } //#undef zxyoi signed main(){ #ifdef zxyoi freopen("bag.in","r",stdin); #else #ifndef ONLINE_JUDGE freopen("bag.in","r",stdin);freopen("bag.out","w",stdout); #endif #endif int T=gi();while(T--)solve(); return 0; }