CF869 E 二维BIT

1代表建一个屏障，2代表去掉一个屏障，3询问是否两点相通。

仿造一维询问是否在同一区间的问题扩展到二维，树状数组维护区间标记即可，标记值可以直接2500进制不会爆LL。

/** @Date    : 2017-10-09 21:03:38

  * @FileName: 869E 二维树状数组.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

LL C[2510][2510];

LL n, m, q;

void add(LL x, LL y, LL val)

{

	while(x <= n)

	{

		LL ty = y;//别直接用y阿...

		while(ty <= m)

		{

			C[x][ty] += val;

			ty += ty & (-ty);

		}

		x += x & (-x);

	}

}

void fill(LL x1, LL y1, LL x2, LL y2, LL v)

{

	add(x1, y1, v);

	add(x2 + 1, y2 + 1, v);

	add(x1, y2 + 1, -v);

	add(x2 + 1, y1, -v);

}

LL query(LL x, LL y)

{

	LL ans = 0;

	while(x > 0)

	{

		LL ty = y;

		while(ty > 0)

		{

			ans += C[x][ty];

			ty -= ty & (-ty);

		}

		x -= x & (-x);

	}

	return ans;

}

int main()

{

	MMF(C);

	cin >> n >> m >> q;

	LL t, x1, x2, y1, y2;

	for(int i = 0; i < q; i++)

	{

		scanf("%lld%lld%lld%lld%lld", &t, &x1, &y1, &x2, &y2);

		LL val = x1 + y1*2500LL + x2*2500LL*2500LL + y2*2500LL*2500LL*2500LL;

		//cout << val << endl;

		if(t <= 2)

			fill(x1, y1, x2, y2, val*(t==1?1:-1));

		else

			printf("%s\n", (query(x1, y1)==query(x2, y2)?"Yes":"No") );

	}

    return 0;

}

巴特西

CF869 E 二维BIT

最新文章

热门文章