ds

<div class="post_brief"><p> 难得的水水的双倍题。</p>   看上去是想考lct然后忘强制在线了么？那就直接预处理出形态然后链剖呗。当然我还没有达到mhy这种认为lct比tcd好写的水平。   中间还把修改写挂了一次，然后1180的询问数是2843的3倍又re了一次。晕。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; struct seg { int l, r, s[2]; seg *ls, *rs; }; struct query { char o; int a, b, s; }; const int maxn = 30009; const int maxm = 300009; int n, m, r[maxn], d[maxn], v[maxn], u[maxn]; int fa[maxn], sz[maxn], tc, fc[maxn], ch[maxn], cl[maxn]; int qret[2]; seg slst[maxn << 2], *sp(slst), *rt[maxn]; edge elst[maxn << 1], *ep(elst), *head[maxn]; query q[maxm];...

<div class="post_brief"><p> 去找水题于是找到这么一道恶心的代码题。其实应该可以用函数指针来优化一下代码量，不过懒得了。虽然复制粘贴导致调试了老半天。</p>   水水的链剖+线段树。然后tag打一打就好了。   最近是装备了高超的开坑技巧啊。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct seg { int l, r, s, a, b, rv; seg *ls, *rs; inline void update() { if (l + 1 < r) { s = ls-> s + rs-> s; a = min(ls-> a, rs-> a); b = max(ls-> b, rs-> b); if (rv) { s = -s; swap(a, b); a = -a; b = -b; } } else a = b = s; } inline void chgTag() { s = -s; swap(a, b); a = -a; b = -b; rv ^= 1; } inline void downTag() { if (rv) { rv = 0; if (l + 1 < r) { ls-> chgTag(); rs-> chgTag(); } } } }; struct edge { int t, v; edge *next; };...

<div class="post_brief"><p> 有离线镜像还是能省不少流量。开心。不过流量还是用得飞快啊。</p>   这就是个cdq重构的题。学习了前几天xyz大爷讲的扔线段树的做法，省了不少代码。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct node { int v, c; node *next; }; struct seg { int l, r; node *head; seg *ls, *rs; }; const int maxa = 209; const int maxn = 40009; const int maxm = 10009; const int maxnd = maxn * 23; const int mov[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};...

<div class="post_brief"><p> bc的题。今天bc又挂了。这题没有写完，然后b题fst了。伤心啊。</p>   其实思路比较简单。直接链剖dfs序上把所有区间找出来swap就好了。不过代码实现起来还是比较麻烦的，很容易绕晕。加上smt久了没写手生了，于是就调了一晚上。唉，我还是太年轻了。   #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; struct node { int v, s, sz, w, rv; node ls, rs; inline void update() { sz = 1; s = v; if (ls) { sz += ls-> sz; s += ls-> s; } if (rs) { sz += rs-> sz; s += rs-> s; } } inline void fix() { if (rv) { swap(ls, rs); if (ls) ls-> rv ^= 1; if (rs) rs-> rv ^= 1; rv = 0; } } }; typedef pair <node, node> npr;...

想起去年在考场上完全没有思路不想写数据结构于是骗了30分。现在想想当初还是naive。   这题看上去就是点分治。因为要动态加点所以要动态。然后利用替罪羊树的方法重构树上的一团东西（不能叫团，否则命名重复了）。   本来以为要写很久，结果也没写多久。奇怪的是，把maintain展开到insert里面之后就跑得飞快了，否则过不到而且根本跑不下来9和10。又丑了郁闷。   #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int buf_len = 4000; const size_t buf_size = buf_len * sizeof(char); char buf[buf_len], *bufb(buf), *bufe(buf + 1); #define readBuf() { if (++ bufb == bufe) bufe = (bufb = buf) + fread(buf, 1, buf_size, stdin); } #define readInt(x) { register int s(0); do { readBuf(); } while (!isdigit(*bufb)); do { s = s * 10 + *bufb - 48; readBuf(); } while (isdigit(*bufb)); x = s; }...

