【国家集训队2012】【BZOJ2738】矩阵乘法
Description
给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。
Input
第一行两个数N,Q，表示矩阵大小和询问组数；
接下来N行N列一共N*N个数，表示这个矩阵；
再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。
Output
对于每组询问输出第K小的数。
Sample Input
2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3
Sample Output
1
3
HINT
矩阵中数字是109以内的非负整数；
20%的数据：N<=100,Q<=1000；
40%的数据：N<=300,Q<=10000；
60%的数据：N<=400,Q<=30000；
100%的数据：N<=500,Q<=60000。
Source
【【国家集训队2012】【BZOJ2738】矩阵乘法】矩阵的整体二分
二维树状数组维护.
忘了加l>r return 不停TLE*T_T*
#include
#include
#include
#include
#include
#include
#define MAXN 60100
#define lowbit(x)(x&(-x))
using namespace std;
int n,Q,top,maxn,now;
int c[510][510];
int ans[MAXN];
void add(int x,int y,int delta)
{
for (int i=x;
i<=n;
i+=lowbit(i))
for (int j=y;
j<=n;
j+=lowbit(j)) c[i][j]+=delta;
}
int query(int x,int y)
{
int ret=0;
for (int i=x;
i;
i-=lowbit(i))
for (int j=y;
j;
j-=lowbit(j))ret+=c[i][j];
return ret;
}
void in(int &x)
{
char ch=getchar();
x=0;
int flag=1;
while (!(ch>='0'&&ch<='9')) flag=ch=='-'?-1:flag,ch=getchar();
while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
x*=flag;
}
struct Query
{
int x1,y1,x2,y2,k,id;
bool fin;
}q[MAXN],newq[MAXN];
struct operate
{
int x,y,val;
bool operator <(const operate& a)const
{
return val250010];
void solve(int l,int r,int L,int R)
{
int mid=(L+R)>>1;
if (l>r)return;
if (L==R)
{
for (int i=l;
i<=r;
i++)ans[q[i].id]=mid;
return;
}
while (now!=top&&a[now+1].val<=mid) now++,add(a[now].x,a[now].y,1);
while (a[now].val>mid&&now) add(a[now].x,a[now].y,-1),now--;
int tp1=l,tp2=r;
for (int i=l;
i<=r;
i++)
{
int temp=query(q[i].x2,q[i].y2)-query(q[i].x1-1,q[i].y2)-query(q[i].x2,q[i].y1-1)+query(q[i].x1-1,q[i].y1-1);
if (q[i].k<=temp)newq[tp1++]=q[i];
elsenewq[tp2--]=q[i];
}
memcpy(q+l,newq+l,sizeof(Query)*(r-l+1));
solve(l,tp1-1,L,mid);
solve(tp2+1,r,mid+1,R);
}
int main()
{
in(n);
in(Q);
for (int i=1;
i<=n;
i++)
for (int j=1;
j<=n;
j++)
a[++top].x=i,a[top].y=j,in(a[top].val),maxn=max(maxn,a[top].val);
sort(a+1,a+top+1);
for (int i=1;
i<=Q;
i++)in(q[i].x1),in(q[i].y1),in(q[i].x2),in(q[i].y2),in(q[i].k),q[i].id=i;
solve(1,Q,0,maxn+1);
for (int i=1;
i<=Q;
i++)printf("%d\n",ans[i]);
} 推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长