题目链接
题意：这题设置的恶心不能多说，构造点和矩形，大概就是问每个矩形里面是否包含点
思路：树状数组，把点排序，按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; }