程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> URAL 1707. Hypnotoad&#39;s Secret（樹狀數組）

URAL 1707. Hypnotoad&#39;s Secret（樹狀數組）

編輯：C++入門知識

URAL 1707. Hypnotoad's Secret（樹狀數組）

URAL 1707. Hypnotoad's Secret

題目鏈接

題意：這題設置的惡心不能多說，構造點和矩形，大概就是問每個矩形裡面是否包含點

思路：樹狀數組，把點排序，按y軸，在按x軸，在按詢問，這樣每次遇到一個點就在相應的掃描線上加，遇到查詢就詢問出左邊到這個點位置的，就能預處理出每個點左下角包含的點的個數，然後每個矩形再利用容斥原理去搞一下即可

代碼：

#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;

const int N = 1050005;
const int M = 5005;

const ll MOD = 200904040930 + 33;

struct Point {
	int x, y;
	bool isop;
	Point() {}
	Point(int x, int y, bool isop) {
		this->x = x;
		this->y = y;
		this->isop = isop;
	}
} p[N];

bool cmp(Point a, Point b) {
	if (a.y == b.y) {
		if (a.x == b.x)
			return a.isop < b.isop;
		return a.x < b.x;
	}
	return a.y < b.y;
}

int pn;

int n, m;

struct OP {
	int a0, b0, c0, d0;
	int da, db, dc, dd;
	int q;
	void read() {
		scanf("%d%d%d%d%d%d%d%d%d", &a0, &b0, &c0, &d0, &da, &db, &dc, &dd, &q);
	}
} op[350];

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

int bit[M];

void add(int x, int v) {
	while (x <= n) {
		bit[x] += v;
		x += lowbit(x);
	}
}

int get(int x) {
	int ans = 0;
	while (x) {
		ans += bit[x];
		x -= lowbit(x);
	}
	return ans;
}

int get(int l, int r) {
	return get(r) - get(l - 1);
}

typedef pair pii;
#define MP(a,b) make_pair(a,b)

map cnt;
int save[350];
ll mi7[350];

int main() {
	mi7[0] = 1;
	for (int i = 1; i < 350; i++)
		mi7[i] = mi7[i - 1] * 7 % MOD;
	while (~scanf("%d%d", &n, &m)) {
		cnt.clear();
		pn = 0;
		memset(bit, 0, sizeof(bit));
		int s0, t0, ds, dt, k;
		while (m--) {
			scanf("%d%d%d%d%d", &s0, &t0, &ds, &dt, &k);
			for (int i = 0; i < k; i++) {
				p[pn++] = Point(s0, t0, false);
				s0 = ((s0 + ds) % n + n) % n;
				t0 = ((t0 + dt) % n + n) % n;
			}
		}
		scanf("%d", &m);
		for (int i = 0; i < m; i++) {
			op[i].read();
			int a0 = op[i].a0, b0 = op[i].b0, c0 = op[i].c0, d0 = op[i].d0;
			int da = op[i].da, db = op[i].db, dc = op[i].dc, dd = op[i].dd;
			int q = op[i].q;
			for (int j = 0; j < q; j++) {
				int a = min(a0, b0), b = max(a0, b0), c = min(c0, d0), d = max(c0, d0);
				p[pn++] = Point(a - 1, c - 1, true);
				p[pn++] = Point(b, c - 1, true);
				p[pn++] = Point(a - 1, d, true);
				p[pn++] = Point(b, d, true);
				a0 = ((a0 + da) % n + n) % n;
				b0 = ((b0 + db) % n + n) % n;
				c0 = ((c0 + dc) % n + n) % n;
				d0 = ((d0 + dd) % n + n) % n;
			}
		}
		sort(p, p + pn, cmp);
		for (int i = 0; i < pn; i++) {
			if (p[i].isop) cnt[MP(p[i].x, p[i].y)] = get(1, p[i].x + 1);
			else add(p[i].x + 1, 1);
		}
		for (int i = 0; i < m; i++) {
			int a0 = op[i].a0, b0 = op[i].b0, c0 = op[i].c0, d0 = op[i].d0;
			int da = op[i].da, db = op[i].db, dc = op[i].dc, dd = op[i].dd;
			int q = op[i].q;
			for (int j = 0; j < q; j++) {
				int a = min(a0, b0), b = max(a0, b0), c = min(c0, d0), d = max(c0, d0);
				int tmp = cnt[MP(b, d)] - cnt[MP(a - 1, d)] - cnt[MP(b, c - 1)] + cnt[MP(a - 1, c - 1)];
				if (tmp == 0) save[j] = 0;
				else save[j] = 1;
				a0 = ((a0 + da) % n + n) % n;
				b0 = ((b0 + db) % n + n) % n;
				c0 = ((c0 + dc) % n + n) % n;
				d0 = ((d0 + dd) % n + n) % n;
			}
			if (q <= 20) {
				for (int j = 0; j < q; j++)
					printf("%d", save[j]);
				printf("\n");
			} else {
				ll out = 0;
				for (int j = 0; j < q; j++)
					out = (out + mi7[j] * save[j]) % MOD;
				printf("%lld\n", out);
			}
		}
	}
	return 0;
}