[JZOJ4687]奇袭

[JZOJ4687]奇袭

题目

由于各种原因，桐人现在被困在Under World（以下简称UW）中，而UW马上要迎来最终的压力测试——魔界入侵。 
唯一一个神一般存在的Administrator被消灭了，靠原本的整合骑士的力量是远远不够的。所以爱丽丝动员了UW全体人民，与整合骑士一起抗击魔族。 
在UW的驻地可以隐约看见魔族军队的大本营。整合骑士们打算在魔族入侵前发动一次奇袭，袭击魔族大本营！ 
为了降低风险，爱丽丝找到了你，一名优秀斥候，希望你能在奇袭前对魔族大本营进行侦查，并计算出袭击的难度。 
经过侦查，你绘制出了魔族大本营的地图，然后发现，魔族大本营是一个N×N的网格图，一共有N支军队驻扎在一些网格中（不会有两只军队驻扎在一起）。 
在大本营中，每有一个k×k(1≤k≤N)的子网格图包含恰好k支军队，我们袭击的难度就会增加1点。 
现在请你根据绘制出的地图，告诉爱丽丝这次的袭击行动难度有多大。 
输入保证每一行和每一列都恰有一只军队。

INPUT

第一行，一个正整数N，表示网格图的大小以及军队数量。 

接下来N行，每行两个整数,Xi,Yi，表示第i支军队的坐标。

保证每一行和每一列都恰有一只军队,即每一个Xi和每一个Yi都是不一样 的。

OUTPUT

一行，一个整数表示袭击的难度。

SAMPLE

INPUT

5

1 1

3 2

2 4

5 5

4 3

OUTPUT

10

解题报告

考试打了一个二维树状数组= =

正解：

我们考虑：

保证每一行和每一列都恰有一只军队,即每一个$X_{i}$和每一个$Y_{i}$都是不一样的。

这是这道题的关键，既然每一个$X_{i}$与每一个$Y_{i}$都是不一样的，那么我们就想，我们是否可以把二维压成一维？

自然可以。

以横坐标为下标，纵坐标为关键字，我们实际上就得到了一个$1$到$n$的排列

那么要求的值就转化为：

在区间$[L,R]$中，满足$max(L,R)-min(L,R)==R-L$的区间的个数

想想为什么？

我们要求的是在$k imes k$的矩阵中，恰有$k$个军队的矩阵数目

我们假设我们取的子网格图为以$(a,b)$为左上顶点的$k imes k$子网格，这$k$个军队所在坐标为$(x_{i},y_{i})$那么显然，在这第$a$行到第$a+k-1$行中，每一行的军队都应在$[b,b+k-1]$的区间中

即：

$$max(y_{i})=b+k-1,min(y_{i})=b$$

当我们将其压成一维后，自然就得到了上面的结论

重点在于如何处理这个值

我们考虑分治，就得到$ans[L,R]=ans[L,MID]+ans[MID+1]+ans[...]$

其中，$ans[...]$代表跨越$MID$的区间的答案

我们完全可以处理出每个位置到$MID$的最大值及最小值，那么就可以应用上述的式子了

对于跨越中间的区间的答案，我们可以看作两种情况：

1. 最值在$MID$同侧
2. 最值在$MID$异侧

其中，左右颠倒的情况基本是互相对称的，所以我们只详细讨论其中两种

当最值同在左侧时：

我们枚举一个$l$作为区间左端点，由上述式子可推知：$r=l+max(l,mid)-mid(l,mid)$（移项就出来了）

然后就可以判断该右端点的合法性

首先，当$r<=mid$时，该$r$不合法，因为该区间就没有跨越$MID$，并不属于讨论的大前提

然后，我们已经确定了此时的$max$与$min$，所以我们还需判断该$r$是否对其产生影响

即：

$$max(MID+1,r)<max(l,MID)$$

$$min(MID+1,r)>min(l,MID)$$

最值同在右侧：

对称一下

枚举右端点，算左端点，判断是否合法

最小值在左侧，最大值在右侧：

枚举左端点$l$，显然，$max(MID+1,i)(i>MID)$随着$i$增大是单调不下降的（因为新加入的值只可能在比当前$max$大时才会更新该值，否则该值不变，故单调不下降）

同理，$min(MID+1,i)(i>MID)$单调不上升

