【Codeforces 526F】Pudding Monsters | Mrsrz's blog

分治

题目大意：

给定 $n\times n$ 的网格，每行每列恰有一个棋子。

问有多少个 $k\times k$ 的子方阵，恰好包含 $k$ 个棋子。

题解：

考虑按行排好序，每行存下这个棋子的列 $a_i$。那么一个方阵包含的棋子一定是连续的一段。

而一段 $[l,r]$ 能够产生贡献，必定满足 $(\max_{i\in[l,r]} a_i)-(\min_{i\in[l,r]}a_i)=r-l$。

考虑分治，每次计算经过终点的区间。

那么有四种情况：

1. $\max$ 在左边，$\min$ 在右边。
2. $\min$ 在左边，$\max$ 在右边。
3. $\max$ 和 $\min$ 均在左边。
4. $\max$ 和 $\min$ 均在右边。

由于 $\max$ 和 $\min$ 均有单调性，因此上面四种情况都可以利用这个单调性，用桶+双指针解决。

时间复杂度 $O(n\log n)$。

Code：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=3e5+5,M=3e5;
int n,k,a[N],cnt[N*2],mx[N],mn[N];
LL ans=0;
void init(int l,int m,int r){
    mx[m]=mn[m]=a[m];
    mx[m+1]=mn[m+1]=a[m+1];
    for(int i=m-1;i>=l;--i)
        mx[i]=max(mx[i+1],a[i]),mn[i]=min(mn[i+1],a[i]);
    for(int i=m+2;i<=r;++i)
        mx[i]=max(mx[i-1],a[i]),mn[i]=min(mn[i-1],a[i]);
}
void work_(int l,int m,int r){//max--r min--l
    for(int R=m+1,h=m,t=m;R<=r;++R){
        while(t>=l&&mx[t]<mx[R])++cnt[mn[t]-t+M],--t;
        while(h>t&&mn[h]>mn[R])--cnt[mn[h]-h+M],--h;
        ans+=cnt[mx[R]-R+M];
    }
    for(int i=l;i<=m;++i)cnt[mn[i]-i+M]=0;
}
void work__(int l,int m,int r){//max--r min--r
    for(int R=m+1,it=m;R<=r;++R){
        while(it>=l&&mx[it]<mx[R]&&mn[it]>mn[R])++cnt[it+M],--it;
        ans+=cnt[R-mx[R]+mn[R]+M];
    }
    for(int i=l;i<=m;++i)cnt[i+M]=0;
}
void _work(int l,int m,int r){//max--l min--r
    for(int L=m,h=m+1,t=m+1;L>=l;--L){
        while(t<=r&&mx[t]<mx[L])++cnt[mn[t]+t],++t;
        while(h<t&&mn[h]>mn[L])--cnt[mn[h]+h],++h;
        ans+=cnt[mx[L]+L];
    }
    for(int i=m+1;i<=r;++i)cnt[mn[i]+i]=0;
}
void __work(int l,int m,int r){//max--l min--l
    for(int L=m,it=m+1;L>=l;--L){
        while(it<=r&&mx[it]<mx[L]&&mn[it]>mn[L])++cnt[it],++it;
        ans+=cnt[mx[L]-mn[L]+L];
    }
    for(int i=m+1;i<=r;++i)cnt[i]=0;
}
void solve(int l,int r){
    if(l==r)return;
    const int mid=l+r>>1;
    init(l,mid,r);
    work_(l,mid,r);
    work__(l,mid,r);
    _work(l,mid,r);
    __work(l,mid,r);
    solve(l,mid),solve(mid+1,r);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        int x;
        cin>>x;cin>>a[x];
    }
    ans=n;
    solve(1,n);
    cout<<ans<<'\n';
    return 0;
}