BZOJ 2738 矩阵乘法

Link

Solution

看道题,整体二分嘛。然后很开心地写。每次执行的值域是\([low,high]\)把矩阵中当前\(\le (low+high)/2\)的点插入BIT,查询个矩阵和就好了。 然后T飞了。。然后发现我每次将值插入BIT,是暴力遍历整个矩阵。。每次遍历都是\(O(n^2)\),而每次不管值域多小都有\(O(n^2)\),所以仅仅遍历矩阵的复杂度就是\(O(n^3)\)。。不T才怪。。 然后把所有数都提取出来排个序,每次在排序的区间内把元素插入BIT,复杂度就有保障了,但是WA?? 为什么WA??对拍之后,发现我在求子矩阵和的时候把左上角的那个矩阵加了两次。。真不知道怎么想的。。写的时候还觉得很有道理=_=。 # Code 把scanfdefine成get就是为了在卡常数的时候原地把get的实现换成fread优化就行了。。

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
120
121
122
123
124
125
126
127
//Code by Lucida
#include<bits/stdc++.h>
//#define get(x) scanf("%d",&x)
namespace IO
{
const int IN=1e7;
char inbuf[IN],*iptr=inbuf,*iend=inbuf;
#define getc() (iptr==iend && (iend=(iptr=inbuf)+fread(inbuf,1,IN,stdin),iptr==iend)?EOF:*iptr++)
inline void get(int &x)
{
static int f,ch;f=1;
while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
x=ch-'0';
while(isdigit(ch=getchar())) (x*=10)+=ch-'0';
x*=f;
}
}using namespace IO;
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=500+10,MAXQ=60000+10;
using std::copy;
using std::unique;
using std::sort;
using std::lower_bound;
struct BIT
{
int a[MAXN][MAXN],us[MAXN][MAXN],ut,n,m;
void Clear(){++ut;}
#define lowbit(x) (x & -x)
void Add(int x,int y,int v)
{
for(int i=x;i<=n;i+=lowbit(i))
{
int *pa=a[i],*pu=us[i];
for(int j=y;j<=m;j+=lowbit(j))
{
if(pu[j]!=ut) pu[j]=ut,pa[j]=0;
pa[j]+=v;
}
}
}
int Sum(int x,int y)
{
if(!x || !y) return 0;
int res=0;
for(int i=x;i;i-=lowbit(i))
{
int *pa=a[i],*pu=us[i];
for(int j=y;j;j-=lowbit(j))
{
if(pu[j]!=ut) pu[j]=ut,pa[j]=0;
res+=pa[j];
}
}
return res;
}
int Sum(int x1,int y1,int x2,int y2)
{
return Sum(x2,y2)-Sum(x1-1,y2)-Sum(x2,y1-1)+Sum(x1-1,y1-1);
}
#undef lowbit
}bit;
struct Num
{
int x,y,v;
bool operator <(const Num &a) const
{
return v<a.v;
}
}nums[MAXN*MAXN];
struct Query
{
int x1,x2,y1,y2,K,id;
}p[MAXQ],t[MAXQ];int a[MAXN][MAXN],ANS[MAXQ],n;
void DC(int low,int high,int L,int R)
{
if(low==high)
{
for(int i=L;i<=R;i++) ANS[p[i].id]=nums[low].v;
return;
}
bit.Clear();
int mid=(low+high)>>1;
for(int i=low;i<=mid;i++)
bit.Add(nums[i].x,nums[i].y,1);
int pl=L,pr=R;
for(int i=L;i<=R;i++)
{
int res=bit.Sum(p[i].x1,p[i].y1,p[i].x2,p[i].y2);
if(p[i].K<=res) t[pl++]=p[i];
else p[i].K-=res,t[pr--]=p[i];
}
copy(t+L,t+R+1,p+L);
DC(low,mid,L,pl-1);DC(mid+1,high,pr+1,R);
}
int main()
{
int Q;
get(n),get(Q);bit.n=bit.m=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
get(a[i][j]);
for(int i=1;i<=Q;i++)
{
get(p[i].x1),get(p[i].y1),get(p[i].x2),get(p[i].y2),get(p[i].K);
p[i].id=i;
}
int nc=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
nums[++nc].v=a[i][j];
nums[nc].x=i,nums[nc].y=j;
}
sort(nums+1,nums+1+nc);
DC(1,nc,1,Q);
for(int i=1;i<=Q;i++) printf("%d\n",ANS[i]);
return 0;
}
/* AC Record(Bugs) *
* TLE Naive
* WA 2DBIT
* * * * * * * * * */

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利