比赛情况：
过程：cqf签了1001,1005，然后wmd莫队过了1010。之后我和cqf干过去了1008。后面cqf和wmd过了1009，我最后过了1006；
T1008 Maximal submatrix
题意：给定一个N*M的矩阵，求一个面积最大的子矩阵，且子矩阵每一列从上到下的数值是不下降的
idea：这题一开始想麻烦了，导致卡了比较久。我们可以转化成这个模型
这个模型只需要左右各跑一遍单调栈就行了。
我们可以以每一行作为最底下那一排，跑一遍这个模型。当然需要先预处理出每一个格子往下连续的还有几个比它大。
ACcode:
#include<bits/stdc++.h>
#define LL long long
#define N 2050
#define MIN 0xc0c0c0c0
using namespace std;
int a[2050][2050],p[2050][2050],ans = MIN,maxx = 0;
void ww()
{
ans = 0;
int n,m;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]),p[i][j]=1;
for (int i=n-1;i>=1;i--) for (int j=1;j<=m;j++) if (a[i][j]<=a[i+1][j]) p[i][j]=p[i+1][j]+1;
int h[N],l[N],r[N],q[N];
for(int z=1;z<=n;z++)
{
maxx = 0;
int tt = 0;
q[0] = 0;
p[z][0] = p[z][m+1] = -1;
for(int i=1;i<=m;i++)
{
while( p[z][i] <= p[z][ q[tt] ] ) tt--;
l[ i ] = q[tt];
q[ ++tt ] = i;
}
tt = 0;
q[0] = m+1;
for(int i=m;i>=1;i--)
{
while( p[z][i] <= p[z][ q[tt] ] ) tt--;
r[i] = q[tt];
q[ ++tt ] = i;
}
for(int i=1;i<=m;i++)
{
maxx = max( maxx , p[z][i]*( r[i]-l[i]-1 ) );
}
ans = max( maxx , ans );
}
printf("%d\n",ans);
}
int main()
{
//freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
while (t)
{
t--;
ww();
}
}
T1006 Xor sum
题意：给一个长度为n的序列，再给定一个k，求一个最短的（同样长度找最靠左的）连续的子序列，是的子序列里面的值异或起来之后大于等于k，没有输出-1。
idea：数列做前缀异或，将题面转化为找两个距离最近的数，使得他们的异或值不小于k。
枚举靠右的那个数，同时维护01字典树，字典树每个节点保存范围内最靠右的点的位置。根据k来询问对应的log个节点，从而更新答案。
效率:O(nlogn)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
#define LL long long
#define N 100100
using namespace std;
int tr[N*15][2],t,n,a[N],x,id[N*15],idx = 0,l,r,minn,k,len,b[N];
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void insert( int pp , int x )
{
int p = 0;
for(int i=30;i>=0;i--)
{
if( !tr[p][ ((x>>i) & 1 )] )
{
idx++;
tr[p][ ((x>>i) & 1 )] = idx;
}
p = tr[p][ ((x>>i) & 1 )];
}
id[ p ] = pp;
}
int search( int x )
{
int p = 0;
for(int i=30;i>=0;i--)
{
int s = ((x>>i) & 1);
if( tr[p][!s] ) p = tr[p][!s];
else p = tr[p][s];
}
return id[p];
}
void solve( )
{
memset(tr,0,sizeof(tr));
//memset(id,0,sizeof(id));
len = INF;
minn = INF;
l = -1,r = n+1;
idx = 0;
n = read();
k = read();
for(int i=1;i<=n;i++)
{
b[i] = read();
a[i] = b[i] ^ a[i-1];
}
insert( 0 , a[0] );
for(int i=1;i<=n;i++)
{
int j = search( a[i] );
int temp1 = b[i];
int temp2 = a[j] ^ a[i];
int ll = j+1,rr = i;
if( temp1>=k )
{
l = r = i;
break;
}
else if( temp2 >= k )
{
if( (rr-ll+1) < len )
{
l = ll;
r = rr;
len = r-l+1;
}
else if( (rr-ll+1) == len )
{
if( ll<l )
{
l = ll;
r = rr;
len = r-l+1;
}
}
}
insert( i , a[i] );
}
if( l==-1 )
{
printf("-1\n");
}
else printf("%d %d\n",l,r);
}
int main()
{
//freopen("in.txt","r",stdin);
cin>>t;
while( t-- )
{
solve();
}
return 0;
}
PS:比赛时评测机跑得快啊
多谢评论区两位大佬提醒，原先的代码在赛后是过不去的QWQ
稍微修改了一下数组范围，memset那部分变快了，这是上面这段代在赛后评测的结果
（而且不用快读好像还更快 ）
