博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
ural 1707. Hypnotoad's Secret(线段树)
阅读量:6407 次
发布时间:2019-06-23

本文共 3946 字,大约阅读时间需要 13 分钟。

题目大意:给定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
#include
using namespace std;typedef long long ll;const ll mod = 200904040963LL;const int maxn = 300000;#define lson(x) ((x)<<1)#define rson(x) (((x)<<1)|1)int lc[maxn << 2], rc[maxn << 2], s[maxn << 2];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] = 0; if (l == r) return; int mid = (l + r) / 2; build(lson(u), l, mid); build(rson(u), mid + 1, r); pushup(u);}void modify(int u, int x) { if (lc[u] == x && x == rc[u]) { s[u] += 1; return; } int mid = (lc[u] + rc[u]) / 2; 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]) / 2, ret = 0; 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 = 0, int y = 0, int t = 0) { 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[350];vector
pos, tmp, cnt;vector
vec;vector
que;map
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 - 1, b - 1, 1); add_point(c, d, 1); int u = vec.size(); que.push_back(state(vec[u-2], vec[u-1])); add_point(a - 1, d, 1); add_point(c, b - 1, 1);}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 = 0; 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 = 0; j < k; j++) { add_point(a, b, 0); a = (a + aa + N) % N; b = (b + bb + N) % N; } } scanf("%d", &P); for (int i = 0; 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 = 0; 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[0]); for (int i = 1; i < tmp.size(); i++) { if (tmp[i] != tmp[i-1]) pos.push_back(tmp[i]); } build(1, 0, pos.size());}inline int judge (state u) { return G[u.b] + G[u.a] - G[point(u.b.x, u.a.y, 1)] - G[point(u.a.x, u.b.y, 1)];}void solve () { for (int i = 0; i < vec.size(); i++) { if (vec[i].t) G[vec[i]] = query(1, 0, find(vec[i].y)); else modify(1, find(vec[i].y)); } int mv = 0; for (int i = 0; i < cnt.size(); i++) { if (cnt[i] > 20) { ll ret = 0; for (int j = 0; j < cnt[i]; j++) ret = (ret + (judge(que[mv + j]) > 0 ?

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; }

转载地址:http://xltea.baihongyu.com/

你可能感兴趣的文章
php中mysqli 处理查询结果集总结
查看>>
你不知道的JavaScript运算符
查看>>
小程序开发注意事项
查看>>
ECMAScript7规范中的instanceof操作符
查看>>
Hadoop HDFS原理分析
查看>>
【webpack4】基本配置和入门api
查看>>
Mac使用ssh公钥登录Linux
查看>>
【366天】跃迁之路——程序员高效学习方法论探索系列(实验阶段124-2018.02.06)...
查看>>
POJ3070-Fibonacci(矩阵快速幂)
查看>>
[vue插件]基于vue2.x的电商图片放大镜插件
查看>>
标准的组件结构
查看>>
vue——一个页面实现音乐播放器
查看>>
SVG 扬帆起航
查看>>
NET Core-学习笔记(二)
查看>>
职业生涯上的点点滴滴
查看>>
Linux下添加新硬盘,分区及挂载
查看>>
一起来将vscode变成私人定制笔记本
查看>>
Flutter 云音乐
查看>>
RecyclerView实现多type页面
查看>>
个人的web商城网站
查看>>