分治（完美子图）

•                                                                                                     完美子图

• 题目描述

• 小Q和小P 都非常喜欢做一些有趣的题目，他们经常互相出一些题目来考对方。
• 一天，小Q给小P出了这样一道题目：给出一个n*n 的网格图，在网格中放置n个点，（不会有两个点放置在同一个网格中）。如果一个m*m(1<=m<=n)的子网格图恰好包含m个点,则称这样的子网格图为完美子网格图。
• 现在小Q问小 P,对于给定的网格图存在多少个完美子网格图。小P这回被难住了，他请你来帮忙，你能帮他解决这个问题吗？

  输入格式

• 第一行，一个正整数n，表示网格图的大小以及点的数量。
• 接下来n行，每行两个整数xi,yi，表示第i个点的坐标。

  保证每一行和每一列都只有一个点。

  输出格式

  一行，完美子网格图的数量。

  样例

  样例输入

  5
  1 1
  3 2
  2 4
  5 5
  4 3
  

  样例输出

  10
  

  数据范围与提示

• 显然，分别以(2,2),(4,4)为左上,右下顶点的一个子网格图中有 个点，我们找到了一个完美子网格图，类似的完美子网格图在原图中能找出10个。
• n<=50000
• 思路：二维难以处理将其压缩成一维，将其看成一个1到n的序列，用a[x]=y表示第x行的点在第y列。给定n个数的一个排列，问这个序列中有多少个子区间的数恰好的连续的。相当于统计有多少个子区间[l,r]满足Max-Min==r-l,Max,Min分别为区间[l,r]的最大最小值。
• 运用分治思想，将区间[l,r]分成[l,mid],[mid+1,r]两部分，就会出现三种情况：完美子图全部在左边;完美子图全部在右边;完美子图一部分在左，一部分在右。
• 对于前两种情况属于递归子问题，第三种需将左右两边合并则出现四种情况：第一种:最大最小值均在左边,因为Max[i]-Min[i]==j-i,可以通过左端点i求出右端点j;第二种：最大最小值均在右边，同理用右端点j求出左端点i;第三种：最小值在左边，最大值在右边，i为左端点，j为右端点，则Max[j]-Min[i]==j-i =>Max[j]-j==Min[i]=i.;第四种：最小值在右边，最大值在左边，i为左端点，j为右端点，则Max[i]-Min[j]==j-i => Min[j]+j==Min[i]+i。
  
• 

   1 #include<cstdio>
   2 #include<algorithm>
   3 using namespace std;
   4 const int maxn=50000+10;
   5 int a[maxn],Min[maxn],Max[maxn],cnt[maxn<<1];
   6 int ans=0,n;
   7 void Divi(int l,int r){
   8      if(l==r){
   9          ans++;
  10          return;
  11      }//当只有一个点时，一定为一个完美子图，ans++
  12      int mid=(l+r)>>1;
  13      Divi(l,mid);//递归左边
  14      Divi(mid+1,r);//递归右边
  15      Min[mid]=Max[mid]=a[mid];
  16      Min[mid+1]=Max[mid+1]=a[mid+1];
  17      for(int i=mid-1;i>=l;i--){
  18          Min[i]=min(Min[i+1],a[i]);
  19          Max[i]=max(Max[i+1],a[i]);
  20      }
  21      for(int i=mid+2;i<=r;i++){
  22          Min[i]=min(Min[i-1],a[i]);
  23          Max[i]=max(Max[i-1],a[i]);
  24      }//初始化，Max，Min都是对于mid而言
  25      for(int i=mid;i>=l;i--){
  26          int j=i+Max[i]-Min[i];
  27          if(j<=r&&j>mid&&Max[j]<Max[i]&&Min[i]<Min[j]) ans++;
  28      }//最大最小值都在左端，判断时保证j在右端
  29      for(int j=mid+1;j<=r;j++){
  30          int i=j-Max[j]+Min[j];
  31         if(i>=l&&i<=mid&&Max[i]<Max[j]&&Min[i]>Min[j]) ans++;
  32      }//最大最小值都在右端，判断时i在左端
  33      int j=mid+1,k=mid+1;
  34      for(int i=mid;i>=l;i--){//左小右大
  35          while(j<=r&&Min[j]>Min[i]){//j满足左小
  36              cnt[Max[j]-j+n]++;
  37              j++;
  38          }//因为Max[j]-j可能为负数，所以加n
  39           //不改变j的值，因为第一个while中若新的i的Min[i]不变，一定会走到当前的j，若更小，一定会走到当前的j，且可能向后走
  40          while(k<j&&Max[i]>Max[k]){//若不满足右大，cnt--，因为若左大左小，前面已经计算过
  41              cnt[Max[k]-k+n]--;
  42              k++;
  43          }//不改变k的值，因为第二个while中若新的i的Max[i]不变，一定会走到当前的k，若更大，一定会走到当前的k，且可能向后走
  44          ans+=cnt[Min[i]-i+n];//因为Max[j]-j==Min[i]-i
  45      }
  46      while(k<j){
  47          cnt[Max[k]-k+n]--;
  48          k++;
  49      }//不用memset，会T掉
  50      j=mid,k=mid;
  51      for(int i=mid+1;i<=r;i++){
  52          while(j>=l&&Min[i]<Min[j]){
  53              cnt[Max[j]+j]++;
  54              j--;
  55          }
  56          while(k>j&&Max[k]<Max[i]){
  57              cnt[Max[k]+k]--;
  58              k--;
  59          }
  60          ans+=cnt[Min[i]+i];
  61      }
  62      while(k>j){
  63          cnt[Max[k]+k]--;
  64          k--;
  65      }
  66 }
  67 int main(){
  68     scanf("%d",&n);
  69     for(int i=1;i<=n;i++){
  70        int x,y;
  71        scanf("%d%d",&x,&y);
  72        a[x]=y;
  73     }
  74     Divi(1,n);
  75     printf("%d",ans);
  76     return 0;
  77 }

  View Code

   

分治（完美子图）

原文：https://www.cnblogs.com/HZOIDJ123/p/13285477.html