【Tsinsen1333】矩阵乘法 – 徐亦轲的博客

记得3.13日我曾说过

【为什么我每天光搞这些东西

让我们来回顾一下

居然今天考试就用了。。

和那道题基本一样，就是要把树状数组换成二维的

【写完了之后造了点数据测了一下发现会T。。然后各种加优化还是会T一点点。。想着估计60分了，结果向总机子还快些，1.1秒就过了。。

YJP和G10似乎都是蒯的hzwer的

然后高一好多看过我blog的人似乎都蒯了我的

~~不过我也从hzwer那里蒯了个优化过来虽然加了优化并没有变快~~

一开始自己写的，和上次那个思路一样，加了个没有询问的区间直接跳过的剪枝：

// <mat.cpp> - 03/23/16 08:21:06
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
#define lowbit(x) ((x)&(-x))
const int MAX=320001;
int n,q,tot;
struct oper{
	int x1,y1,x2,y2,k,s,got;
	bool tp;
}op[MAX],opl[MAX],opr[MAX];
int ans[MAX];
int c[550][550];
inline void add(int x,int y,int k){
	for(int X=x;X<=n;X+=lowbit(X))
		for(int Y=y;Y<=n;Y+=lowbit(Y))
			c[X][Y]+=k;
}
inline int ask(int x,int y){
	int ans=0;
	for(int X=x;X;X-=lowbit(X))
		for(int Y=y;Y;Y-=lowbit(Y))
			ans+=c[X][Y];
	return ans;
}
void divide(int top,int end,int l,int r){
	if(top>end)return;
	if(l==r){
		for(int i=top;i<=end;i++)
			if(op[i].tp)ans[op[i].s]=l;
		return;
	}
	int m=(l+r)>>1;
	int lo=0,ro=0;
	bool lc=0,rc=0;
	for(int i=top;i<=end;i++)
		if(op[i].tp){
			int tmp=ask(op[i].x2,op[i].y2)+ask(op[i].x1-1,op[i].y1-1)-ask(op[i].x1-1,op[i].y2)-ask(op[i].x2,op[i].y1-1);
			if(op[i].got+tmp>=op[i].k){opl[++lo]=op[i];lc=1;}
			else {op[i].got+=tmp;opr[++ro]=op[i];rc=1;}
		}else{
			if(op[i].k<=m){add(op[i].x1,op[i].y1,1);opl[++lo]=op[i];}
			else opr[++ro]=op[i];
		}
	for(int i=top;i<=end;i++)
		if(!op[i].tp&&op[i].k<=m)add(op[i].x1,op[i].y1,-1);
	for(int i=1;i<=lo;i++)op[top+i-1]=opl[i];
	for(int i=1;i<=ro;i++)op[top+lo+i-1]=opr[i];
	if(lc)divide(top,top+lo-1,l,m);
	if(rc)divide(top+lo,end,m+1,r);
}
int main(){
	freopen("mat.in","r",stdin);
	freopen("mat.out","w",stdout);
	n=getint(),q=getint();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			op[++tot].x1=i;op[tot].y1=j;
			op[tot].k=getint();
		}
	for(int i=1;i<=q;i++){
		op[++tot].x1=getint();op[tot].y1=getint();
		op[tot].x2=getint();op[tot].y2=getint();
		op[tot].k=getint();
		op[tot].tp=1;
		op[tot].s=i;
	}
	divide(1,tot,0,1000000000);
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
	return 0;
}

// <mat.cpp> - 03/23/16 08:21:06

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

#define lowbit(x) ((x)&(-x))

const int MAX=320001;

int n,q,tot;

struct oper{

int x1,y1,x2,y2,k,s,got;

bool tp;

}op[MAX],opl[MAX],opr[MAX];

int ans[MAX];

int c[550][550];

inline void add(int x,int y,int k){

for(int X=x;X<=n;X+=lowbit(X))

for(int Y=y;Y<=n;Y+=lowbit(Y))

c[X][Y]+=k;

}

inline int ask(int x,int y){

int ans=0;

for(int X=x;X;X-=lowbit(X))

for(int Y=y;Y;Y-=lowbit(Y))

ans+=c[X][Y];

return ans;

}

void divide(int top,int end,int l,int r){

if(top>end)return;

if(l==r){

for(int i=top;i<=end;i++)

if(op[i].tp)ans[op[i].s]=l;

return;

}

int m=(l+r)>>1;

int lo=0,ro=0;

bool lc=0,rc=0;

for(int i=top;i<=end;i++)

if(op[i].tp){

int tmp=ask(op[i].x2,op[i].y2)+ask(op[i].x1-1,op[i].y1-1)-ask(op[i].x1-1,op[i].y2)-ask(op[i].x2,op[i].y1-1);

if(op[i].got+tmp>=op[i].k){opl[++lo]=op[i];lc=1;}

else {op[i].got+=tmp;opr[++ro]=op[i];rc=1;}

}else{

if(op[i].k<=m){add(op[i].x1,op[i].y1,1);opl[++lo]=op[i];}

else opr[++ro]=op[i];

}

for(int i=top;i<=end;i++)

if(!op[i].tp&&op[i].k<=m)add(op[i].x1,op[i].y1,-1);

for(int i=1;i<=lo;i++)op[top+i-1]=opl[i];

for(int i=1;i<=ro;i++)op[top+lo+i-1]=opr[i];

if(lc)divide(top,top+lo-1,l,m);

if(rc)divide(top+lo,end,m+1,r);

}

int main(){

freopen("mat.in","r",stdin);

freopen("mat.out","w",stdout);

n=getint(),q=getint();

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++){

op[++tot].x1=i;op[tot].y1=j;

op[tot].k=getint();

}

