题意：
有 $m$ 个小朋友，圣诞老人有 $N$ 个咒语，第 $i$ 个咒语施展出来的话，可以给 $[Li,Ri]$ 范围内的小朋友一块糖果，对每个小朋友来说，他得到的糖如果是奇数的话就会happy，否则就会不happy。
现在要求求出当圣诞老人采取某种最优的施展咒语的策略（一些用了一些没用，具体不需要求出来）的时候，最多有多少个小朋友可以happy？
题目保证，每个小朋友最多被 k 个咒语覆盖到。
数据范围： $m \le 10^9$, $N \le 10^5$, $1 \le k \le 8$, $1 \le Li \le Ri \le m$
题解：
(先吐槽下这题竟然2600分，这可是个div2D)
用扫描线的思想来做。
假设有一根竖直的扫描线在横轴上扫过去，那么他只会在每个 $[Li,Ri]$ 段的头尾两端发生状态变化，我们设置这些点为关键点，当我们采取某种特定的策略的时候，两个关键点之间的数据是不会发生变化的。
由于每个点最多被 $k$ 个线段覆盖，我们可以暴力的枚举出来当前扫描到的点的状态，即它被多少种线段覆盖到了，这个状态显然可以用二进制位来表示。由于我们是一个一个关键点找过去的，而两个关键点之间的数据状态仅由前一个点即可确定，所以我们的dp转移只需要考虑前一个点。
具体的转移：设 $dp[i][S]$ 为考虑到了第i个关键点（按从小到大的顺序），覆盖当前点的线段状态为 $S$ 的时候，最优解是多少。
- 当当前点为某线段的起点时，我们考虑每个 $S$ 中是否包含了第 $i$ 条线段，如果
- 包含了，那么 $dp[i][S]=dp[i-1][S^(1<<p)]+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$ ,因为我们相当于加上了新的一段；(其中p为当前线段所应在的二进制位，下同)
- 没包含，那么$dp[i][S]=dp[i][S]$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$，等于说我们的扫描线在这一段仍然是按照之前的状态在扫描。
- 当当前点为某线段的终点时，我们仍然考虑每个 $S$ 中是否包含了第 $i$ 条线段，如果
- 包含了，由于这条线段到此我们认为结束了，所以这种状态根本不合法，直接设置为$-INF$
- 没包含，那么$dp[i][S]=max(dp[i-1][S],dp[i-1][S^(1<<p)])$ $+(i到第i+1个关键点的距离)*(S中二进制位为1的奇偶性)$，因为我们前面一段可能选了大，也可能不选更大，我们需要取个最优解。
然后我们可以发现两个转移都有方向性，我们可以用滚动数组忽略掉第一维，也就是说状态数组可以只开 $dp[1<<8]$ 即可。
实现细节：
- 使用同一个 $used[8]$ 数组来表示当前的二进制位都表示的是第几条线段，因为每过一个点只会有最多1个点发生变化，所以这种方法是非常简洁的，不用像很多写法一样重新映射。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxn = 100005;
pair<int,int> pos[maxn*2];
int dp[(1<<8)+5],used[8];
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;++i){
cin>>pos[2*i-1].first>>pos[2*i].first;
pos[2*i-1].second=i,pos[2*i].second=-i;
++pos[2*i].first;//[l,r] next is [r+1,...
}
sort(pos+1,pos+1+2*n);
for(int i=1;i<(1<<k);++i) dp[i]=-INF;
for(int it=1,p,id,len;it<=(n<<1);++it){
len=(it==(n<<1)?0:pos[it+1].first-pos[it].first);
id=pos[it].second;
if(id>0){//start
for(int i=0;i<k;++i)
if(!used[i]){
used[p=i]=id;
break;
}
for(int j=(1<<k)-1;j>=0;--j){
if((j>>p)&1){
dp[j]=dp[j^(1<<p)]+len*__builtin_parity(j);
}else{
dp[j]+=len*__builtin_parity(j);
}
}
}else{//end
for(int i=0;i<k;++i)
if(used[i]==-id){
used[p=i]=0;
break;
}
for(int j=0;j<(1<<k);++j){
if((j>>p)&1){
dp[j]=-INF;
}else{
dp[j]=max(dp[j],dp[j^(1<<p)])+len*__builtin_parity(j);//choose or not
}
}
}
}
cout<<dp[0];
return 0;
}