首页 > 程序开发 > 软件开发 > 其他 >

矩阵乘法-二维树状数组-整体二分

2017-10-07

矩阵乘法-二维树状数组-整体二分。矩阵乘法:Description:给你一个N*N的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第K小数。  

矩阵乘法

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。


很想问出题人题目的名字是什么情况……
完全和题目内容无关的名字啊……
其实咱是来学二维树状数组的……


思路:
第一眼CDQ……
然后发现好像不太会写……
那就整体二分吧。

那么考虑把输入的每个点按值排序,整体二分答案的值。
每次二分时,维护一个二维树状数组,将值小于当前二分值的点加入树状数组。
那么对于每个询问,以树状数组的查询结果是否大于k作为判断依据即可~

#include
#include
#include
#include
#include

using namespace std;

typedef long long ll;
const int N=509;
const int M=60009;

inline int read()
{
    int x=0;char ch=getchar();
    while(ch<&#39;0&#39; || &#39;9&#39;>1;
    if(st>ed)return;

    if(l==r)
    {
        for(int i=st;i<=ed;i++)
            ans[q[i].id]=mid;
        return;
    }

    while(curmid)
        add(g[cur].x,g[cur].y,-1),cur--;

    int ltp=st-1,rtp=ed+1;
    for(int i=st;i<=ed;i++)
    {
        int val=query(q[i].x2,q[i].y2)-query(q[i].x2,q[i].y1-1)-query(q[i].x1-1,q[i].y2)+query(q[i].x1-1,q[i].y1-1);
        if(q[i].k<=val)
            tq[++ltp]=q[i];
        else
            tq[--rtp]=q[i];
    }

    for(int i=st;i<=ed;i++)
        q[i]=tq[i];

    solve(st,ltp,l,mid);
    solve(rtp,ed,mid+1,r);
}

int main()
{
    n=read();
    m=read();

    int mval=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            g[++tot]=(node){read(),i,j};
            mval=max(mval,g[tot].val);
        }

    sort(g+1,g+tot+1);

    for(int i=1;i<=m;i++)
    {
        q[i].x1=read();
        q[i].y1=read();
        q[i].x2=read();
        q[i].y2=read();
        q[i].k=read();
        q[i].id=i;
    }

    solve(1,m,1,mval);

    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);

    return 0;
}
相关文章
最新文章
热点推荐