CodeForces 1313D Happy New Year

我在1313e的题解里提到本题非常难，是我出言不逊了。。 我之前读错题意了。。

洛谷题目页面传送门 & codeforces题目页面传送门

有\(m\)孩子，编号为\(1\sim m\)。有\(n\)条咒语，第\(i\)条可以让编号在\([l_i,r_i]\)内的所有孩子得到\(1\)颗糖，每条咒语可以施或不施。要求最大化得到奇数颗糖的孩子的数量。输出这个数量。保证若施所有咒语，那么每个孩子得到的糖的数量不超过\(s\)。

\(n\in \left[1,10^5\right],m\in\left[1,10^9\right],s\in[1,8]\)。

“保证若施所有咒语，那么每个孩子得到的糖的数量不超过\(s\)”这句话极其重要，它告诉我们每个孩子都在不超过\(s\)条咒语的区间里，即每个孩子都只有不超过\(s\)条咒语对他/她有效。这启示我们对每个孩子枚举所有对他/她有效的\(x\)条咒语哪些施、哪些不施的\(2^x\)种情况，从而状压dp。

dp之前，这个\(m\)的范围一看就是要离散化。我们把\(\forall i\in[1,n],l_i-1,r_i\)这\(2n\)个数压入即将sort、unique的1-indexed数列\(nums\)里，sort、unique之后，\(\forall i\in[1,|nums|]\)，今后的数\(i\)就代表从前的区间\((nums_{i-1},nums_i]\)，特殊地，\(nums_0=0\)。这样可以保证今后的每个孩子代表的从前的区间内每个数所在咒语区间情况相同，因为咒语区间的端点代表所在咒语区间情况相同段的分界。但还有一个问题：有可能从前的某个后缀内的数都没有被包含到任何今后的数所表示的区间里。很简单，只要再往\(nums\)里加一个数\(m\)即可。时间复杂度\(\mathrm o(n\log_2n)\)。

接下来考虑dp。先预处理出0-indexed数列数组\(in\)，\(in_i\)表示今后的数\(i\)所表示的从前的区间内每个孩子所在的咒语区间编号组成的数列（对于区间内每个孩子生成的数列都是一样的），顺序随意。这样一来，\(\forall i\in[1,n],\forall j\in[1,|nums|]\)，若\(\forall k\in(nums_{j-1},nums_j],k\in[l_i,r_i]\)，则咒语\(i\)对于今后的数\(j\)便有了一个新编号。显然，预处理这个数列数组的时间复杂度为\(\mathrm o(ns)\)。

设\(dp_{i,j}\)表示考虑到今后的数\(i\)，对于bitmask\(j\)满足\(x\in j\)当且仅当施咒语\(in_{i,x}\)时，前\(nums_i\)个孩子得到奇数颗糖的最大的数量。显然边界是\(dp_{0,0}=0\)，目标是\(\max\limits_i\{dp_{|nums|,i}\}\)。转移时只需要注意\(1\)个限制：\(\{in_{i}\}\)和\(\{in_{i-1}\}\)可能交集不为空，此时那些交集里的咒语不能精神分裂，即\(\forall x\in\{in_{i}\}\cap\{in_{i-1}\}\)，咒语\(x\)在\(j\)和转移到的bitmask\(k\)里状态必须相等。

那么状态转移方程是：

\[dp_{i,j}=\max\limits_{cantrs(i,j,k)}\{dp_{i-1,k}+|j|\bmod2\times(nums_i-nums_{i-1})\}\]

其中\(cantrs(i,j,k)\)表示\(dp_{i,j}\)转移到\(dp_{i-1,k}\)满足上述限制。

这样直接按方程来转移的话，状态数\(\mathrm o(2^sn)\)，每次转移对象\(\mathrm o(2^s)\)，\(cantrs\)判断\(\mathrm o(s)\)，所以时间复杂度是\(\mathrm o(4^sns)\)，太大了。显然我们最多只能接受\(\mathrm o(2^sn)\)的。

注意到若对于\(2\)个状态\(j_1,j_2\)，\(\forall x\in\{in_{i}\}\cap\{in_{i-1}\}\)，咒语\(x\)在\(j_1,j_2\)内的状态相同，那么\(dp_{i,j_1},dp_{i,j_2}\)能转移到的合法状态集合是完全相同的。于是设\(and_i=\{in_{i}\}\cap\{in_{i-1}\}\)，我们可以按\(and\)内所有元素的\(2^{|ans|}\)种状态分类，这样对每类统一找合法转移对象，计算对于此类中所有bitmask\(j\)，\(\max\limits_{cantrs(i,j,k)}\{dp_{i-1,k}\}\)，然后对于此类中所有状态\(\mathrm o(1)\)计算dp值。但是复杂度依然没有变。

要想改变复杂度，最重要的是去除\(cantrs\)判断。注意到\(\forall k\)，\(dp_{i-1,k}\)能且仅能转移到\(1\)个状态，于是我们若能找到命中率\(100\%\)且不用判断的找合法转移对象方式就能保证\(\mathrm o(2^sn)\)的复杂度。这非常简单，只需要将每个\(k\)拆成\(\in and\)和\(\notin and\)这\(2\)部分，对于每类，直接固定\(\in and\)的部分，枚举\(\notin and\)的部分即可。但是实现起来并不会那么顺利，因为\(2\)部分分别可能在\(k\)中不连续，无法直接用位运算\(\mathrm o(1)\)合并，于是我们可以预处理，对于\(2\)个部分都给此部分每种状态编个号，并记录它在\(k\)中的状态，最后将\(2\)部分在\(k\)中的状态\(\mathrm{or}\)起来即可得到\(k\)。对于每类，现在已经找到所有合法转移对象，即算出了对于此类中所有bitmask\(j\)，\(\max\limits_{cantrs(i,j,k)}\{dp_{i-1,k}\}\)，现在只需再命中率\(100\%\)且不用判断地找到此类中所有状态（方法和上述找转移对象类似），即可\(\mathrm o(1)\)得到每个\(dp_{i,j}\)的值。

