题解：AT_dwango2015_prelims_5 電波局

· · 题解

题目大意：给出一个边长为 n 的正三角形平面，初始有 m 次覆盖操作，每次覆盖一个正三角形区域内的点，然后有 q 次查询操作，每次查询一个正三角形区域内未被覆盖的点数。

首先将下标对齐后将正三角形变为等腰直角三角形。

求一个三角形未覆盖的点数，可以转变为先求出初始下被覆盖的总点数，然后将查询的三角形当成一次覆盖，再求出被覆盖的总点数，两次答案相减即为所求。

那么先考虑如果求初始的答案，再进行 q 次即可回答所有询问。

难点在于对重合部分的处理，那么我们希望对每个覆盖操作进行一些删减，使得每个点恰好被覆盖一次，并且覆盖的总面积是好计算的。

考虑对行从大到小进行扫描线，按照三角形的底边（即 a_i+c_i-1）从大到小加入每个三角形。

那么加入一个三角形 i 时，如果存在三角形 j 满足 a_i-b_i\le a_j-b_j，那么我们可以删减三角形 j 的行 \le a_i+c_i-1 的部分，因为这些部分都被 i 覆盖了。

否则我们可以删减三角形 i 的列 \ge b_j 的部分，因为这些部分都被 j 覆盖了。

考虑扫描线时用链表维护三角形 s_1,s_2,\cdots s_k 满足 b_{s_i}\lt b_{s_{i+1}},a_{s_i}-b_{s_i}\gt a_{s_{i+1}}-b_{s_{i+1}}。

那么每次加入新的三角形 i 时，找到对应的前驱后继，如果前驱包含 i 就直接跳过。

否则对前驱进行一次删减，然后考虑后继，如果被 i 包含就对后继进行删减，并且后继已经没有扫描线上方的部分了，将后继移除链表，接着考虑下一个后继，直到后继不被包含，对 i 进行删减。

注意到每个三角形只会被移除链表 1 次，所以对后继的删减次数是 O(m) 的，同时加入一个三角形最多只会对本身和前驱进行删减，因此总共的删减次数是 O(m) 的。

在每次对三角形删减时，统计上一次删减到这一次删减之间的行区域的面积，简单分讨后可以 O(1) 计算。

时间复杂度 O(m^2)，瓶颈在于找前驱后继，用数据结构维护可以做到 O(m\log m)，总复杂度 O(qm\log m)。

注意到询问时只会新加入一个三角形，我们却要对所有三角形重新求一遍前驱后继，是没有必要的。

首先因为是用链表维护，我们只要找到前驱即可。

考虑求出初始状态每个三角形的前驱，加入新的三角形后，我们暴力求出新加入的三角形的前驱。

而对于原先就有的三角形，前驱只有可能是原先的前驱或者是新加入的三角形，这是容易判断的。

这样我们就做到了 O(m^2) 预处理，O(m) 回答询问。

总时间复杂度 O(m(m+q))。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
typedef long long ll;
int n,m,q,pr[N],nx[N],l[N],r[N],d[N],Pr[N];
bool dl[N],fg;
struct node{
    int x,y,z;
    bool operator <(const node a)const{return x+z>a.x+a.z;}
}a[N];
ll Ans,ans;
bool cmp(int u,int v){
    return a[u].x-a[u].y<=a[v].x-a[v].y;
}
void calc(int i,int nw){
    int lv=a[i].x,rv=a[i].x+r[i]-l[i];
    if(rv<=nw)ans+=1ll*(d[i]-nw)*(r[i]-l[i]+1);
    else if(lv<=nw){
        r[i]=min(r[i],l[i]+d[i]-a[i].x);
        rv=a[i].x+r[i]-l[i];
        ans+=1ll*(d[i]-nw)*(r[i]-l[i]+1)-1ll*(rv-nw)*(rv-nw-1)/2;
    }else if(lv<=d[i]){
        if(rv<=d[i])ans+=1ll*(d[i]-lv+1+d[i]-rv+1)*(r[i]-l[i]+1)/2;
        else ans+=1ll*(d[i]-lv+1)*(d[i]-lv+2)/2;
    }
    d[i]=nw;
}
void work(int i,int u,int v){
    int nw=a[i].x+a[i].z-1;
    if(u&&cmp(u,i))return dl[i]=true,void();
    while(v<m+2&&cmp(i,v)){
        calc(v,nw);
        dl[v]=true,v=nx[v];
    }
    if(u&&a[i].y-1<r[u]){
        calc(u,nw);
        r[u]=a[i].y-1;
    }
    d[i]=nw;
    pr[i]=u,nx[i]=v;
    nx[pr[i]]=pr[nx[i]]=i;
    l[i]=a[i].y,r[i]=a[i].y+a[i].z-1;
    if(v<m+2)r[i]=min(r[i],a[v].y-1);
}
void ins(int i){
    int v=m+2;
    while(pr[v]&&a[pr[v]].y>=a[i].y)v=pr[v];
    int u=Pr[i]=pr[v];
    work(i,u,v);
}
void Ins(int i){
    int u,v;
    if(i==m+1){
        v=m+2;
        while(v&&a[pr[v]].y>=a[i].y)v=pr[v];
        u=pr[v];
    }else{
        u=Pr[i];
        if(dl[u]||fg&&nx[u]==m+1&&a[m+1].y<a[i].y)u=m+1;
        v=nx[u];
    }
    work(i,u,v);
}
void init(){
    nx[0]=m+2,pr[m+2]=0;
    for(int i=1;i<=m;++i)ins(i);
    for(int i=pr[m+2];i;i=pr[i])calc(i,0);
    Ans=ans;
}
void solve(){
    ans=0;
    nx[0]=m+2,pr[m+2]=0;
    for(int i=1;i<=m;++i)dl[i]=false;
    fg=false;
    for(int i=1;i<=m;++i){
        if(!fg&&a[m+1]<a[i])Ins(m+1),fg=true;
        Ins(i);
    }
    if(!fg)Ins(m+1);
    for(int i=pr[m+2];i;i=pr[i])calc(i,0);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a+1,a+m+1);
    init();
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        scanf("%d%d%d",&a[m+1].x,&a[m+1].y,&a[m+1].z);
        solve();
        printf("%lld\n",ans-Ans);
    }
    return 0;
}