首页 > 代码库 > 【分块】【链表】bzoj2738 矩阵乘法
【分块】【链表】bzoj2738 矩阵乘法
http://www.cnblogs.com/jianglangcaijin/p/3460012.html
首先将矩阵的数字排序。设置size，每次将size个数字插入。插入时，我们用h[i][j]记录该位置的数字是否已经插入；用sum[i][j]表示子矩阵(1,1)到(i,j)已经插入的数字个数总和。每次插入后，暴力扫一次询问，若查询子矩阵的数字个数大于等于K则答案就在此次插入的数字中①；然后将该询问从链表中删除。
①怎样知道是插入的哪个数字呢？暴力O(sqrt(n))地扫描当前这段区间，依次判断这个数插入时是否恰好达到k个。
复杂度真心不知道怎么分析了……跪了……
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<list> 5 using namespace std; 6 struct Ask{int x1,y1,x2,y2,k,p; 7 Ask(const int &x){scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k); p=x;}Ask(){}}; 8 list<Ask>Q; 9 typedef list<Ask>::iterator ITER;10 struct Val3{int v,x,y;}Ins[250001];11 bool operator < (const Val3 &a,const Val3 &b){return a.v<b.v;}12 int n,m,sumv[501][501],q,anss[60001];13 bool vis[501][501];14 void makeblock()15 {16 int sz=sqrt(q),sum=1; if(!sz) sz=1; 17 for(;sum*sz<q;++sum)18 {19 int l=(sum-1)*sz+1; int r=sum*sz;20 for(int i=l;i<=r;++i) vis[Ins[i].x][Ins[i].y]=1;21 for(int i=1;i<=n;++i)22 for(int j=1;j<=n;++j)23 sumv[i][j]=sumv[i-1][j]+sumv[i][j-1]-sumv[i-1][j-1]+vis[i][j];24 ITER it=Q.begin();25 while(it!=Q.end())26 {27 int hav=sumv[(*it).x2][(*it).y2]-sumv[(*it).x1-1][(*it).y2]-28 sumv[(*it).x2][(*it).y1-1]+sumv[(*it).x1-1][(*it).y1-1];29 if(hav>=(*it).k)30 {31 for(int i=r;i>=l;--i)32 if(Ins[i].x>=(*it).x1 && Ins[i].x<=(*it).x2 &&33 Ins[i].y>=(*it).y1 && Ins[i].y<=(*it).y2)34 {35 if(hav==(*it).k)36 {37 anss[(*it).p]=Ins[i].v;38 break;39 } --hav;40 }41 ITER t=it; ++it; Q.erase(t);42 }43 else ++it;44 }45 }46 int l=(sum-1)*sz+1; int r=q;47 for(int i=l;i<=r;++i) vis[Ins[i].x][Ins[i].y]=1;48 for(int i=1;i<=n;++i)49 for(int j=1;j<=n;++j)50 sumv[i][j]=sumv[i-1][j]+sumv[i][j-1]-sumv[i-1][j-1]+vis[i][j];51 ITER it=Q.begin();52 while(it!=Q.end())53 {54 int hav=sumv[(*it).x2][(*it).y2]-sumv[(*it).x1-1][(*it).y2]-55 sumv[(*it).x2][(*it).y1-1]+sumv[(*it).x1-1][(*it).y1-1];56 if(hav>=(*it).k)57 {58 for(int i=r;i>=l;--i)59 if(Ins[i].x>=(*it).x1 && Ins[i].x<=(*it).x2 &&60 Ins[i].y>=(*it).y1 && Ins[i].y<=(*it).y2)61 {62 if(hav==(*it).k)63 {64 anss[(*it).p]=Ins[i].v;65 break;66 } --hav;67 }68 ITER t=it; ++it; Q.erase(t);69 }70 else ++it;71 }72 }73 int main()74 {75 scanf("%d%d",&n,&m);76 for(int i=1;i<=n;++i)77 for(int j=1;j<=n;++j)78 {79 scanf("%d",&Ins[++q].v);80 Ins[q].x=i; Ins[q].y=j;81 }82 sort(Ins+1,Ins+q+1);83 for(int i=1;i<=m;++i) Q.push_back(Ask(i));84 makeblock();85 for(int i=1;i<=m;++i) printf("%d\n",anss[i]);86 return 0;87 }
【分块】【链表】bzoj2738 矩阵乘法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。