【学习笔记】整体二分（BZOJ2738矩阵乘法）

也是因为一道题才来学的。。。

然后就发现这道模板貌似是暑假初期在某校集训的时候的比赛题 并且好像没改= =

前置芝士

1.二分= =

* CDQ分治[你要是知道CDQ分治的话这玩意就很好理解啦]

*本题使用二维树状数组

整体二分是类似CDQ分治的一类东西

CDQ分治是计算左边对右边的贡献

整体二分是计算左边的贡献来确定答案在哪边

具体来说就是这样一个过程

[l,r,L,R] : 小写代表答案区间 大写表示询问区间

我们通过计算 l 到 mid 的答案 来确定[L,R]的询问的答案是属于[l,mid]还是[mid,r]

对于这个题就是把<=mid的值计算贡献 然后对于这些询问看是否>=k 这样就可以同时二分答案和询问从而做到均摊nlgn

代码实现并不复杂。 注意权值和询问别放反了= =

附代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 20021225
#define ll long long
#define lowbit(x) (x&(-x))
#define mxn 60010
using namespace std;struct node{int x,y,v;}t[250010];
struct query{int x1,x2,y1,y2,k;}q[mxn];
int f[510][510],n,ans[mxn],id[mxn];
int cur[mxn],cr[mxn],m,cnt=0;
int val[250010];
void modify(int x,int y,int v)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
f[i][j]+=v;
}int query(int x,int y)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
ans+=f[i][j];
return ans;
}int get(int x1,int x2,int y1,int y2)
{
//puts("");
return query(x2,y2) - query(x1-1,y2) - query(x2,y1-1) + query(x1-1,y1-1);
}int now;
void work(int l,int r,int L,int R)// [L,R] val [l,r] query
{
//printf("%d %d %d %d\n",l,r,L,R);
if(l>r)return;if(L==R)
{
for(int i=l;i<=r;i++)ans[id[i]]=val[L];
return;
}int MID = L+R>>1;
while(now<MID)now++,modify(t[now].x,t[now].y,1);
while(now>MID)modify(t[now].x,t[now].y,-1),now--;
int l1=0,l2=0,mid;
for(int i=l;i<=r;i++)
{
int x=id[i];// printf("%d\n",i);
int tmp = get(q[x].x1,q[x].x2,q[x].y1,q[x].y2);
if(tmp >= q[x].k)cur[++l1] = x;
elsecr[++l2] = x;
}mid = l+l1-1;
for(int i=1;i<=l1;i++)
id[l+i-1]=cur[i];
for(int i=1;i<=l2;i++)
id[mid+i]=cr[i];work(l,mid,L,MID); work(mid+1,r,MID+1,R);
}bool cmp(node a,node b)
{
return a.v<b.v;
}int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
t[++cnt].x=i,t[cnt].y=j,scanf("%d",&t[cnt].v);
sort(t+1,t+cnt+1,cmp);
for(int i=1;i<=cnt;i++)val[i]=t[i].v;
for(int i=1;i<=m;i++)
scanf("%d%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2,&q[i].k),id[i]=i;
work(1,m,1,cnt);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}