[COI2009] PLAHTE 题解

zifanwang · 2022-10-27 21:30:08 · 题解

首先对于每一个矩形，若 x_2<0，就将 x_1,x_2 均乘上 -1 再交换，对于 y_1,y_2 也做同样的操作。

我们建立一个操作序列 a[0~1000]，和一个数组 d，每一个操作用 (x,y) 表示，就是在 d 内把所有 0 到 x 的位置加上 y。

我们再定义一种新的操作 [x,y,z]，表示对于每一个 0\le i\le x 都在 a[i] 处插入一个操作 (y,z)。

我们定义一种行为 \{i,x_1,x_2,z\}，表示执行：

• 若 x_1<0，就执行三个操作操作 [i,-x_1,z],[i,x_2,z],[i,0,-z]
• 若 x_1=0，就执行操作 [i,x_2,z]
• 若 x_1>0，就执行两个操作 [i,x_2,z],[i,x_1-1,-z]

下面对于每一个矩形的 y_1,y_2 进行分类：

• 若 y_1<0，执行行为 \{-y_1,x_1,x_2,1\},\{y_2,x_1,x_2,1\},\{0,x_1,x_2,-1\}
• 若 y_1=0，执行行为 \{y_2,x_1,x_2,1\}
• 若 y_1>0，执行行为 \{y_2,x_1,x_2,1\},\{y_1-1,x_1,x_2,-1\}

因为询问的时间是单调递增的，可以记录一个时间 t，表示当前是 t 时刻，初始化 t=-1。对于每一个询问 k，重复下面的操作直到 t=k：

• 将 t+1，然后执行 a[t] 的所有操作。

最后的答案就对于每一个 0\le i\le k，d 数组内第 i 个位置对应的值的和，可以用树状数组维护 d。但是这只能过掉 |y_1|,|y_2|\le 1000 的数据。

正解

我们发现要执行的操作 [x,y,z] 的数量是不多的。

再经过仔细思考，可以发现 t 时刻的答案就是对于所有 [x,y,z]，(\min(x,t)+1)(\min(y,t)+1)\times z 的和。详细的原因可以看看题解的末尾。

我们先不执行这些操作，把这些操作插入到一个集合 S，然后维护四个值 sum,add,ans,addans：

• sum 表示所有 y>t 的操作 [x,y,z] 的 z\times(\min(x,t)+1) 的和。

• add 表示 t 每怎加 1 时 sum 要增加的值，也就是所有 y>t\land x>t 的操作 [x,y,z] 的 z 的和。

• ans 表示所有 y\le t 的操作 [x,y,z] 对答案的贡献。

• addans 表示 t 每怎加 1 时 ans 要增加的值，也就是所有 y\le t\land x>t 的操作 [x,y,z] 的 z\times(y+1) 的和。

我们建立一个 dl 数组，对于每一个操作 [x,y,z] 在 dl[x+1] 处插入。

当 t 每次增加 1 时，枚举所有 dl[t] 内的操作 [x,y,z]：

• 若此操作已经在集合 S 内被删除了（也就是在这次询问之前 y\le t），就把 addans 减去 z\times(y+1)。

• 若此操作还在集合 S 内（也就是在这次询问之前 y>t），就把 add 减去 z。

直到 t=k 时 t 才停止增加，下面再更新集合 S。枚举所有满足 y\le k 的操作 [x,y,z]：

• 若 x\ge k，说明此操作还在未在上面的 dl 数组中被访问过，此时 sum 要减去 z\times(k+1)，add 减去 z，ans 加上 z\times (k+1)(y+1)，addans 加上 z\times (y+1)。

• 若 x<k，把 sum 减去 z\times (x+1)，ans 加上 z\times (x+1)(y+1)。

最终的答案就是 (t+1)\times sum+ans。

代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 1000003
#define md 1000000007
#define pb push_back
#define mkp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
inline int read(){
    int x=0;bool flag=true;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')flag=false;ch=getchar();}
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return flag?x:-x;
}
struct node{
    int x,y,z;
};
inline bool operator<(node x,node y){
    return x.y!=y.y?x.y<y.y:x.x!=y.x?x.x<y.x:x.z<y.z;
}
int n,m,t=-1;
vector<node>dl[mxn];
multiset<node>s;
ll sum,add,ans,ads;
void puta(int x,int y,int z){
    add+=z;
    s.insert({x,y,z});
    dl[x+1].pb({x,y,z});
}
void ins(int x,int l,int r,int y){
    if(l<0){
        puta(x,-l,y);
        puta(x,r,y);
        puta(x,0,-y);
    }else if(l==0){
        puta(x,r,y);
    }else{
        puta(x,r,y);
        puta(x,l-1,-y);
    }
}
signed main(){
    n=read();
    for(int i=0,x1,x2,y1,y2;i<n;++i){
        x1=read(),y1=read(),x2=read(),y2=read();
        if(x1<0&&x2<0){
            swap(x1,x2);
            x1=-x1,x2=-x2;
        }
        if(y1<0&&y2<0){
            swap(y1,y2);
            y1=-y1,y2=-y2;
        }
        if(y1<0){
            ins(-y1,x1,x2,1);
            ins(y2,x1,x2,1);
            ins(0,x1,x2,-1);
        }else if(y1==0){
            ins(y2,x1,x2,1);
        }else{
            ins(y2,x1,x2,1);
            ins(y1-1,x1,x2,-1);
        } 
    }
    m=read();
    int x;
    while(m--){
        x=read();
        while(t<x){
            t++;
            for(node i:dl[t]){
                auto it=s.find(i);
                if(it==s.end())ads-=i.z*(i.y+1ll);
                else add-=i.z;
            }
            sum+=add;
            ans+=ads;
        }
        while(s.size()&&(s.begin()->y)<=x){
            node i=*s.begin();s.erase(s.begin());
            if(i.x>=x){
                sum-=i.z*(x+1ll);
                add-=i.z;
                ans+=i.z*(i.y+1ll)*(x+1ll);
                ads+=i.z*(i.y+1ll);
            }else{
                sum-=i.z*(i.x+1ll);
                ans+=(i.x+1ll)*(i.y+1ll)*i.z;
            }
        }
        printf("%lld\n",sum*(x+1ll)+ans);
    }
    return 0;
}

问题：为什么 t 时刻的答案就是对于所有 [x,y,z]，(\min(x,t)+1)(\min(y,t)+1)\times z 的和。

题目要求的就是一个左下角为 (-k,-k)，右上角为 (k,k) 的大矩形和一些其他的矩形的交的面积之和。

因为最终的答案是所有 t\le k 时的 d 数组内的第 0 到 i 个位置对应的值的总和，操作 [x,y,z] 就可以转化成一个左下角是 (0,0)，右上角是 (x,y)，权值为 z 的矩形。

答案就是一个左下角是 (0,0)，右上角是 (k,k) 的大矩形和每一个 [x,y,z] 对应的矩形的交的面积乘以 z 的和。