浙江龙网

  1. 首页 > 生活百科 > >

洛谷 P4135 作诗 题解

生活百科

题面 。
之前做过一道很类似的题目 洛谷P4168蒲公英 ，然后看到这题很快就想到了解法，做完这题可以对比一下，真的很像 。
题目要求区间内出现次数为正偶数的数字的数量 。
数据范围1e5，可以分块 。
我们预处理出这么两个数组 。
一个是某个数字出现次数的分块前缀和，这个很简单 。
一个是sum[ i ][ j ]代表从第i个分块到第j个分块出现次数为正偶数的数字的个数 。
这个数组很好维护，只需要枚举左端点分块和右端点分块然后统计数字出现次数即可 。
这些代码里有一些细节，可以结合注释理解 。
for(int i=1;i<=get_pos(n);i++){        int kin=0;        for(int j=i;j<=get_pos(n);j++){            for(int k=(j-1)*len+1;k<=min(n,j*len);k++){//这里有一些细节                tmp[a[k]]++;                if((tmp[a[k]]&1))//如果这个数加完之后变成了奇数                    if(tmp[a[k]]>1)//如果加完之后出现次数大于一，那么这个数就作为正偶数被统计进答案了，要减掉                        kin--;                    else//否则这个数在加一之前没有被统计过，没有必要更改，这里写个else是因为防止与下面那个else产生冲突                        kin+=0;                else//加完之后如果变成了偶数那肯定从奇数变成了正偶数 ， 对答案有贡献                    kin++;            }            sum[i][j]=kin;        }        for(int j=1;j<=c;j++)//清空辅助数组            tmp[j]=0;    }接下来处理询问 。
对于询问的l,r，算出其所在的分块lb,rb 。
若l，r所在分块相同或相邻则暴力计算，时间复杂度n1/2 。
若l，r所在分块之间相隔至少一个分块 ， 那么先将答案设成这两个分块之间的出现次数为正偶数的数字数量 。
然后 ， 计算两边散块内数字对答案的贡献 。
情况较多，可结合注释理解 。
void get_q(){    ans=0;    for(int i=l;i<=lb*len;i++){        tmp[a[i]]++;        if(tmp[a[i]]&1)//如果这个数在散块中出现次数为奇数            if((tim[rb-1][a[i]]-tim[lb][a[i]])&1)//如果它在中间块中出现次数为奇数，那么它没有被预先统计进答案里，且目前它对答案有贡献                ans++;            else//如果这个数在中间块中出现次数为偶数                if(tim[rb-1][a[i]]-tim[lb][a[i]]>0)//如果这个数在中间块中出现次数为正偶数，那么它已经作为答案被统计过了，现在不符合条件要减掉                    ans--;                else//这个数并没有作为答案被统计过                    if(tmp[a[i]]>1)//如果这个数在散块中之前已经作为正偶数被统计了，要减掉                        ans--;                    else//否则并没有影响                        ans-=0;        else//这个数在散块中出现次数为偶数            if(tim[rb-1][a[i]]-tim[lb][a[i]]&1)//如果这个数在中间块中出现次数为奇数 ， 那么这个数的出现次数被作为正偶数统计过 ， 要减掉                ans--;            else//否则这个数之前没有算进答案里，要加进去                ans++;    }    for(int i=(rb-1)*len+1;i<=r;i++){//以下分类同上        tmp[a[i]]++;        if(tmp[a[i]]&1)            if((tim[rb-1][a[i]]-tim[lb][a[i]])&1)                ans++;            else                if(tim[rb-1][a[i]]-tim[lb][a[i]]>0)                    ans--;                else                    if(tmp[a[i]]>1)                        ans--;                    else                        ans-=0;        else            if(tim[rb-1][a[i]]-tim[lb][a[i]]&1)                ans--;            else                ans++;    }    for(int i=l;i<=lb*len;i++)//清空辅助数组        tmp[a[i]]--;    for(int i=(rb-1)*len+1;i<=r;i++)        tmp[a[i]]--;    ans+=sum[lb+1][rb-1];}

推荐阅读


上一篇：带权bitset?/bitset优化莫队 模板 洛谷P4135 Ynoi2016 掉进兔子洞 题解

下一篇：洛谷P4168 蒲公英 分块处理区间众数模板