题目大意:给定N和M,然后N组s0, t0, Δs, Δt, k,每组能够计算出k个星星的坐标;M组a0, b0, c0, d0, Δa, Δb, Δc,
Δd, q。每组要求算出q个矩形,推断矩形内是否包括星星,对于q≥20的情况要依据公式计算一个值就可以。
解题思路:计算出全部的星星坐标和矩阵,这个每的说了,将矩阵差分成两点。通过计算出每一个点左下角有多少个星
星,然后用容斥计算出矩阵内是否有点。这个属于线段树的一个应用。
#include #include #include #include
1 : 0) * T[j]) % mod; printf("%lld", ret); } else { for (int j = 0; j < cnt[i]; j++) printf("%d", judge(que[mv + j]) > 0 ?
1 : 0); } mv += cnt[i]; printf("\n"); } } int main () { T[0] = 1; for (int i = 1; i <= 345; i++) T[i] = T[i-1] * 7 % mod; while (scanf("%d%d", &N, &M) == 2) { init(); solve(); } return 0; }