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。

解题思路：

整体二分思想非常浓。

将点权排序，二分mid时加入前mid个答案。

在二维树状数组上+1

最后二维树状数组查询前缀合就知道区间有多少个数。

最后统计答案就好了。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 struct data{

     int i,j;

     int val;

 }d[];

 struct que{

     int px,py,qx,qy;

     int no;

     int val;

 }q[],ss[],sp[];

 int line[][];

 int n,Q;

 int cnt;

 int top;

 int ans[];

 int lowbit(int x)

 {

     return x&(-x);

 }

 void update(int x,int y,int v)

 {

     for(int i=x;i<=n;i+=lowbit(i))

     {

         for(int j=y;j<=n;j+=lowbit(j))

         {

             line[i][j]+=v;

         }

     }

     return ;

 }

 int query(int x,int y)

 {

     int ans=;

     for(int i=x;i;i-=lowbit(i))

     {

         for(int j=y;j;j-=lowbit(j))

         {

             ans+=line[i][j];

         }

     }

     return ans;

 }

 bool cmp(data x,data y)

 {

     return x.val<y.val;

 }

 void Insert(int no,int dir)

 {

     update(d[no].i,d[no].j,dir);

     return ;

 }

 int sum(int no)

 {

     int ret=;

     ret=query(q[no].qx,q[no].qy)+query(q[no].px-,q[no].py-);

     ret-=query(q[no].qx,q[no].py-)+query(q[no].px-,q[no].qy);

     return ret;

 }

 void macrs(int l,int r,int ll,int rr)

 {

     if(ll>rr)

         return ;

     if(l==r)

     {

         for(int i=ll;i<=rr;i++)

             ans[q[i].no]=d[l].val;

         return ;

     }

     int mid=(l+r)>>;

     while(top<mid)

         Insert(++top,);

     while(top>mid)

         Insert(top--,-);

     int sta1=,sta2=;

     for(int i=ll;i<=rr;i++)

     {

         if(sum(i)>=q[i].val)

             sp[++sta1]=q[i];

         else

             ss[++sta2]=q[i];

     }

     int sta=ll-,lmid;

     for(int i=;i<=sta1;i++)

         q[++sta]=sp[i];

     lmid=sta;

     for(int i=;i<=sta2;i++)

         q[++sta]=ss[i];

     macrs(l,mid,ll,lmid);

     macrs(mid+,r,lmid+,rr);

     return ;

 }

 int main()

 {

     scanf("%d%d",&n,&Q);

     for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

         {

             int tmp;

             scanf("%d",&tmp);

             d[++cnt]=(data){i,j,tmp};

         }

     std::sort(d+,d+cnt+,cmp);

     for(int i=;i<=Q;i++)

     {

         scanf("%d%d%d%d%d",&q[i].px,&q[i].py,&q[i].qx,&q[i].qy,&q[i].val);

         if(q[i].px>q[i].qx)

             std::swap(q[i].px,q[i].qx);

         if(q[i].py>q[i].qy)

             std::swap(q[i].py,q[i].qy);

         q[i].no=i;

     }

     macrs(,cnt,,Q);

     for(int i=;i<=Q;i++)

         printf("%d\n",ans[i]);

     return ;

 }

巴特西