首页 > 代码库 > 【bzoj4066】 简单题

【bzoj4066】 简单题

http://www.lydsy.com/JudgeOnline/problem.php?id=4066 (题目链接)

题意

  维护一个矩阵,两个操作,给某一个元素加上A,求其中一个子矩阵的元素之和。强制在线。

Solution

  KDtree,其它的就是跟平衡树的维护差不多。

  然而我现在还是TLE啊T_T,但是正确性拍过没问题,求大佬帮忙看看哪里挂了T_T

细节

  注意重新构树的时候,叶子节点的左右儿子要重新赋为0,因为最初它们的左右儿子并不是0。

代码

// bzoj4066#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<ctime>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;inline int gi() {	int x=0,f=1;char ch=getchar();	while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1;ch=getchar();}	while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}const int maxn=200010;int n,K,sz,rt;LL ans;struct KDtree {	int val,l,r,v[2],mx[2],mn[2];	LL sum;	friend bool operator < (const KDtree a,const KDtree b) {		return a.v[K]<b.v[K];	}}tr[maxn],t[maxn],S;void update(int k) {	for (int i=0;i<=1;i++) {		if (tr[k].l) {			tr[k].mn[i]=min(tr[tr[k].l].mn[i],tr[k].mn[i]);			tr[k].mx[i]=max(tr[tr[k].l].mx[i],tr[k].mx[i]);		}		if (tr[k].r) {			tr[k].mn[i]=min(tr[tr[k].r].mn[i],tr[k].mn[i]);			tr[k].mx[i]=max(tr[tr[k].r].mx[i],tr[k].mx[i]);		}	}	tr[k].sum=tr[k].val+tr[tr[k].l].sum+tr[tr[k].r].sum;}void insert(int &k,int p) {	K=p;	if (!k) {tr[k=++sz]=S;return;}	if (S.v[0]==tr[k].v[0] && S.v[1]==tr[k].v[1]) {		tr[k].val+=S.val,tr[k].sum+=S.val;		return;	}	if (S<tr[k]) insert(tr[k].l,p^1);	else insert(tr[k].r,p^1);	update(k);}bool in(int x1,int y1,int X1,int Y1,int x2,int y2,int X2,int Y2) {	return x1>=x2 && X1<=X2 && y1>=y2 && Y1<=Y2;}bool out(int x1,int y1,int X1,int Y1,int x2,int y2,int X2,int Y2) {	return X1<x2 || x1>X2 || Y1<y2 || y1>Y2;}LL query(int k,int x,int y,int X,int Y) {	if (!k) return 0;	LL tmp=0;	if (in(tr[k].mn[0],tr[k].mn[1],tr[k].mx[0],tr[k].mx[1],x,y,X,Y)) return tr[k].sum;	if (out(tr[k].mn[0],tr[k].mn[1],tr[k].mx[0],tr[k].mx[1],x,y,X,Y)) return 0;	if (in(tr[k].v[0],tr[k].v[1],tr[k].v[0],tr[k].v[1],x,y,X,Y)) tmp+=tr[k].val;	tmp+=query(tr[k].l,x,y,X,Y)+query(tr[k].r,x,y,X,Y);	return tmp;}int rebuild(int l,int r,int p) {	K=p;	int mid=(l+r)>>1;	nth_element(t+l,t+mid,t+r+1);	tr[mid]=t[mid];	tr[mid].l=l<mid ? rebuild(l,mid-1,p^1) : 0;   //如果不赋值为0的话之后查询或插入时就会RE	tr[mid].r=r>mid ? rebuild(mid+1,r,p^1) : 0;	update(mid);	return mid;}int main() {	n=gi();	ans=0;	for (int op,x1,y1,x2,y2,A,m=10000;1;) {		op=gi();if (op==3) break;		x1=gi()^ans,y1=gi()^ans;		if (op==1) {			A=gi()^ans;			S.v[0]=x1;S.v[1]=y1;S.sum=S.val=A;			S.mx[0]=S.mn[0]=x1;S.mx[1]=S.mn[1]=y1;			insert(rt,0);			if (sz==m) {				//printf("%.3lf ",(double)clock()/CLOCKS_PER_SEC);				for (int i=1;i<=m;i++) t[i]=tr[i];				rt=rebuild(1,m,0);m+=10000;				//printf("%.3lf\n",(double)clock()/CLOCKS_PER_SEC);			}		}		else {			x2=gi()^ans,y2=gi()^ans;			ans=query(rt,x1,y1,x2,y2);			printf("%lld\n",ans);		}	}	//printf("%.3lf ",(double)clock()/CLOCKS_PER_SEC);	return 0;}

 

【bzoj4066】 简单题