BZOJ2738矩阵乘法——整体二分+二维树状数组-白红宇

BZOJ2738矩阵乘法——整体二分+二维树状数组

阅读量：6764 次

发布时间：2019-06-26

本文共 1468 字，大约阅读时间需要 4 分钟。

题目描述

给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。

输入

第一行两个数N,Q，表示矩阵大小和询问组数；

接下来N行N列一共N*N个数，表示这个矩阵；

再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。

输出

对于每组询问输出第K小的数。

样例输入

2 2

2 1

3 4

1 2 1 2 1

1 1 2 2 3

样例输出

提示

矩阵中数字是109以内的非负整数；

20%的数据：N<=100,Q<=1000；

40%的数据：N<=300,Q<=10000；

60%的数据：N<=400,Q<=30000；

100%的数据：N<=500,Q<=60000。

考虑暴力，对于每次询问二分答案，求权值$\le mid$的点的个数是否有$k$个，显然时间复杂度爆炸。

我们将所有询问一起二分，也就是整体二分。

先将每个点的权值排序，每次将权值$\le mid$的点加入到矩阵中，然后对当前要处理的所有询问进行查询。

如果查询矩形内点个数大于等于$k$那么说明这个询问的答案要在$[l,mid]$中，就将这个询问归为左区间，否则将询问的$k$减掉这次查询的结果，归为右区间。这样递归下去即可得到每个询问的答案。

至于查询矩形内点数用二维树状数组差分一下即可。

每层处理完不要忘记把树状数组清空。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define ll long longusing namespace std;int n,m;int v[510][510];struct lty{ int x,y,val;}a[250010];int cnt;int num;struct miku{ int a,b,c,d,k;}q[60010];int ans[60010];int s[60010];int ql[60010];int qr[60010];bool cmp(lty a,lty b){ return a.val
                 
                  R) { return ; } if(l==r) { for(int i=L;i<=R;i++) { ans[s[i]]=a[l].val; } return ; } int mid=(l+r)>>1; for(int i=l;i<=mid;i++) { add(a[i].x,a[i].y,1); } int sl=L,sr=R; for(int i=L;i<=R;i++) { int res=query(q[s[i]].a,q[s[i]].b,q[s[i]].c,q[s[i]].d); if(res>=q[s[i]].k) { ql[sl++]=s[i]; } else { qr[sr--]=s[i]; q[s[i]].k-=res; } } for(int i=L;i

转载于:https://www.cnblogs.com/Khada-Jhin/p/10651935.html

你可能感兴趣的文章