[luogu3801]红色的幻想乡

题目描述

经过上次失败后，蕾米莉亚决定再次发动红雾异变，但为了防止被灵梦退治，她决定将红雾以奇怪的阵势释放。
我们将幻想乡看做是一个n*m的方格地区，一开始没有任何一个地区被红雾遮盖。蕾米莉亚每次站在某一个地区上，向东南西北四个方向各发出一条无限长的红雾，可以影响到整行/整列，但不会影响到她所站的那个地区。如果两阵红雾碰撞，则会因为密度过大而沉降消失。
灵梦察觉到了这次异变，决定去解决它。但在解决之前，灵梦想要了解一片范围红雾的密度。可以简述为两种操作:
1 x y 蕾米莉亚站在坐标(x,y)的位置向四个方向释放无限长的红雾。
2 x1 y1 x2 y2 询问左上点为(x1,y1)，右下点为(x2,y2)的矩形范围内，被红雾遮盖的地区的数量。

解法

因为对于一次修改，一定会修改到底，怎么说的，就是这一列或者是这一整行都被我们修改了，那么我们就可以将这幅图抽象成两条数轴上的操作。
对于每一次的修改，我们只需要单点修改某一个节点上的数。
但是这个节点上需要记录什么信息呢？这种题目很明显用线段树维护比较好（树状数组也很好，但是我还是喜欢线段树），那么要节点要记录的数值有\(l\)，和\(r\)，除此之外，我们需要知道在这一段区间中，被红雾所覆盖的节点的总数。
然后单点修改就到这里位置。
关于查询操作，我们每次是查询两个线段树的区间和。
我们假设求出求出来的值分别是\(ansx\)和\(ansy\)，对于的分别是\(x\)轴上的答案和\(y\)轴上的答案。
然后在定义\(lenx\)和\(leny\)表示查找区间\(x\)的长度和和\(y\)区间的长度。
因为我们知道，两个红雾重合在一起就会被抵消掉，也就是说在查找区间内，所有的\(ansx\)和所有\(ansy\)全都会重合。为什么？因为每一次修改就一定是修改到底。
那么我们通过容斥原理，如果仅算\(x\)的答案就是\(ansy*x\)，也就是当前\(x\)数×有的\(y\)，同理\(y\)的答案是\(ansx*y\)，但是有消除，所以我们需要\(-\)掉\(2*ansx*ansy\)，为什么是\(2*ansx*ansy\)，而不是\(ansx*ansy\)，因为你不是在去掉重复，而是减掉消除的部分。

ac代码

#include<bits/stdc++.h>
#define LL long long
#define N 100005
using namespace std;
int read(){
    int w=0,x=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return w?-x:x;
}
int n,m,q;
struct segment_tree{
    #define ls (nod<<1)
    #define rs (nod<<1|1)
    #define mid ((l+r)>>1)
    struct node{
        int l,r;
        LL s;
    }tr[N<<2];
    void pushup(int nod){tr[nod].s=tr[ls].s+tr[rs].s;}
    void build(int l,int r,int nod){
        tr[nod].l=l; tr[nod].r=r; tr[nod].s=0;
        if(l==r) return;
        build(l,mid,ls);
        build(mid+1,r,rs);
    }
    void update_point(int nod,int k){
        int l=tr[nod].l,r=tr[nod].r;
        if(l==r){tr[nod].s^=1;return;}
        if(k<=mid) update_point(ls,k);
        else update_point(rs,k);
        pushup(nod);
    }
    LL query_sec(int nod,int ql,int qr){
        int l=tr[nod].l,r=tr[nod].r;
        if(ql<=l&&r<=qr) return tr[nod].s;
        LL res=0;
        if(ql<=mid) res+=query_sec(ls,ql,qr);
        if(qr>mid) res+=query_sec(rs,ql,qr);
        return res;
    }
}tr1,tr2;
int main(){
    n=read(),m=read(),q=read();
    tr1.build(1,n,1); tr2.build(1,m,1);
    while(q--){
        int opt=read();
        if(opt==1){
            int x=read(),y=read();
            tr1.update_point(1,x); tr2.update_point(1,y);
        }
        else{
            #define x1 saber
            #define x2 archer
            #define y1 caster
            #define y2 rider
            int x1=read(),y1=read(),x2=read(),y2=read();
            LL a1=tr1.query_sec(1,x1,x2),a2=tr2.query_sec(1,y1,y2);
            LL ans=a1*(LL)(y2-y1+1)+a2*(LL)(x2-x1+1)-a1*a2*2;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

对于自己代码的感想

因为\(y1\)成为了关键字，那么就重定义一下（我是一个\(Fate\)迷）QAQ。

巴特西

[luogu3801]红色的幻想乡

题目描述

解法

ac代码

对于自己代码的感想

最新文章

热门文章