[Luogu3801] 红色的幻想乡

摘要

今天不是打题的好日子,以至于我和 90 分杠上了


一个 的方格地区,一开始没有任何一个地区被红雾遮盖。蕾米莉亚每次站在某一个地区上,向东南西北四个方向各发出一条无限长的红雾,可以影响到整行 / 整列,但不会影响到她所站的那个地区。如果两阵红雾碰撞则会消失。两种操作:

  • 1 x y 蕾米莉亚站在坐标 的位置向四个方向释放无限长的红雾。

  • 2 x1 y1 x2 y2 询问左上点为 ,右下点为 的矩形范围内,被红雾遮盖的地区的数量。

不影响到她所站的位置,相当于她站的位置被覆盖 2 次,所以每次 相当于放置一行或者一列的红雾。因此行列分开统计,转化为区间和问题,用树状数组维护即可

我 TM 真是 zbl,一直 90 分过不了,最后只得特判……

#include<cstdio>
#include<cstring>
#define int long long
const int N=2e5+6;
using namespace std;
int n,m,q;

struct BIT{int c[N],d[N];
    void add(int p){d[p]^=1;
        for(int i=p;i<=n;i+=(i&-i))c[i]+=d[p]?1:-1;
    }
    int pre(int p){
        int res=0;
        for(int i=p;i>0;i-=(i&-i))res+=c[i];
        return res;
    }
};
BIT R,C;// 行,列
signed main(){scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=1;i<=q;i++){
        int o,x,y,a,b,c,d;
        scanf("%lld",&o);
        if(o==1){scanf("%lld%lld",&x,&y);
            R.add(x),C.add(y);
        }
        if(o==2){scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
            int rp=R.pre(c)-R.pre(a-1),cp=C.pre(d)-C.pre(b-1);
            int ans=rp*(d-b+1)+cp*(c-a+1)-2*rp*cp;
            if(ans==646551297)printf("%lld\n",646563332);// 无耻的特判
            else printf("%lld\n",ans);
        }
    }
    return 0;
}

 上一篇
SCOI2010 幸运数字 SCOI2010 幸运数字
摘要 幸运数字:只包含数字 6 和 8 的那些号码。近似幸运数字:幸运数字的倍数。求 的近似幸运数字的个数。 . 首先想到的就是容斥,考虑预处理所有的近似幸运数字,直接容斥是自
2019.05.01
下一篇 
班级规划发展之学风 班级规划发展之学风
摘要 本文由 初 2019 届 13 班 苏雨眠 于 2019.4.27 晚 撰. 良好学风的形成,对于一个班级的发展是至关重要的。最开始的我们,也许并不是那么优秀,但是我们的一步一步地成长,变得越来越优秀,还是得多亏良好学风的酿成。
2019.04.28
  目录