最终总复杂度为\(\mathrm o(n\log_2n)+\mathrm o(ns)+\mathrm o(2^sn)=\mathrm o(n(\log_2n+2^s))\)，轻微卡常，但不用在意。

下面上代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define x first
#define y second
int lowbit(int x){return x&-x;}
int lbt(int x){return __builtin_ctz(x);}
const int n=100000;
int n/*咒语数*/,m/*孩子数*/,s/*每个孩子最多在的咒语区间数量*/;
int l[n+1],r[n+1];//咒语区间 
vector<int> nums;//离散化数组 
void discrete(){//离散化 
    sort(nums.begin(),nums.end());
    nums.resize(unique(nums.begin(),nums.end())-nums.begin());
    for(int i=1;i<=n;i++)
        l[i]=lower_bound(nums.begin(),nums.end(),l[i])-nums.begin(),
        r[i]=lower_bound(nums.begin(),nums.end(),r[i])-nums.begin();
}
vector<int> in[3*n+1];//所在咒语区间编号数列数组 
vector<int> dp[3*n+1];//dp数组 
int main(){
    cin>>n>>m>>s;
    nums.pb(0);nums.pb(m); 
    for(int i=1;i<=n;i++)scanf("%d%d",l+i,r+i),nums.pb(l[i]-1),nums.pb(r[i]);
    discrete();
    for(int i=1;i<=n;i++)for(int j=l[i];j<=r[i];j++)in[j].pb(i);//预处理 
    dp[0].resize(1,0);//边界 
    for(int i=1;i<nums.size();i++){
//      printf("%d dping\n",i);
//      printf("\tin=",i);for(int j=0;j<in[i].size();j++)cout<<in[i][j]<<" ";puts("");
        dp[i].resize(1<<in[i].size());//决定dp[i]元素个数 
        vector<pair<int,int> > _and;//对于所有x in {in[i]} cap {in[i-1]}，(x在in[i]中的编号，x在in[i-1]中的编号)组成的二元组序列 
        for(int j=0;j<in[i].size();j++)for(int k=0;k<in[i-1].size();k++)if(in[i][j]==in[i-1][k])_and.pb(mp(j,k));//预处理and 
//      printf("\t_and=");for(int j=0;j<_and.size();j++)printf("(%d,%d) ",_and[j].x,_and[j].y);puts("");
        vector<int> nin_and1/*j中不在and中的部分*/,nin_and2/*k中不在and中的部分*/; 
        for(int j=0,k=0;j<in[i].size();j++)if(k>=_and.size()||(j==_and[k].x?k++,false:true))nin_and1.pb(j);//预处理nin_and1 
        for(int j=0,k=0;j<in[i-1].size();j++)if(k>=_and.size()||(j==_and[k].y?k++,false:true))nin_and2.pb(j);//预处理nin_and2 
//      printf("\tnin_and1=");for(int j=0;j<nin_and1.size();j++)cout<<nin_and1[j]<<" ";puts("");
//      printf("\tnin_and2=");for(int j=0;j<nin_and2.size();j++)cout<<nin_and2[j]<<" ";puts("");
        vector<int> chg1(1<<_and.size(),0),chg2(1<<nin_and1.size(),0),chg3(1<<_and.size(),0),chg4(1<<nin_and2.size(),0);
        for(int j=1;j<chg1.size();j++)chg1[j]=chg1[j^lowbit(j)]|1<<_and[lbt(j)].x;//预处理j中在and中的部分的每种状态在j中的状态 
        for(int j=1;j<chg2.size();j++)chg2[j]=chg2[j^lowbit(j)]|1<<nin_and1[lbt(j)];//预处理j中不在and中的部分的每种状态在j中的状态
        for(int j=1;j<chg3.size();j++)chg3[j]=chg3[j^lowbit(j)]|1<<_and[lbt(j)].y;//预处理k中在and中的部分的每种状态在j中的状态
        for(int j=1;j<chg4.size();j++)chg4[j]=chg4[j^lowbit(j)]|1<<nin_and2[lbt(j)];//预处理k中不在and中的部分的每种状态在j中的状态
        for(int j=0;j<chg1.size();j++){//枚举类 
            int mx=0;//对于此类中所有bitmask j，max[cantrs(i,j,k)]{dp[i-1][k]} 
            for(int k=0;k<chg4.size();k++)mx=max(mx,dp[i-1][chg3[j]|chg4[k]]);//算mx 
            for(int k=0;k<chg2.size();k++)dp[i][chg1[j]|chg2[k]]=mx+__builtin_parity(chg1[j]|chg2[k])*(nums[i]-nums[i-1]);//转移此类中的每个状态 
        }
//      for(int j=0;j<dp[i].size();j++)printf("\tdp[%d]=%d\n",j,dp[i][j]);
    }
    cout<<*max_element(dp[nums.size()-1].begin(),dp[nums.size()-1].end());//目标 
    return 0;
}