我们可以建两个指针$r1,r2$，用$r1$与$r2$中间所有点为合法右端点

我们令$r2$满足$min(MID+1,r2)>min(l,MID)$，以满足$min$在左侧

再令$r1$满足$max(MID+1,r1-1)<max(l,MID)$，以使$[MID+1,r1-1]$为不合法的右端点区间

这样就可以保证$[r1,r2]$为合法右端点的区间

剩下的就是统计个数了

还是上面的式子：$max(l,r)-min(l,r)=r-l$

移项：$max(l,r)-r=min(l,r)-l$

即：$max(MID+1,r)-r=min(l,MID)-l$

我们可以用桶来实现，对于$r2$，我们把$max(MID+1,r2)-r2$扔进桶里，对于移动前的$r1$，我们把$max(MID+1,r1)-r1$从桶里扔出来

注意桶的清空以及保证$r1<=r2$

最大值在左侧，最小值在右侧：

对称一下

枚举右端点

读者可以自行移项推一下这种情况的式子（反正底下代码里也有）

这样就可以在$O(nlog_{2}n)$的时间复杂度内解决问题了

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
    return sum;
}
const int N(50005);
const int ADD=N<<1;
typedef long long L;
int n;
int a[N];
int mxl[N],mxr[N],mnl[N],mnr[N];
L tong[ADD<<1];
inline L cal(int l,int r){
    if(l==r)
        return 1;
    int mid((l+r)>>1);
    L ret(0);
    mxl[mid]=mnl[mid]=a[mid];
    mxr[mid+1]=mnr[mid+1]=a[mid+1];
    for(int i=mid-1;i>=l;--i)
        mxl[i]=max(mxl[i+1],a[i]),mnl[i]=min(mnl[i+1],a[i]);
    for(int i=mid+2;i<=r;++i)
        mxr[i]=max(mxr[i-1],a[i]),mnr[i]=min(mnr[i-1],a[i]);
    for(int i=mid;i>=l;--i){
        int pos(mxl[i]-mnl[i]+i);
        if(pos<=mid||pos>r)
            continue;
        if(mnr[pos]>mnl[i]&&mxr[pos]<mxl[i])
            ++ret;
    }
    for(int i=mid+1;i<=r;++i){
        int pos(mnr[i]-mxr[i]+i);
        if(pos>mid||pos<l)
            continue;
        if(mnl[pos]>mnr[i]&&mxl[pos]<mxr[i])
            ++ret;
    }
    int r1(mid+1),r2(mid);
    for(int i=mid;i>=l;--i){
        while(mnr[r2+1]>mnl[i]&&r2<r){
            ++r2;
            ++tong[mxr[r2]-r2+ADD];
        }
        while(mxl[i]>mxr[r1]){
            --tong[mxr[r1]-r1+ADD];
            ++r1;
            if(r1>r)
                break;
        }
        if(r1>r)
            break;
        if(r1<=r2)
            ret+=tong[mnl[i]-i+ADD];
    }
    for(int i=l;i<=mid;++i)
        tong[mnl[i]-i+ADD]=0;
    for(int i=mid+1;i<=r;++i)
        tong[mxr[i]-i+ADD]=0;
    int l1(mid),l2(mid+1);
    for(int i=mid+1;i<=r;++i){
        while(mnl[l2-1]>mnr[i]&&l2>l){
            --l2;
            ++tong[mxl[l2]+l2+ADD];
        }
        while(mxr[i]>mxl[l1]){
            --tong[mxl[l1]+l1+ADD];
            --l1;
            if(l1<l)
                break;
        }
        if(l1<l)
            break;
        if(l2<=l1)
            ret+=tong[mnr[i]+i+ADD];
    }
    for(int i=l;i<=mid;++i)
        tong[mxl[i]+i+ADD]=0;
    for(int i=mid+1;i<=r;++i)
        tong[mnr[i]+i+ADD]=0;
    return ret;
}
inline L ef(int l,int r){
    if(l==r)
        return 1;
    int mid((l+r)>>1);
    return cal(l,r)+ef(l,mid)+ef(mid+1,r);
}
int main(){
    n=read();
    for(int i=1;i<=n;++i){
        int x(read()),y(read());
        a[x]=y;
    }
    printf("%lld
",ef(1,n));
}

ps：注意在减的时候下标可能出负数，自行处理一下即可