题目大意：给定一个矩形，求一个子矩形满足权值和在[k,2k]之间
跪漆子超= =
首先考虑1*n的情况
如果存在[k,2k]之间的点，直接输出
否则如果存在一个区间满足和>=k且任意元素
这个很显然 因为区间内所有元素都
那么我们把这个结论扩展到二维 也是对的
证明：如果存在一个子矩形满足和>=k且所有元素
如果这个子矩形的和<=2k，那么满足条件直接输出
否则这个子矩形的和一定>2k
下面讨论：
如果这个子矩形只有一行，那么同上面那种情况
否则我们取这个矩阵最上方的一行和最下方的一行
易知一定存在一行的和<=整个矩形的和的一半
那么我们把这一行砍掉 由于整个矩形的和>2k 因此砍掉后矩形的和一定>k
这样无限砍下去，总有一时刻矩形的和会<=2k，此时直接输出即可
将>2k的点判断为坏点，用悬线法/单调队列搞出所有的极大子矩形，依次判断即可
时间复杂度O(n^2)
#include#include #include #include #define M 2020 using namespace std; int n,k,a[M][M]; long long sum[M][M]; long long Get_Sum(int x1,int y1,int x2,int y2) { return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]; } void Output(int x1,int y1,int x2,int y2) { while( Get_Sum(x1,y1,x2,y2)>k*2 ) { if(x1==x2) y2--; else { if( Get_Sum(x1+1,y1,x2,y2)>=k ) x1++; else x2--; } } printf("%d %d %d %d\n",y1,x1,y2,x2); exit(0); } void Monotonous_Stack(int base,int h[]) { static int stack[M],top; static int l[M],r[M]; int i; for(top=0,i=1;i<=n+1;i++) { while( top && h[stack[top]]>h[i] ) r[stack[top--]]=i-1; stack[++top]=i; } for(top=0,i=n;~i;i--) { while( top && h[stack[top]]>h[i] ) l[stack[top--]]=i+1; stack[++top]=i; } for(i=1;i<=n;i++) if(h[i]) { long long temp=Get_Sum(base-h[i]+1,l[i],base,r[i]); if( temp>=k ) Output(base-h[i]+1,l[i],base,r[i]); } } int main() { int i,j; cin>>k>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&a[i][j]); if( a[i][j]>=k && a[i][j]<=k*2 ) { printf("%d %d %d %d\n",j,i,j,i); return 0; } sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; } static int h[M]; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) h[j]=a[i][j]>k*2?0:h[j]+1; Monotonous_Stack(i,h); } puts("NIE"); return 0; }