Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes!

二维数据结构 code如下

Posted by ACAccepted at 2019-10-04 11:29:25 on Problem 1195 and last updated at 2019-10-04 11:31:17
/*
     Auther:xzy
     Time:782MS
     status:Accepted
     Submit ID:20923452
*/
//二维树状数组
#include <cstdio>
using namespace std;

template<typename T>
inline T read()
{
	T x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
	return x*f;
}

const int MAXN=10005;
int n;

namespace flat_BIT
{
	int tree[MAXN][MAXN];
	
	inline void update(int x,int y,int val)
	{
		for (int i=x;i<=n;i+=(i&-i))
			for (int j=y;j<=n;j+=(j&-j)) tree[i][j]+=val;
	}
	
	inline int query(int x,int y)
	{
		int sum=0;
		for (int i=x;i>0;i-=(i&-i))
			for (int j=y;j>0;j-=(j&-j)) sum+=tree[i][j];
		return sum;
	}
	
	inline int query(int x1,int y1,int x2,int y2)
	{
		return query(x2,y2)-query(x2,y1-1)-query(x1-1,y2)+query(x1-1,y1-1);
	}
}

int main()
{
	int cas,x,y,d,x0,y0;cas=read<int>();
	n=read<int>();
	for (cas=read<int>();cas!=3;cas=read<int>())
	{
		if (cas==1)
		{
			x=read<int>();y=read<int>();d=read<int>();
			flat_BIT::update(x+1,y+1,d);
		}
		else
		{
			x=read<int>();y=read<int>();x0=read<int>();y0=read<int>();
			printf("%d\n",flat_BIT::query(x+1,y+1,x0+1,y0+1));
		}
	}
	return 0;
}




















/*
     Auther:xzy
     Time:1422MS
     status:Accepted
     Submit ID:20923574
*/
//二维线段树
#include <cstdio>
using namespace std;

template<typename T>
inline T read()
{
	T x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
	return x*f;
}

const int MAXN=2025;
int n;

namespace flat_stree
{
	struct stree_y
	{
		int val[MAXN<<2];
		
		inline void update(int k,int l,int r,int x,int d)
		{
			if (l==r) {val[k]+=d;return ;}
			int mid=l+r>>1;
			if (x<=mid) update(k<<1,l,mid,x,d);
			else update(k<<1|1,mid+1,r,x,d);
			val[k]=val[k<<1]+val[k<<1|1];
		}
		
		inline int query(int k,int l,int r,int _l,int _r)
		{
			if (_l<=l&&_r>=r) return val[k];
			int mid=l+r>>1,res=0;
			if (_l<=mid) res+=query(k<<1,l,mid,_l,_r);
			if (_r>mid) res+=query(k<<1|1,mid+1,r,_l,_r);
			return res;
		}
	};
	
	struct stree_x
	{
		struct stree_y root[MAXN<<2];
		
		inline void update(int k,int l,int r,int x,int y,int d)
		{
			root[k].update(1,1,n,y,d);
			if (l==r) return ;
			int mid=l+r>>1;
			if (x<=mid) update(k<<1,l,mid,x,y,d);
			else update(k<<1|1,mid+1,r,x,y,d);
		}
		
		inline int query(int k,int l,int r,int _l,int _r,int __l,int __r)
		{
			if (_l<=l&&_r>=r) return root[k].query(1,1,n,__l,__r);
			int mid=l+r>>1,res=0;
			if (_l<=mid) res+=query(k<<1,l,mid,_l,_r,__l,__r);
			if (_r>mid) res+=query(k<<1|1,mid+1,r,_l,_r,__l,__r);
			return res;
		}
	}root;
}

int main()
{
	int cas,x0,y0,x,y,d;cas=read<int>();
	n=read<int>();
	for (cas=read<int>();cas!=3;cas=read<int>())
	{
		if (cas==1)
		{
			x=read<int>();y=read<int>();d=read<int>();
			flat_stree::root.update(1,1,n,x+1,y+1,d);
		}
		else 
		{
			x=read<int>();y=read<int>();x0=read<int>();y0=read<int>();
			printf("%d\n",flat_stree::root.query(1,1,n,x+1,x0+1,y+1,y0+1));
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator