首页 > 代码库 > 【UOJ #46】 【清华集训2014】玄学
【UOJ #46】 【清华集训2014】玄学
题目描述
巨酱有 n 副耳机，他把它们摆成了一列，并且由 1 到n依次编号。每个耳机有一个玄学值，反映了各自的一些不可名状的独特性能。玄学值都是 0 到 m-1 间的整数。在外界的作用下（包括但不限于换线、上放、更换电源为核电、让kAc叔叔给它们讲故事），这些耳机的玄学值会发生改变。特别地，巨酱观察发现，每种作用 o 对应了两个整数 ao与 bo，在这种作用之后，玄学值原本为 x 的耳机，其玄学值恰会变成 (aox+bo)modm。
巨酱对他手头耳机的表现并不满意，遗憾的是，最近他并不有钱，无法任性，不能赶紧买买买以满足自己。手头紧张的他准备拟定一个相对经济的方案，通过各种作用来改善他手头玩具的性能。具体地说，为了尽快完成方案的制订，巨酱希望自己能高效地完成以下工作：
巨酱想到了一种操作，能让耳机的玄学值由 x 变为 (ax+b)modm，并且他计划对编号为 i 到 j 的耳机执行这种操作。
巨酱想知道如果将（并且仅将）自己的第 i 个到第 j 个计划按顺序付诸行动，编号为 k 的耳机的玄学值将会变成多少。
出于著名算法竞赛选手的矜持，巨酱表示自己才不需要你的帮助。但是如果巨酱真的厌倦了自己的玩具，它们就会被50包邮出给主席。为了不让后者白白捡到便宜，你考虑再三还是决定出手。
题解
二进制分组的思想。
用线段树维护时间的操作序列，每次操作一个一个往线段树里面插，等到一个线段被插满的时候用归并来维护区间的信息。查询的时候如果一个线段没有被插满就递归下去。定位到一个区间的时候在区间里面归并出来的信息二分。
代码
1 #include <cstdio> 2 3 #define maxn 100010 4 #define maxm 600010 5 #define R register 6 int x[maxn], tnum; 7 struct Seg { 8 int l, r, a, b; 9 } p[maxn * 200];10 int lef[maxm << 2], rig[maxm << 2], pcnt, ta, tb, ql, qr, n, m, k, ans;11 void update(R int o, R int l, R int r)12 {13 lef[o] = pcnt + 1;14 for (R int i = lef[o << 1], j = lef[o << 1 | 1], head = 1; i <= rig[o << 1] || j <= rig[o << 1 | 1]; )15 if (p[i].r <= p[j].r)16 {17 p[++pcnt] = (Seg) {head, p[i].r, 1ll * p[i].a * p[j].a % m, (1ll * p[j].a * p[i].b + p[j].b) % m};18 head = p[i].r + 1;19 p[i].r == p[j].r ? ++j : 0; ++i;20 }21 else22 {23 p[++pcnt] = (Seg) {head, p[j].r, 1ll * p[i].a * p[j].a % m, (1ll * p[j].a * p[i].b + p[j].b) % m};24 head = p[j].r + 1; ++j;25 }26 rig[o] = pcnt;27 }28 int find(R int o, R int t, R int &s)29 {30 R int l = lef[o], r = rig[o];31 while (l < r)32 {33 R int mid = l + r >> 1;34 if (t <= p[mid].r) r = mid;35 else l = mid + 1;36 }37 // printf("%d %d t %d s %d %d %d\n", p[l].l, p[l].r, t, s, p[l].a, p[l].b);38 s = (1ll * s * p[l].a + p[l].b) % m;39 }40 void modify(R int o, R int l, R int r, R int t)41 {42 if (l == r)43 {44 lef[o] = pcnt + 1;45 ql > 1 ? p[++pcnt] = (Seg) {1, ql - 1, 1, 0}, 1: 0;46 p[++pcnt] = (Seg) {ql, qr, ta, tb};47 qr < n ? p[++pcnt] = (Seg) {qr + 1, n, 1, 0}, 1: 0;48 rig[o] = pcnt;49 return ;50 }51 R int mid = l + r >> 1;52 if (t <= mid) modify(o << 1, l, mid, t);53 else modify(o << 1 | 1, mid + 1, r, t);54 55 if (t == r) update(o, l, r);56 }57 void query(R int o, R int l, R int r)58 {59 if (ql <= l && r <= qr)60 {61 find(o, k, ans);62 return ;63 }64 R int mid = l + r >> 1;65 if (ql <= mid) query(o << 1, l, mid);66 if (mid < qr) query(o << 1 | 1, mid + 1, r);67 }68 int main()69 {70 R int type; scanf("%d%d%d", &type, &n, &m);71 for (R int i = 1; i <= n; ++i) scanf("%d", &x[i]);72 R int Q; scanf("%d", &Q);73 for (R int QQ = 1; QQ <= Q; ++QQ)74 {75 R int opt, l, r; scanf("%d%d%d", &opt, &l, &r);76 type & 1 ? l ^= ans, r ^= ans : 0;77 if (opt == 1)78 {79 scanf("%d%d", &ta, &tb); ++tnum; ql = l; qr = r;80 modify(1, 1, Q, tnum);81 }82 else83 {84 scanf("%d", &k); type & 1 ? k ^= ans : 0; ql = l; qr = r;85 ans = x[k];86 query(1, 1, Q);87 printf("%d\n", ans);88 }89 }90 return 0;91 }
【UOJ #46】 【清华集训2014】玄学
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。