<span>奇袭 CodeForces 526F Pudding Monsters 题解</span>

考场上没有认真审题，没有看到该题目的特殊之处：

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

于是无论如何也想不到复杂度小于$O(n^3)$的算法，

只好打一个二维前缀和草草了事。

所以还是要仔细审题。

$O(n^2)$算法：

因为每行上只有一个军队，每列上仅有一个军队，

我们发现一个性质，如果记录上每行军队的列数，设h（x）表示第x行军队所在列，

一个$x->y$方案是合法的当且仅当$y-x=max(h(i))-min(h(i))$ $i \in [x,y]$，

枚举左右端点，记录已有的信息即可$O(1)$判断每个区间是否合法。

问题被我们转化为在一个数组a中，寻找符合$y-x=max(h(i))-min(h(i))$ $i \in [x,y]$的方案个数。

一种解决方法是分治。

在分治的过程中，答案共来自三部分，

1.方案区间不涵盖中点的，递归向下处理。

对于涵盖中点的，先预处理出从中点到l，r的最大值和最小值。

2.方案区间最大值最小值均在一侧的：

以都在左侧为例。

我们从中点扫向左侧过程中，

对于每个点，都尝试使$mx[i]-mn[i]=p-i \Leftrightarrow p=mx[i]-mn[i]+i$满足，

通过预处理的mx和mn，判断该区间是否合法即可

3.方案区间最大值最小值分在左右的：

以左侧最小值，右侧最大值为例。

设k在左侧，i在右侧

如果使一个方案成立，我们需要满足三个条件：

$mx[i]-mn[k]=k-i \Leftrightarrow mx[i]+i=mn[k]+k ---① \\ mx[i]>mx[k] ---② \\ mn[i]>mn[k]---③ $

使k从中点向左移动，我们发现决策区间的左右端点是单调的，

注意到mn和mx绝对是单调的，

mn[k]不断减小，存在右端点以右的点符合条件2，

有更多的右区间符合条件2，则我们的右端点随之可以向右运动。

mx[k]不断增大，我们要使决策区间的左端点向右，

使至少满足条件3，则我们的左端点随之向右移动。

通过1式，我们可以把等号左侧放进一个桶里，随时维护合法决策区间，不断在桶中以等号右侧寻找答案即可。

但是对于左大右小的方案，桶中存在负数域，但能保证这个负数不会小于-n，

一个很好的解决方法是将桶数组翻3倍，建立一个指针指向桶数组的第n个点，

可以直接访问指针的下标，原本的负数域被压到了正数，问题得到了解决。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int N=50010;
 5 int n,x[N],b[N*3],*bk=b+N,mx[N],mn[N];
 6 int solve(int l,int r)
 7 {
 8     if(l==r) return 1;
 9     int ans=0,mid=(l+r)>>1;
10     ans+=solve(l,mid); ans+=solve(mid+1,r);
11     mx[mid+1]=mn[mid+1]=x[mid+1]; mx[mid]=mn[mid]=x[mid];
12     for(int i=mid+2;i<=r;i++) mx[i]=max(mx[i-1],x[i]),mn[i]=min(mn[i-1],x[i]);
13     for(int i=mid-1;i>=l;i--) mx[i]=max(mx[i+1],x[i]),mn[i]=min(mn[i+1],x[i]);//pre
14     for(int i=mid;i>=l;i--)
15     {
16         int p=mx[i]-mn[i]+i;
17         if(p>mid&&p<=r&&mx[i]>mx[p]&&mn[i]<mn[p]) ans++;
18     }//最值在左
19     for(int i=mid+1;i<=r;i++)
20     {
21         int p=i-mx[i]+mn[i];
22         if(p>=l&&p<=mid&&mx[i]>mx[p]&&mn[i]<mn[p]) ans++;
23     }//最值在右
24     int i=mid+1,j=mid+1;
25     for(int k=mid;k>=l;k--)
26     {
27         while(mn[j]>mn[k]&&j<=r) bk[mx[j]-j]++,j++;
28         while(mx[i]<mx[k]&&i<j ) bk[mx[i]-i]--,i++;
29         ans+=bk[mn[k]-k];
30     }
31     while(i<j) bk[mx[i]-i]--,i++;//左小右大
32     i=mid,j=mid;
33     for(int k=mid+1;k<=r;k++)
34     {
35         while(mn[j]>mn[k]&&j>=l) bk[mx[j]+j]++,j--;
36         while(mx[i]<mx[k]&&i>j ) bk[mx[i]+i]--,i--;
37         ans+=bk[mn[k]+k];
38     }
39     while(i>j) bk[mx[i]+i]--,i--;//左大右小
40     return ans;
41 }
42 int main()
43 {
44     scanf("%d",&n);
45     for(int i=1,a,b;i<=n;++i)
46     {
47         scanf("%d%d",&a,&b);
48         x[a]=b;
49     }
50     printf("%d\n",solve(1,n));
51     return 0;
52 }