<div class="post_brief"><p> 老久之前就看到过的题，不过不会做。今天晚上也是花了差不多俩小时才调过，虽然大概一个半小时都在纠结二分怎么写的问题。我没救了。</p>   考虑经典的中位数二分，是把≤x的数字取-1，>x的数取1，然后算最大子串看是否大于-1或1中的某一个，具体要看题目要求偶数是取上整还是下整什么的。   然后这题就把所有东西排序之后拿可持久化线段树把这个序列搞出来，然后照着之前的思路二分就好了。线段树用来维护最大和最小前缀和。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct dat { int sm, s; }; struct seg { int l, r; dat v[2]; seg *ls, *rs; }; #define _l (long long int) typedef pair <int, int> vpr; typedef dat(*dat_mf)(const dat&, const dat&); const int maxn = 20009; const int maxnd = maxn * 19; const dat null_str = {0, 0}; const dat neg_str0 = {-1, -1}; const dat neg_str1 = {-1, -1}; const dat pos_str0 = {1, 1}; const dat pos_str1 = {1, 1};...

<div class="post_brief"><p> ioi的数据结构题，果然还是比较BT的。</p>   做法是对颜色分开，大的颜色预处理，小的颜色直接暴力。   然后一个小错又坑了好久。我真的没救了。 #include <cstdio> #include <cstdlib> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int buf_len = 4000; const size_t buf_size = buf_len * sizeof(char); char buf[buf_len], *bufb(buf), *bufe(buf + 1); #define readBuf() { if (++ bufb == bufe) bufe = (bufb = buf) + fread(buf, 1, buf_size, stdin); } #define readInt(x) { register int s(0); do { readBuf(); } while (!isdigit(*bufb)); do { s = s * 10 + *bufb - 48; readBuf(); } while (isdigit(*bufb)); x = s; }...

<div class="post_brief"><p> 听说是水水的splay，果然是。</p>   乍一看要用lct，然后因为度数只有2，所以肯定是一条链。然后就直接用splay来维护。然后因为少写了句splay(v)导致多调了至少一节课的时间。我没救了。 #include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; #define upmax(a,b) { if (a < b) a = b; } struct splay_node { int vl, vm, rv; splay_node *pt, *ls, *rs; inline void update() { vm = vl; if (ls) upmax(vm, ls-> vm); if (rs) upmax(vm, rs-> vm); } inline void fix() { if (rv) { swap(ls, rs); if (ls) ls-> rv ^= 1; if (rs) rs-> rv ^= 1; rv = 0; } } };...

<div class="post_brief"><p> 灭绝树的模板题么。之前不知道这题，差点当原创题出出去了。</p>   好像有不少人不知道这东西的样子？orz zhx。   灭绝树只有一句口诀：一个东西的父亲是所有入边的另一端的点的LCA。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; const int maxn = 70009; const int maxl = 19; const int maxe = 2000009; int n, ind[maxn], oud[maxn], tpo[maxn], ath[maxn][maxl], sz[maxn], d[maxn]; edge *ha[maxn], *hr[maxn], *ht[maxn]; inline void addEdge(edge** head, int u, int v) { edge* ep = new edge; ep-> t = v; ep-> next = head[u]; head[u] = ep; }...

<div class="post_brief"><p> 原来在win下也有敲回车的bug。开心。</p>   这题坑啊。暴力还是很好想的，如果个数超过几十个的话就肯定有解了。比较坑的是两边之和大于第三边，边权231-1然后加起来就超过int的范围了。连WA若干次再见。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; const int maxn = 100009; const int maxc = 88; int n, m, v[maxn], d[maxn], fa[maxn], c[maxc]; edge *head[maxn], elst[maxn << 1], *ep(elst); void bfs() { static int q[maxn]; int hd(0), tl(1); q[0] = 1; memset(d, 0, sizeof(d)); d[1] = 1; while (hd < tl) { int p(q[hd ++]); for (edge* e = head[p]; e; e = e-> next) if (!...