当你发现某一道题给出了 \(1\le n\le 2\cdot 10^5 , 2 \le m \le 2\cdot 10^5 , 2 \le k \le \min(10, m)\) 的数据范围，你大胆猜测复杂度取决于 \(k\)，但这个不大不小的范围和不大不小的时限让你很纠结是否使用状压，冲一发之后发现 \(O(nk2^k)\) 是过不了的，但是你发现似乎有很多不必要的转移，然后你把它放在一起做，你就通过了这道题，最劣是 \(9\) 个 \([1,n]\) 和对所有奇数位置放 \([i,i]\)，但是卡不掉，可能因为本来 \(dp\) 就跑得快而且这个做法每个步骤都很慢
点击查看代码
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define N 200005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
int n,m,K;
vector<int>q,rai[N];
vector<pair<int,int>>line;
int dp[2][1025][11],st[1025],rev[11],lg[1025],ppcnt[1025];
inline void chkmax(int&x,int y){x<y?x=y:x;}
namespace SGT{
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
vector<int>vec[N<<2];int tag[N<<2];
void Build(int k,int l,int r){
vec[k].clear();tag[k]=0;if(l==r)return;
Build(ls,l,mid);Build(rs,mid+1,r);
}
void Modify(int k,int l,int r,int x,int y,int z){
if(l>=x&&r<=y)return tag[k]++,vec[k].emplace_back(z),void();
if(x<=mid)Modify(ls,l,mid,x,y,z);
if(mid<y)Modify(rs,mid+1,r,x,y,z);
}
void dfs(int k,int l,int r){
if(l==r){
if(tag[k]<=K)q.emplace_back(l);
return;
}
tag[ls]+=tag[k];tag[rs]+=tag[k];tag[k]=0;
dfs(ls,l,mid);dfs(rs,mid+1,r);
}
void Down(int k,int l,int r,int x,vector<int>&y){
for(auto u:vec[k])y.emplace_back(u);if(l==r)return;
x<=mid?Down(ls,l,mid,x,y):Down(rs,mid+1,r,x,y);
}
}
using namespace SGT;
void solve(){
n=read();m=read();K=read();
Build(1,1,n);
for(int i=1,l,r;i<=m;i++)l=read(),r=read(),Modify(1,1,n,l,r,i);
q.clear();dfs(1,1,n);int len=q.size();
if(!q.size())return void(puts("0"));
for(int i=0;i<len;i++)rai[i].clear(),Down(1,1,n,q[i],rai[i]);
for(int s=0;s<1<<K;s++)
for(int i=0;i<=K;i++)dp[0][s][i]=dp[1][s][i]=-n;
dp[0][0][0]=0;
vector<pair<int,int>>Q;Q.emplace_back(0,1);
for(int i=0;i<len;i++)sort(rai[i].begin(),rai[i].end());
for(int i=1;i<len;i++){
bool flg=(rai[i].size()==rai[i-1].size());
if(flg)for(int p=0,siz=rai[i].size();p<siz;p++)flg&=(rai[i][p]==rai[i-1][p]);
if(!flg)Q.emplace_back(i,1);
else Q.back().second++;
}
len=Q.size();
for(int i=0;i<len;i++){
int id=Q[i].first,siz=rai[id].size(),val=Q[i].second;
if(i>0){
int ID=Q[i-1].first,Siz=rai[ID].size();
for(int p=0;p<K;p++)rev[p]=-1;
for(int p=0;p<siz;p++)
for(int q=0;q<Siz;q++)
if(rai[id][p]==rai[ID][q])rev[q]=p;
for(int s=1;s<1<<Siz;s++){
st[s]=st[s^(s&(-s))];
if(~rev[lg[s&(-s)]])st[s]|=(1<<rev[lg[s&(-s)]]);
}
for(int s=0;s<1<<Siz;s++){
int t=st[s],ned=ppcnt[((1<<siz)-1)^t];
for(int p=0;p<=K;p++)chkmax(dp[i&1][t][p],dp[!(i&1)][s][p]);
for(int p=ned;p<=K;p++)
chkmax(dp[i&1][(1<<siz)-1][p],dp[!(i&1)][s][p-ned]+val);
for(int p=0;p<=K;p++)dp[!(i&1)][s][p]=-n;
}
}
else dp[i&1][(1<<siz)-1][siz]=val;
}
int ans=0;
for(int s=0;s<1<<K;s++)
for(int i=0;i<=K;i++)chkmax(ans,dp[(len-1)&1][s][i]);
printf("%d\n",ans);
}
signed main(){
freopen("data.in","r",stdin);
for(int i=2;i<1<<10;i++)lg[i]=lg[i>>1]+1;
for(int i=0;i<1<<10;i++)ppcnt[i]=__builtin_popcount(i);
int T=read();while(T--)solve();
return 0;
}