题目大意
给出一个n*n的图，有n个点，每行每列有且仅有一个点，求有多少个k*k矩形中有k个点。
解题思路
可以发现按x坐标把点排序后得出一个排列，求有多少个区间长度等于最大值减最少值。可以考虑分治，可以算出中心到左右区间的最大最小值，若最大最小值在同侧则可以枚举一端算出另一端再判断是否合法。若不同侧可以发现左最大右最小时r-l==max[l]-min[r]，即l+max[l]==r+min[r]，相互独立可以开桶判断。从中间往左枚举一端，发现满足左最大右最小的右端区间是单调的，因为最大值单调上升最小值单调下降，左端最大最小值变化，右端最小值必须更小最大值可以更大，判一下是否有答案即可。
code
#include
#include
#include
#include
#include
#define LF double
#define LL long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const maxn=50000;
int n,x[maxn+10],y[maxn+10],z[maxn+10],ans,mi[maxn+10],mx[maxn+10],cnt1[maxn*2+10],cnt2[maxn*2+10];
bool cmp(int i,int j){return x[i]void solove(int l,int r){if(l==r)return;int m=(l+r)/2;mi[m]=mx[m]=x[m];mi[m+1]=mx[m+1]=x[m+1];fd(i,m-1,l){mi[i]=min(mi[i+1],x[i]);mx[i]=max(mx[i+1],x[i]);}fo(i,m+2,r){mi[i]=min(mi[i-1],x[i]);mx[i]=max(mx[i-1],x[i]);}int l1=m+1,r1=m+1,l2=m+1,r2=m+1;cnt1[m+1-mx[m+1]+n]++;cnt2[m+1+mi[m+1]]++;fd(i,m,l){int j=i+mx[i]-mi[i];if((j>m)&&(j<=r)&&(mx[i]>mx[j])&&(mi[i]1,r){int i=j-(mx[j]-mi[j]);if((l<=i)&&(i<=m)&&(mx[i]mi[j]))ans++;}fd(i,m,l){for(;(r11]>=mi[i]);r1++,cnt1[r1-mx[r1]+n]++);for(;(l1<=r)&&(mx[l1]if(l1<=r1)ans+=cnt1[i-mi[i]+n];for(;(r21]<=mx[i]);r2++,cnt2[r2+mi[r2]]++);for(;(l2<=r)&&(mi[l2]>mi[i]);cnt2[l2+mi[l2]]--,l2++);if(l2<=r2)ans+=cnt2[i+mx[i]];}for(;r1for(;l1<=r;cnt1[l1-mx[l1]+n]--,l1++);for(;r2for(;l2<=r;cnt2[l2+mi[l2]]--,l2++);solove(l,m);solove(m+1,r);
}
int main(){freopen("d.in","r",stdin);freopen("d.out","w",stdout);scanf("%d",&n);fo(i,1,n)scanf("%d%d",&x[i],&y[i]),z[i]=i;sort(z+1,z+n+1,cmp);fo(i,1,n)x[i]=y[z[i]];solove(1,n);printf("%d",ans+n);return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