for(int i=1;i<=q;i++){

op[++tot].x1=getint();op[tot].y1=getint();

op[tot].x2=getint();op[tot].y2=getint();

op[tot].k=getint();

op[tot].tp=1;

op[tot].s=i;

}

divide(1,tot,0,1000000000);

for(int i=1;i<=q;i++)printf("%d\n",ans[i]);

return 0;

}

然后看了看hzwer写的，是先将数列排序，然后用一个T表示[0,T]区间内的数小于等于当前m，然后每次改T的范围，不清空树状数组。（好像也差不多）（似乎还是好一些）（但是Tsinsen上测出来一样快）

// <mat.cpp> - 03/23/16 08:21:06
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
#define lowbit(x) ((x)&(-x))
const int MAX=260000;
int n,q,tot,T;
struct changes{
	int x,y,k;
	bool operator < (const changes b) const {return k<b.k;}
}cg[MAX];
struct oper{
	int x1,y1,x2,y2,k,s;
}op[MAX],opl[MAX],opr[MAX];
int ans[MAX];
int c[550][550];
inline void add(int X,int y,int k){
	for(;X<=n;X+=lowbit(X))
		for(int Y=y;Y<=n;Y+=lowbit(Y))
			c[X][Y]+=k;
}
inline int ask(int X,int y){
	int ans=0;
	for(;X;X-=lowbit(X))
		for(int Y=y;Y;Y-=lowbit(Y))
			ans+=c[X][Y];
	return ans;
}
void divide(int top,int end,int l,int r){
	if(top>end)return;
	if(l==r){
		for(int i=top;i<=end;i++)ans[op[i].s]=l;
		return;
	}
	int m=(l+r)>>1;
	while(cg[T+1].k<=m&&T<tot){add(cg[T+1].x,cg[T+1].y,1);T++;}
	while(cg[T].k>m){add(cg[T].x,cg[T].y,-1);T--;}
	int lo=0,ro=0;
	for(int i = top;i <= end;i++){
		int tmp=ask(op[i].x2,op[i].y2)+ask(op[i].x1-1,op[i].y1-1)-ask(op[i].x1-1,op[i].y2)-ask(op[i].x2,op[i].y1-1);
		if(tmp>=op[i].k)opl[++lo]=op[i];
		else opr[++ro]=op[i];
	}
	for(int i=1;i<=lo;i++)op[top+i-1]=opl[i];
	for(int i=1;i<=ro;i++)op[top+lo+i-1]=opr[i];
	if(lo)divide(top,top+lo-1,l,m);
	if(ro)divide(top+lo,end,m+1,r);
}
int main(){
	n=getint(),q=getint();
	for(int i = 1;i <= n;i++)
		for(int j=1;j<=n;j++){
			cg[++tot].x=i;cg[tot].y=j;
			cg[tot].k=getint();
		}
	sort(cg+1,cg+tot+1);
	for(int i=1;i<=q;i++){
		op[i].x1=getint();op[i].y1=getint();
		op[i].x2=getint();op[i].y2=getint();
		op[i].k=getint();
		op[i].s=i;
	}
	divide(1,q,cg[1].k,cg[tot].k);
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
	return 0;
}

// <mat.cpp> - 03/23/16 08:21:06

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

#define lowbit(x) ((x)&(-x))

const int MAX=260000;

int n,q,tot,T;

struct changes{

int x,y,k;

bool operator < (const changes b) const {return k<b.k;}

}cg[MAX];

struct oper{

int x1,y1,x2,y2,k,s;

}op[MAX],opl[MAX],opr[MAX];

int ans[MAX];

int c[550][550];

inline void add(int X,int y,int k){

for(;X<=n;X+=lowbit(X))

for(int Y=y;Y<=n;Y+=lowbit(Y))

c[X][Y]+=k;

}

inline int ask(int X,int y){

int ans=0;

for(;X;X-=lowbit(X))

for(int Y=y;Y;Y-=lowbit(Y))

ans+=c[X][Y];

return ans;

}

void divide(int top,int end,int l,int r){

if(top>end)return;

if(l==r){

for(int i=top;i<=end;i++)ans[op[i].s]=l;

return;

}

int m=(l+r)>>1;

while(cg[T+1].k<=m&&T<tot){add(cg[T+1].x,cg[T+1].y,1);T++;}

while(cg[T].k>m){add(cg[T].x,cg[T].y,-1);T--;}

int lo=0,ro=0;

for(int i = top;i <= end;i++){

int tmp=ask(op[i].x2,op[i].y2)+ask(op[i].x1-1,op[i].y1-1)-ask(op[i].x1-1,op[i].y2)-ask(op[i].x2,op[i].y1-1);

if(tmp>=op[i].k)opl[++lo]=op[i];

else opr[++ro]=op[i];

}

for(int i=1;i<=lo;i++)op[top+i-1]=opl[i];

for(int i=1;i<=ro;i++)op[top+lo+i-1]=opr[i];

if(lo)divide(top,top+lo-1,l,m);

if(ro)divide(top+lo,end,m+1,r);

}

int main(){

n=getint(),q=getint();

for(int i = 1;i <= n;i++)

for(int j=1;j<=n;j++){

cg[++tot].x=i;cg[tot].y=j;

cg[tot].k=getint();

}

sort(cg+1,cg+tot+1);

for(int i=1;i<=q;i++){

op[i].x1=getint();op[i].y1=getint();

op[i].x2=getint();op[i].y2=getint();

op[i].k=getint();

op[i].s=i;

}

divide(1,q,cg[1].k,cg[tot].k);

for(int i=1;i<=q;i++)printf("%d\n",ans[i]);

return 0;

}