ABC385D题解

· · 题解

我真不信有谁的比我另类

赛时因为懒得想一些其它的妙妙做法，第一眼看上去就觉得是扫描线。个人觉得这种做法非常好理解。首先本题肯定是难在第二问，接下来讲解解法以及思考痕迹。

观察样例：

可以发现第二问所求就是它给出的点在自己的路线的路线上的个数。

我们把一个点看作是以它为左下角的一个大小为一的方格，这样便可以扫描线了。

然后正着考虑不好想，考虑容斥，先求出自己路线的面积，设其为 sum，再求出自己路线和所有的点并在一起的面积，设其为 k，答案即为 n-k+sum。然后第一问是好求的，这样这题便做完了。

code:

#include<bits/stdc++.h>
#define int long long
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define mid ((l+r)>>1)
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N=8e5+5;
bool ST;
int n,m,T;

struct rectangle{
    int x,y,X,Y;
}a[N],b[N];
struct line{
    int y,x,X,flag;
}li[N];
bool cmp(line x,line y){
    return x.y<y.y;
}
int yy[N],xx[N];
struct node{
    int l,r,sum,all,tag,res;
}t[N<<2];
void build(int x,int l,int r){
    t[x].l=l,t[x].r=r;
    if(l==r){
        t[x].all=xx[l+1]-xx[l];
        return;
    }
    build(ls(x),l,mid);build(rs(x),mid+1,r);
    t[x].all=t[ls(x)].all+t[rs(x)].all;
}
void add(int x,int l,int r,int sum){
    if(t[x].l>=l&&t[x].r<=r){
        t[x].tag+=sum;
        if(t[x].tag) {
            t[x].sum=t[x].all;
        } 
        else {
            if(t[x].l!=t[x].r) {
                t[x].sum=t[ls(x)].sum+t[rs(x)].sum;
            }
            else t[x].sum=0;
        }
        return;
    }
    if(t[x].l>r||t[x].r<l) return;
    add(ls(x),l,r,sum);add(rs(x),l,r,sum);
    if(t[x].tag) t[x].sum=t[x].all;
    else t[x].sum=t[ls(x)].sum+t[rs(x)].sum;
}
int solve(int nn){
    xx[0]=yy[0]=0;int mm;int res=0;
    for(int i=1;i<=nn;i++){
//        cin>>a[i].x>>a[i].y>>a[i].X>>a[i].Y;
        xx[++xx[0]]=a[i].x;xx[++xx[0]]=a[i].X;
        yy[++yy[0]]=a[i].y;yy[++yy[0]]=a[i].Y;
    }
    sort(xx+1,xx+xx[0]+1);sort(yy+1,yy+yy[0]+1);
    xx[0]=unique(xx+1,xx+xx[0]+1)-xx-1;yy[0]=unique(yy+1,yy+yy[0]+1)-yy-1;
    mm=2*nn;
    for(int i=1;i<=nn;i++){
        a[i].x=lower_bound(xx+1,xx+xx[0]+1,a[i].x)-xx;
        a[i].y=lower_bound(yy+1,yy+yy[0]+1,a[i].y)-yy;
        a[i].X=lower_bound(xx+1,xx+xx[0]+1,a[i].X)-xx;
        a[i].Y=lower_bound(yy+1,yy+yy[0]+1,a[i].Y)-yy;
        li[i*2-1]=line{a[i].y,a[i].x,a[i].X,1};
        li[i*2]=line{a[i].Y,a[i].x,a[i].X,-1};
    }
    sort(li+1,li+mm+1,cmp);
    build(1,1,xx[0]-1);
    add(1,li[1].x,li[1].X-1,1);
    for(int i=2;i<=mm;i++){
        res+=(yy[li[i].y]-yy[li[i-1].y])*t[1].sum;
        add(1,li[i].x,li[i].X-1,li[i].flag);
    }
    return res;
}
int res=0;
struct in{
    int x,y;
}In[N];
bool ED;
signed main(){
//  cerr<<(&ED-&ST)/1048576.0<<'\n';
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int X,Y;
    cin>>n>>m>>X>>Y;
    for(int i=1;i<=n;i++){
        cin>>In[i].x>>In[i].y;
        a[i+m].X=a[i+m].x=In[i].x;
        a[i+m].Y=a[i+m].y=In[i].y;
        a[i+m].X++,a[i+m].Y++;
    }
    for(int i=1;i<=m;i++){
        char c;int w;
        cin>>c>>w;
        if(c=='U') {
            a[i].x=a[i].X=X;
            a[i].y=Y,a[i].Y=Y+w;
            Y+=w;
        }
        if(c=='D') {
            a[i].x=a[i].X=X;
            a[i].y=Y-w,a[i].Y=Y;
            Y-=w;
        }
        if(c=='L') {
            a[i].x=X-w,a[i].X=X;
            a[i].y=a[i].Y=Y;
            X-=w;
        }
        if(c=='R') {
            a[i].x=X,a[i].X=X+w;
            a[i].y=a[i].Y=Y;
            X+=w;
        }
        a[i].X++,a[i].Y++;
        b[i]=a[i];
    }
//  cout<<solve(m)<<'\n';
    int rres=n+solve(m);
    for(int i=1;i<=m;i++) a[i]=b[i];
//  cout<<rres<<'\n';
    rres-=solve(n+m);
//    ;
    cout<<X<<' '<<Y<<' '<<rres;
    return 0;
}