题目链接:ural 1707. Hypnotoad's Secret
题目大意:给定N和M,然后N组s0, t0, Δs, Δt, k,每组可以计算出k个星星的坐标;M组a0, b0, c0, d0, Δa, Δb, Δc,
Δd, q,每组要求算出q个矩形,判断矩形内是否包含星星,对于q≥20的情况要根据公式计算一个值即可。
解题思路:计算出所有的星星坐标和矩阵,这个每的说了,将矩阵差分成两点,通过计算出每个点左下角有多少个星
星,然后用容斥计算出矩阵内是否有点。这个属于线段树的一个应用。
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = L;
const int maxn = ;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << ], rc[maxn << ], s[maxn << ];
inline void pushup(int u) {
s[u] = s[lson(u)] + s[rson(u)];
}
void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
s[u] = ;
if (l == r)
return;
int mid = (l + r) / ;
build(lson(u), l, mid);
build(rson(u), mid + , r);
pushup(u);
}
void modify(int u, int x) {
if (lc[u] == x && x == rc[u]) {
s[u] += ;
return;
}
int mid = (lc[u] + rc[u]) / ;
if (x <= mid)
modify(lson(u), x);
else
modify(rson(u), x);
pushup(u);
}
int query(int u, int l, int r) {
if (l <= lc[u] && rc[u] <= r)
return s[u];
int mid = (lc[u] + rc[u]) / , ret = ;
if (l <= mid)
ret += query(lson(u), l, r);
if (r > mid)
ret += query(rson(u), l, r);
return ret;
}
struct point {
int t, x, y;
point (int x = , int y = , int t = ) {
set(x, y);
this->t = t;
}
void set (int x, int y) {
this->x = x;
this->y = y;
}
friend bool operator < (const point& a, const point& b) {
if (a.x != b.x)
return a.x < b.x;
if (a.y != b.y)
return a.y < b.y;
return a.t < b.t;
}
};
struct state {
point a, b;
state (point a, point b) {
this->a = a;
this->b = b;
}
};
int N, M, P;
ll T[];
vector<int> pos, tmp, cnt;
vector<point> vec;
vector<state> que;
map<point, int> G;
inline void add_point (ll x, ll y, int k) {
vec.push_back(point(x, y, k));
tmp.push_back(y);
}
inline void add_state (int a, int b, int c, int d) {
add_point(a - , b - , );
add_point(c, d, );
int u = vec.size();
que.push_back(state(vec[u-], vec[u-]));
add_point(a - , d, );
add_point(c, b - , );
}
inline int find (int a) {
return lower_bound(pos.begin(), pos.end(), a) - pos.begin();
}
void init () {
G.clear();
cnt.clear();
vec.clear();
que.clear();
pos.clear();
tmp.clear();
int a, b, c, d, aa, bb, cc, dd, k;
for (int i = ; i < M; i++) {
scanf("%d%d%d%d%d", &a, &b, &aa, &bb, &k);
a = (a + N) % N; b = (b + N) % N;
for (int j = ; j < k; j++) {
add_point(a, b, );
a = (a + aa + N) % N;
b = (b + bb + N) % N;
}
}
scanf("%d", &P);
for (int i = ; i < P; i++) {
scanf("%d%d%d%d", &a, &b, &c, &d);
scanf("%d%d%d%d%d", &aa, &bb, &cc, &dd, &k);
a = (a + N) % N; b = (b + N) % N;
c = (c + N) % N; d = (d + N) % N;
cnt.push_back(k);
for (int j = ; j < k; j++) {
add_state(min(a, b), min(c, d), max(a, b), max(c, d));
a = (a + aa + N) % N; b = (b + bb + N) % N;
c = (c + cc + N) % N; d = (d + dd + N) % N;
}
}
sort(vec.begin(), vec.end());
sort(tmp.begin(), tmp.end());
pos.push_back(tmp[]);
for (int i = ; i < tmp.size(); i++) {
if (tmp[i] != tmp[i-])
pos.push_back(tmp[i]);
}
build(, , pos.size());
}
inline int judge (state u) {
return G[u.b] + G[u.a] - G[point(u.b.x, u.a.y, )] - G[point(u.a.x, u.b.y, )];
}
void solve () {
for (int i = ; i < vec.size(); i++) {
if (vec[i].t)
G[vec[i]] = query(, , find(vec[i].y));
else
modify(, find(vec[i].y));
}
int mv = ;
for (int i = ; i < cnt.size(); i++) {
if (cnt[i] > ) {
ll ret = ;
for (int j = ; j < cnt[i]; j++)
ret = (ret + (judge(que[mv + j]) > ? : ) * T[j]) % mod;
printf("%lld", ret);
} else {
for (int j = ; j < cnt[i]; j++)
printf("%d", judge(que[mv + j]) > ? : );
}
mv += cnt[i];
printf("\n");
}
}
int main () {
T[] = ;
for (int i = ; i <= ; i++)
T[i] = T[i-] * % mod;
while (scanf("%d%d", &N, &M) == ) {
init();
solve();
}
return ;
}