【bzoj2738】矩阵乘法整体二分二维树状数组

【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的全部插入二维树状数组

然后查询每个矩阵内的元素个数，若数量>K-1则放左边，否则放右边

继续向下分治，左边二分l-mid，右边mid-r，当然，首先按键值排好序（是指输入的a数组），

然后下面在继续分。

 1 #include<cstring>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstdio>
 6 
 7 
 8 #define N 507
 9 #define M 60007
10 using namespace std;
11 inline int read()
12 {
13     int x=0,f=1;char ch=getchar();
14     while(ch>'9'||ch<'0'){if (ch=='-')f=-1;ch=getchar();}
15     while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 
19 int n,m,top,T;
20 int id[M],tmp[M],ans[M],tr[N][N];
21 bool mark[M];
22 struct Node1
23 {
24     int x,y,num;
25 }a[N*N];
26 struct Node2
27 {
28     int x1,x2,y1,y2,k;
29 }q[M];
30 
31 bool cmp(Node1 x,Node1 y){return x.num<y.num;}
32 inline int lowbit(int x){return x&(-x);}
33 void update(int x,int y,int num)
34 {
35     for (int i=x;i<=n;i+=lowbit(i))
36         for (int j=y;j<=n;j+=lowbit(j))
37             tr[i][j]+=num;
38 }
39 int ask(int x,int y)
40 {
41     int res=0;
42     for (int i=x;i>=1;i-=lowbit(i))
43         for (int j=y;j>=1;j-=lowbit(j))
44             res+=tr[i][j];
45     return res;            
46 }
47 int query(int k)
48 {
49     int x1=q[k].x1,x2=q[k].x2,y1=q[k].y1,y2=q[k].y2;
50     return ask(x2,y2)+ask(x1-1,y1-1)-ask(x1-1,y2)-ask(x2,y1-1);
51 }
52 void solve(int l,int r,int L,int R)
53 {
54     if (l>r||L==R) return;
55     int mid=(L+R)>>1;
56     while(a[T+1].num<=mid&&T<top)update(a[T+1].x,a[T+1].y,1),T++;
57     while(a[T].num>mid)update(a[T].x,a[T].y,-1),T--;//将比mid小或等的都放入二维树状数组中。 
58     int cnt=0;
59     for (int i=l;i<=r;i++)
60     {
61         if (query(id[i])>q[id[i]].k-1) mark[i]=1,ans[id[i]]=mid,cnt++;
62         else mark[i]=0;
63     }
64     int l1=l,l2=l+cnt;
65     for (int i=l;i<=r;i++)//若数量>K-1则放左边，否则放右边
66         if (mark[i])tmp[l1++]=id[i];
67         else tmp[l2++]=id[i];
68     for (int i=l;i<=r;i++)id[i]=tmp[i];
69     solve(l,l1-1,L,mid);solve(l1,l2-1,mid+1,R);    
70 }
71 int main()
72 {
73     n=read(),m=read();
74     int mx=0;
75     for (int i=1;i<=n;i++)
76         for (int j=1;j<=n;j++)
77         {
78             a[++top].x=i,a[top].y=j,a[top].num=read();
79             mx=max(a[top].num,mx);
80         }
81     sort(a+1,a+top+1,cmp);//按照点值大小来排序。 
82     for (int i=1;i<=m;i++)
83         q[i].x1=read(),q[i].y1=read(),q[i].x2=read(),q[i].y2=read(),q[i].k=read();
84     for (int i=1;i<=m;i++)id[i]=i;
85     solve(1,m,0,mx+1);
86     for (int i=1;i<=m;i++)
87         printf("%d
",ans[i]);        
88 }

【bzoj2738】矩阵乘法 整体二分 二维树状数组