矩阵乘法

Time Limit: 20 Sec Memory Limit: 256 MB

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

矩阵中数字是10^9以内的非负整数；
　20%的数据：N<=100,Q<=1000；
　　40%的数据：N<=300,Q<=10000；
　60%的数据：N<=400,Q<=30000；
　100%的数据：N<=500,Q<=60000。

Solution

由于只有询问，我们可以方便地使用整体二分来求解。

先将原矩阵以序列形式存下来，然后按照权值排序，接着我们二分序列上的位置来查询，在[l,mid]这一段序列上的点+1，然后像静态查Kth那么判断即可。（用二维树状数组加入权值）。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;

const int ONE = 505;
const int QUE = 60005;

int n,Q;
int tot;
int C[ONE][ONE];
int Ans[QUE];

struct point
{
    int x,y,val;
}a[ONE*ONE];
bool cmp(const point &a,const point &b) {return a.val < b.val;}

struct power
{
    int x1,y1,x2,y2;
    int k;
    int id;
}oper[QUE],qL[QUE],qR[QUE];

int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

namespace Bit
{
    int lowbit(int x) {return x&-x;}

    void Add(int x,int y,int z)
    {
        for(int i=x;i<=n;i+=lowbit(i))
            for(int j=y;j<=n;j+=lowbit(j))
                C[i][j] += z;
    }

    int Query(int x,int y)
    {
        int res = 0;
        for(int i=x;i>=1;i-=lowbit(i))
            for(int j=y;j>=1;j-=lowbit(j))
                res += C[i][j];
        return res;
    }

    int Getans(power a)
    {
        return Query(a.x2,a.y2) - Query(a.x1-1,a.y2) - Query(a.x2,a.y1-1) + Query(a.x1-1,a.y1-1);
    }
}

void Solve(int l,int r,int L,int R)//位置 询问
{
    if(L>R) return;
    if(l==r)
    {
        for(int i=L;i<=R;i++)
            Ans[oper[i].id] = a[l].val;
        return;
    }

    int mid=(l+r)>>1;
    for(int i=l;i<=mid;i++)
        Bit::Add(a[i].x,a[i].y,1);

    int l_num=0,r_num=0;
    for(int i=L;i<=R;i++)
    {
        int record = Bit::Getans(oper[i]);
        if(record >= oper[i].k)
            qL[++l_num] = oper[i];
        else
            oper[i].k-=record, qR[++r_num] = oper[i];
    }

    for(int i=l;i<=mid;i++)
        Bit::Add(a[i].x,a[i].y,-1);

    int t=L;
    for(int i=1;i<=l_num;i++) oper[t++] = qL[i];
    for(int i=1;i<=r_num;i++) oper[t++] = qR[i];

    Solve(l,mid,L,L+l_num-1);
    Solve(mid+1,r,L+l_num,R);
}


int main()
{
    n=get();    Q=get();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            a[++tot].val = get();
            a[tot].x = i;    a[tot].y = j;
        }
    sort(a+1,a+tot+1,cmp);

    for(int i=1;i<=Q;i++)
    {
        oper[i].x1=get();    oper[i].y1=get();    oper[i].x2=get();    oper[i].y2=get();
        oper[i].k=get();    oper[i].id=i;
    }

    Solve(1,tot,1,Q);

    for(int i=1;i<=Q;i++)
        printf("%d\n",Ans[i]);
}