CF526F Pudding Monsters

题目大意:给出一个\(n* n\)的棋盘,其中有\(n\)个格子包含棋子。

每行每列恰有一个棋子。

\(k*k\)的恰好包含\(k\)枚棋子的子矩形个数。

比较有意思的一道分治题目.

首先我们将所有棋子归位

\(sum_i\)表示第\(i\)行的棋子在第\(sum_i\)

那么\(sum\)数组就一定是一个排列

而题目就可以转化为

这个排列中有多少个区间的值域是连续的

我们考虑分治解决,每次考虑夸\(mid\)的答案个数

我们提前预处理出\(mid\)为起点的向左后缀最值和向右前缀最值

分四种情况考虑,

1:最大值和最小值都在左边

我们可以直接根据最值求出\(r\)

\(r = l+max_l-min_l\)

在判断\(r\)是否合法即可.

2:最大值和最小值都在右边

我们可以直接根据最值求出\(l\)

\(l = r - (max_r-min_i)\)

3:最大值在左边最小值在右边

\(max_i-min_j=j - i\)

化一下变成了

\(max_i+i = min_j+j\)

就开一个桶记录所有合法的\(min_j+j\)每次查询\(max_i+i\),

我们想一下,对于左边的每一个\(i\),可能课他产生贡献的都是一个右边对应的一个区间

我们就用双指针维护这个东西

注意维护的时候先动右边的指针,再跟左边的指针即可

最大值在右边,最小值在在左边

同上即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cctype>
#include<algorithm>
using namespace std;
const int N = 3e5 + 3;
struct node{
    int xi;
    int yi; 
}a[N];
int n,m;
int c[N << 1];
struct th{
    int maxx;
    int minn;   
};
th tl[N],tr[N];
int sum[N];
long long ans = 0;
inline bool cmp(node x,node y){
    return x.xi < y.xi; 
}
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar(); 
    }
    return v * c;
}
inline void solve(int l,int r){
    if(l == r) {ans++;return;}
    int mid = (l + r) >> 1;
    solve(l,mid);solve(mid + 1,r);
//  printf("%d %d\n",l,r);
    tl[mid].maxx = tl[mid].minn = a[mid].yi;
    for(int i = mid - 1;i >= l;--i){
        tl[i].maxx = max(tl[i + 1].maxx,a[i].yi);
        tl[i].minn = min(tl[i + 1].minn,a[i].yi);   
    }
    tr[mid + 1].maxx = tr[mid + 1].minn = a[mid + 1].yi;
    for(int i = mid + 2;i <= r;++i){
        tr[i].maxx = max(tr[i - 1].maxx,a[i].yi);
        tr[i].minn = min(tr[i - 1].minn,a[i].yi);   
    }
//  printf("lmin:");
//  for(int i = mid;i >= l;--i) printf("%d ",tl[i].minn);puts("");
//  printf("lmax:");
//  for(int i = mid;i >= l;--i) printf("%d ",tl[i].maxx);puts("");
//      printf("rmin:");
//  for(int i = mid + 1;i <= r;++i) printf("%d ",tr[i].minn);puts("");
//      printf("rmax:");
//  for(int i = mid + 1;i <= r;++i) printf("%d ",tr[i].maxx);puts("");
//  printf("ans0:%d\n",ans);
    for(int i = mid;i >= l;--i){
        int to = i + tl[i].maxx - tl[i].minn; 
        if(to <= mid || to > r) continue;
        if(tr[to].maxx < tl[i].maxx && tr[to].minn > tl[i].minn) ans++; 
    }
//  printf("ans1:%d\n",ans);
    for(int i = mid + 1;i <= r;++i){
        int to = i - (tr[i].maxx - tr[i].minn);
        if(to >= mid + 1 || to < l) continue;
        if(tl[to].maxx < tr[i].maxx && tr[i].minn < tl[to].minn) ans++; 
    }
//  printf("ans2:%d\n",ans);
    int ll = mid + 1,rr = mid + 1;
    for(int i = mid;i >= l;--i){
//      while(now <= r && tl[i].maxx > tr[now].maxx && tl[i].minn > tr[now].minn) {
//          c[now + tr[now].minn]++;
//          now++;
//      }
        while(rr <= r && tr[rr].maxx < tl[i].maxx) c[rr + tr[rr].minn]++,++rr;
        while(ll < rr && tr[ll].minn > tl[i].minn) c[ll + tr[ll].minn]--,++ll; 
//      if(tl[i].maxx > tr[now - 1].maxx && tl[i].minn > tr[now - 1].minn)
        ans += c[i + tl[i].maxx];
//      while(now <= r && tr[now].minn > tl[i].minn) now++;
//  while()
        
    }
//  printf("ans3:%d\n",ans);
    for(int i = ll;i < rr;++i) c[i + tr[i].minn]--;
        //for(int i = 1;i <= 10000;++i) if(c[i] != 0) cout <<"GG";
//  memset(c,0,sizeof(c));
    ll = rr = mid;
    //max in R,min in L 
    for(int i = mid + 1;i <= r;++i){
//      while(now >= l && tr[i].maxx > tl[now].maxx && tr[i].minn > tl[now].minn){
//          c[now - tl[now].minn + N]++;
//          now--;
//      //  cout << i << " " << now << endl; 
//      }
//      if(tr[i].maxx > tl[now + 1].maxx && tr[i].minn > tl[now + 1].minn)
//      ans += c[i - tr[i].maxx + N];
//      while(now >= l && tl[now].minn > tr[i].minn) now--;
        while(ll >= l && tl[ll].maxx < tr[i].maxx) c[ll - tl[ll].minn + N]++,--ll;
        while(rr > ll && tl[rr].minn > tr[i].minn) c[rr - tl[rr].minn + N]--,--rr;
        ans += c[i - tr[i].maxx + N];
    }
//  memset(c,0,sizeof(c));
    for(int i = rr;i > ll;--i) c[i - tl[i].minn + N]--; 
//  printf("ans4:%d\n",ans);
}
int main(){
    n = read();
    for(int i = 1;i <= n;++i) a[i].xi = read(),a[i].yi = read(),sum[a[i].xi] = a[i].yi;
    for(int i = 1;i <= n;++i) a[i].yi = sum[i];
//  for(int i = 1;i <= n;++i) printf("%d ",sum[i]);puts("");
    solve(1,n);
    cout << ans << endl;
    return 0;
}