【分块】【链表】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
",anss[i]);
86     return 0;
87 }