P5103

Aryper · 2021-08-16 21:34:23 · 个人记录

[JOI 2016 Final]断层

思维题，看起来实现比较简单，但思维含量远远超过了代码的实现难度。

首先，我们注意到如果正向操作，让断层之上的板块抬升，要考虑的情况非常多。因为：第一，包括样例中都存在十字交叉等等的复杂情况，这个纵坐标首先就不好判断；第二，横坐标的位移可能导致这个序列要扩大很长，才能使最终结果中需要的板块在序列中。

于是，我们考虑倒着，让板块从上方塌陷回去。

一开始我们的结果序列就是需要求出其原本所在层数的几个板块，而且因为是塌陷，所以很多需要考虑的交叉导致纵坐标变化不规律的情况全部变成简单的加减，这个可以通过手玩看出。

然后就是一个技巧：令 x'=x-y，y'=x+y，这样做的实际效果其实是把整个图逆时针旋转 45\degree，并使得每一层都在同一条斜线上，每一条竖线和横线都对应了断层的位置。更重要的是，如果要求 x 或 y，都可以通过 x' 与 y' 简单相加减得到。

而我们需要的只有 y，而针对下沉的操作，实际上层数要取 y 的相反数。

所以：-y=-(\dfrac{y'-x'}{2})=\dfrac{x'-y'}{2}。

这样一来，原本要变换两个坐标，现在只用变换 x' 或 y' 中的一个即可。

至于怎么想到这种技巧的，还记得 八皇后 吗？

然后下面是盗图，方便理解。

至于为什么这些斜线相互之间还空着一条斜线，那是留给分数的。八皇后那里没有旋转，所以斜线是紧凑的，然而旋转之后，一些 \frac{1}{2} 倍数的点的 x' 与 y' 相加之后却是整数，但这些点在旋转之后不需要，因此会空出来。

因为旋转，下沉改为了向右或向下平移，但同时，距离也被扩大。每条斜线上相邻的点的距离变为了 \sqrt{2} 单位，那横竖平移就变成了 \sqrt{2}\times\sqrt{2}=2 单位。其实就是翻了两倍，没有什么难以处理的。

然后就是一些操作上的细节。显然这个序列需要两个，一个维护 x'，另一个维护 y'。我们可以使用线段树或差分树状数组来进行区间操作与单点查询。

接着就是找到断层的位置。

对于 D_i=1，在旋转后的图中对应一条竖直的线，断层上方下沉即竖线左边向下平移。那么我们最靠近竖线且向下平移的地层序号 pos 一定满足 x'_{pos}\le x_i。

同理对于 D_i=2，对应水平的线，满足 y'_{pos}>x_i。

至于中间为什么有取等或不取等，可以通过手玩发现。注意我们地层对应的坐标一定是右端的。

那么现在的任务就是找到断层的位置，这个可以通过二分完成。

至此，这道题就基本解决了。

然后我用的是树状数组，写的是朴素二分。所以时间复杂度是 O(q\log^2n) 的。但是因为常数小，所以跑得还是蛮快的。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=2e5;

ll n,q,pos;

ll cx[N+5],cy[N+5];

struct node{
    ll l,d,x;
}a[N+5];

void addx(ll x,ll y) {
    for(;x<=n;x+=x&-x) cx[x]+=y;
}

void addy(ll x,ll y) {
    for(;x<=n;x+=x&-x) cy[x]+=y;
}

ll askx(ll x) {
    ll res=0;
    for(;x;x-=x&-x) res+=cx[x];
    return res;
}

ll asky(ll x) {
    ll res=0;
    for(;x;x-=x&-x) res+=cy[x];
    return res;
}

ll findx(ll x) {
    ll l=1,r=n,mid;
    while(l<r) {
        mid=(l+r+1)>>1;
        if(askx(mid)<=x) l=mid;
        else r=mid-1;
    }
    return l;
}

ll findy(ll x) {
    ll l=1,r=n,mid;
    while(l<r) {
        mid=(l+r)>>1;
        if(asky(mid)>x) r=mid;
        else l=mid+1;
    }
    return l;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();q=read();

    for(ll i=1;i<=q;i++) {
        a[i].x=read();a[i].d=read();a[i].l=read();
    }

    for(ll i=1;i<=n+1;i++) {
        addx(i,1);addy(i,1);
    }

    for(ll i=q;i>=1;i--) {
    //  printf("Nxt:i=%lld d[i]=%lld\n",i,a[i].d);
        if(a[i].d==1) {
            pos=findx(a[i].x);
        //  printf("test:pos=%lld askx_pos=%lld x=%lld\n",pos,askx(pos),a[i].x);
            if(askx(pos)>a[i].x) continue;
            addy(pos+1,2*a[i].l);addy(1,-2*a[i].l);
        }
        if(a[i].d==2) {
            pos=findy(a[i].x);
        //  printf("test:pos=%lld asky_pos=%lld x=%lld\n",pos,asky(pos),a[i].x);
            if(asky(pos)<=a[i].x) continue;
            addx(pos,2*a[i].l);//addx(n+1,-2*a[i].l);
        }
    //  printf("There!\n");
    }

    for(ll i=1;i<=n;i++) {
        write((askx(i)-asky(i))/2);putchar('\n');
    }

    return 0;
}