[BZOJ2639]矩形计算

题目大意：

给定一个\(n\times m(n,m\le200)\)的矩阵。\(q(q\le10^5)\)次询问，每次询问一个子矩阵中所有数字出现次数的平方和。

思路：

二维莫队。

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

#include<algorithm>

#define y1 f2s3D3YjsPPh2TRa4GJVf

inline int getint() {

	register char ch;

	register bool neg=false;

	while(!isdigit(ch=getchar())) neg|=ch=='-';

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return neg?-x:x;

}

const int N=201,TOT=40001,Q=1e5;

int a[N][N],tot,tmp[TOT],bel[N],block,sum,cnt[TOT];

struct Query {

	int x1,y1,x2,y2,id;

	bool operator < (const Query &rhs) const {

		if(bel[x1]!=bel[rhs.x1]) return x1<rhs.x1;

		if(bel[y1]!=bel[rhs.y1]) return y1<rhs.y1;

		if(bel[x2]!=bel[rhs.x2]) return x2<rhs.x2;

		return y2<rhs.y2;

	}

};

Query q[Q];

int ans[Q];

int x1,y1,x2,y2;

inline int sqr(const int &x) {

	return x*x;

}

inline void mdy_x(const int &x,const int &t) {

	for(register int i=y1;i<=y2;i++) {

		sum-=sqr(cnt[a[x][i]]);

		cnt[a[x][i]]+=t;

		sum+=sqr(cnt[a[x][i]]);

	}

}

inline void mdy_y(const int &y,const int &t) {

	for(register int i=x1;i<=x2;i++) {

		sum-=sqr(cnt[a[i][y]]);

		cnt[a[i][y]]+=t;

		sum+=sqr(cnt[a[i][y]]);

	}

}

int main() {

	block=12;

	const int n=getint(),m=getint();

	for(register int i=1;i<=n||i<=m;i++) {

		bel[i]=i/block;

	}

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

		for(register int j=1;j<=m;j++) {

			a[i][j]=getint();

			tmp[++tot]=a[i][j];

		}

	}

	std::sort(&tmp[1],&tmp[tot]+1);

	tot=std::unique(&tmp[1],&tmp[tot]+1)-tmp-1;

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

		for(register int j=1;j<=m;j++) {

			a[i][j]=std::lower_bound(&tmp[1],&tmp[tot]+1,a[i][j])-tmp;

		}

	}

	const int c=getint();

	for(register int i=0;i<c;i++) {

		int x1=getint(),y1=getint(),x2=getint(),y2=getint();

		if(x1>x2) std::swap(x1,x2);

		if(y1>y2) std::swap(y1,y2);

		q[i]=(Query){x1,y1,x2,y2,i};

	}

	std::sort(&q[0],&q[c]);

	x1=1,y1=1,x2=0,y2=0;

	for(register int i=0;i<c;i++) {

		while(x1>q[i].x1) mdy_x(--x1,1);

		while(x2<q[i].x2) mdy_x(++x2,1);

		while(x1<q[i].x1) mdy_x(x1++,-1);

		while(x2>q[i].x2) mdy_x(x2--,-1);

		while(y1>q[i].y1) mdy_y(--y1,1);

		while(y2<q[i].y2) mdy_y(++y2,1);

		while(y1<q[i].y1) mdy_y(y1++,-1);

		while(y2>q[i].y2) mdy_y(y2--,-1);

		ans[q[i].id]=sum;

	}

	for(register int i=0;i<c;i++) {

		printf("%d\n",ans[i]);

	}

	return 0;

}

巴特西

[BZOJ2639]矩形计算

[BZOJ2639]矩形计算

题目大意：

思路：

源代码：

最新文章

热门文章