menu ZigZagK的博客

正在努力加载中QAQ

[随机+差分]Codeforces799F【Beautiful fountains rows】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 75 次访问

题目概述

有 $m\times n$ 的矩阵,第 $i$ 行的 $[L_i,R_i]$ 是好的。现在要选出 $[A,B]$ 使得在所有行中要么没有好的元素要么有奇数个好的元素,求所有合法 $[A,B]$ 的 $\sum B-A+1$ 。

解题报告

神仙套路题,我们先给每行的线段随机一个权值,然后用差分求出每列被线段覆盖的情况,然后就可以愉快的用异或值判断了。但是没有好的元素这个条件皮得很,我们可以先把没有好的元素的情况算成合法,最后删除不合法的情况(这种情况一定是连续的一片)。

把 $[L,R]$ 好的元素的奇偶情况拿下来,如果把出现过的好的元素奇偶情况反一下其实就是判断异或值是不是 $0$ 。关键问题就是如果求出 $[L,R]$ 中出现的好的元素的集合。

考虑 $d_i$ 表示 $L\le i$ 的线段的异或和,$a_i$ 表示覆盖 $i$ 列的所有线段的异或值(之前的差分数组),$sum_i$ 表示 $a_i$ 的异或前缀和。那么对于一个区间 $[A,B]$ :

$sum_{B}\ xor\ sum_{A-1}$ 表示 $[A,B]$ 中好的元素的奇偶情况,$d_{B}\ xor\ d_{A}$ 表示 $A<L\le B$ 的线段的异或和,相比于与 $[A,B]$ 相交的线段少了 $L\le A,R\ge A$ 的这些线段。

你会发现少掉的其实就是 $a_A$ ,所以 $sum_{B}\ xor\ sum_{A-1}=d_B\ xor\ d_A\ xor\ a_A$ 。

那么也就是 $sum_B\ xor\ d_B=sum_A\ xor\ d_A​$ ,map统计一下就好了。

示例程序

#include<cstdio>
#include<cstdlib>
#include<unordered_map>
using namespace std;
typedef unsigned long long ULL;typedef long long LL;
const int maxn=200000;

int n,m;ULL val[maxn+5],a[maxn+5],d[maxn+5],sum[maxn+5];
unordered_map<ULL,LL> f;unordered_map<ULL,int> g;LL ans;

#define Rand() ((ULL)rand()*rand()*rand()+(ULL)rand()*rand()+rand())
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=(srand(759405),scanf("%d%d",&m,&n),1),L,R;i<=m;i++)
        scanf("%d%d",&L,&R),val[i]=Rand(),a[L]^=val[i],a[R+1]^=val[i],d[L]^=val[i];
    for (int i=1;i<=n;i++) a[i]^=a[i-1],d[i]^=d[i-1],sum[i]=sum[i-1]^a[i];
    for (int i=1;i<=n;i++) f[sum[i]^d[i]]+=i-1,g[sum[i]^d[i]]++,ans+=(LL)g[sum[i]^d[i]]*i-f[sum[i]^d[i]];
    for (int i=1,L=1;i<=n;i++) if (!a[i]) ans-=(LL)(i-L+1)*i-(LL)(L-1+i-1)*(i-L+1)/2; else L=i+1;
    return printf("%lld\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
邮箱不能为空,请填写正确格式
网址请用http://或https://开头
评论不能为空
资瓷Markdown和LaTex数学公式
keyboard_arrow_up