ds

<div class="post_brief"><p> 在一道usaco的题上wa了三次。我也是厉害。</p>   其实好像有简单做法的。不过我是要脑补一下曼哈顿最小生成树。   对于一个平面图上的点的曼哈顿最小生成树，一定存在一种方案，使得每个点的度数至多为8。也就是说以斜率为0,inf,1,-1的四条直线分出来的八个区域里各有一个点就行了。然后是可以保证的。   于是就是拿俩树状数组扫四遍就行了。   #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; const int inf = 0x3f3f3f3f; struct point { int x, y, i; point() { x = -inf, y = -1; } point(int xo, int yo) { x = xo, y = yo; } inline void init(int ix) { scanf("%d%d", &x, &y); i = ix; } }; inline bool operator <(const point& a, const point& b) { return (a....

<div class="post_brief"><p> orz mhy。看mhy的刷题记录成为了我成天的刷题方向了。</p>   其实最初也没有想清楚。然后看了一眼mhy写的题解写了凸壳，秒懂。   二分一个答案，设它是ans。如果ans≥realAns的话，那么就会存在yi-ans*xi+qj-ans*pj≥0。然后i和j就分开了。于是变成了求一条路径上yi-ans*xi的最大值。把xi看作k，把yi看作b，就变成半平面交了。于是开归并式线段树把凸壳给记录下来就好了。然后复杂度大约是单次询问O(lg3(n))的？链剖后每棵树单独建树，然后复杂度我就不会算了TT。   于是就硬着头皮写了，然后发现跑得还挺快。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int maxn = 30009; const int maxl = 15; const int max_buf = maxn * maxl * 2; const double eps = 1e-6; const double finf = 1e10; int ibuf_arr[max_buf], *ibuf(ibuf_arr); double fbuf_arr[max_buf], *fbuf(fbuf_arr); struct edge { int t; edge *next; }; struct line { double k, b; inline double xCross(const line& a) { return (a....

<div class="post_brief"><p> 这么水的题居然还要写题解。要不要说我写了半个下午+半个晚上。</p>   丧心病狂想写一发zkw去抢速度rank。然后发现zkw怎么支持区间修改查询TT。课件根本没讲懂。而且max怎么区间加。   想了很久终于想出了来了。然后交上去发现常数巨大比普通线段树还要慢TT。到头来想想如果我直接写普通线段树说不定十多分钟就能过，而且代码量还会小一些。因为那个是可以直接通用的，但是这个比较麻烦。   其实写这个就题解就是想记录一下我yy出来的zkw区间修改区间查询的方法。   这道题是区间查询最大值+区间修改。如果是写一般的线段树，需要记录两个值a和v（至于为啥我用了这俩神奇的字母我也不知道），分别表示当前区间被完整覆盖的修改的最大值（又称lazy标记）和当前区间的最大值。然后所以zkw也要记这两个东西。   如果我们把zkw看作一棵树，那么每次修改和询问操作的时候都是对一些线段的a和v进行操作。（废话）   首先考虑修改。zkw经典的变为开区间取中间能处理a值的改变，但是不能处理v值的改变。因为v值改变的线段不一定会被当前区间包含。然后仔细考虑发现a值没有变但是v值变了的点只可能存在于两个端点到根的路径上。那就直接强行更新一发就好了啊。然后更新的区域就变成了一个有点像倒置漏斗的形状。   再考虑询问。a要覆盖当前区间，v要被当前区间覆盖。那不就是修改把a和v的做法反一下么。   然后好像也不是很麻烦的样子哈。   然后常数很大哈。   那还拿zkw做何用。   晕。   #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int buf_len = 4567; char buf[buf_len], *bufb(buf), *bufe(buf + 1); #define readBuf() { if (++ bufb == bufe) bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin); } #define readInt(x) { register int s(0); do { readBuf(); } while (!...

<div class="post_brief"><p> 第六百道题一定要不水！虽然离第一页还有几十道题的距离。</p>   很早之前见过的题吧。然后一直觉得特别难写所以都没写。以前写点不重复的仙人掌都觉得挺痛苦，更不要说这个了。   现在想想还行，因为我yy出了化简的方法。先搞出dfs树。然后一个顶点如果是一个环里深度最浅的，那么称它为这个环的头。可以证明一个顶点最多在一个不以它为头的环上。把这个环记下来，其它的环都从这个顶点去找边来找就行了。这样的话可以比较节省代码量，写起来也比较明了。虽然还是比mhy长。   然后因为我在最后一步dp的时候写了一个static的f数组，所以光荣了。debug了好久。晕。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, av; edge *next, *rv; }; struct ball { int l, *a, h; }; const int maxn = 50009; const int maxm = 200009; const int maxarr = 400009; int n, m, cb, fb[maxn], d[maxn]; int f[maxn], ans, fd[maxn], fe[maxn]; int stc[maxn], tst; int ibuf_arr[maxarr], *ibuf(ibuf_arr); bool vis[maxn]; edge elst[maxm], *ep(elst), *head[maxn]; ball b[maxm];...

<div class="post_brief"><p> 好吧我的本意是想学习一下dp的。然后发现了这道纠结了一年半还多的题。</p>   首先把环找出来。然后环上会长一些树。先把树的答案求了，因为它很好求。   然后考虑环，那么答案应该是随便断一条边之后答案的最小值（而不是最大值）。于是乎记录一下每个点按某个方向到起点的距离，记为d[i]。算一下每个点的树的深度，记为l[i]。于是每次要最大化l[i]+l[j]+|d[i]-d[j]|。反正是最大化所以顺序是没有关系的，但是不能自交。这是个比较容易错的地方。于是就去写个线段树来维护吧。只查询不修改让我总有能线性搞的想法，虽然没想清楚具体怎么实现。   #include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; struct edge { int t, v; edge *next; }; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 100009; edge elst[maxn << 1], *ep(elst), *head[maxn]; int n, fa[maxn], df[maxn], ol[maxn], d[maxn]; int tlp, lp[maxn << 1]; dint lv[maxn << 1], le[maxn << 1], md[maxn], ans;...

<div class="post_brief"><p> 今天考试题的弱化版。只用求LCA是谁，不用求它的深度。所以直接用线段树找下区间最值就搞定了。然后long的范围有负数坑了一发。</p>   好像在不平衡的平衡树上的题也比较热啊。而且我还做得比较少。是要补一补。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef pair <int, int> vpr; typedef pair <bool, vpr> dpr; struct seg { int l, r; dpr d; seg *ls, *rs; }; struct query { int t, a, b; }; const int maxn = 400009; int n, m, vl[maxn], tv; vpr a[maxn]; query q[maxn]; seg slst[maxn * 3], *sp(slst), *rt; inline int gpos(int x) { return lower_bound(vl, vl + tv, x) - vl; }...

<div class="post_brief"><p> usaco的银组都开始考这种题了么。其实还是挺水的，不过题号比较好。</p>   就按y排序，挨个把时间轴上的东西扔掉就完了。写离散可能还没有直接写smt快呢。   然后线段有一边要减1有点坑。   #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #define _l (long long int) struct cow { int y; int ta, tb; }; struct node { int l, r, w; node ls, rs; }; typedef pair <node, node > npr; const int maxn = 50009; inline bool operator <(const cow& a, const cow& b) { return a....

<div class="post_brief"><p> 左偏树+并查集的一眼题嘛。然后合并的时候搞忘了如果两个人已经在同一个团里要跳过，于是左偏树自交去了。</p>   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define szof(p) ((p)?(p->sz):0) struct node { int sz, vl, id; node *ls, rs; node() {} node(int v, int i) { vl = v; id = i; sz = 1; ls = rs = 0; } inline void update() { if (szof(ls) < szof(rs)) swap(ls, rs); } }; node merge(node p, node q) { if (!p) return q; else if (!...

<div class="post_brief"><p> 今天晚上的效率比白天高啊。</p>   树上莫队的另一道题。比糖果公园好写到哪里去了。   然后手写链表丑掉了导致调试半天+RE了一发。我还是太年轻了。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; typedef struct node { int t; node *next; } edge; const int maxn = 50009; const int maxm = 100009; const int maxl = 17; node nlst[maxn], *np(nlst); struct chain { int sz; node *hd, *tl; chain() { hd = tl = 0; sz = 0; } inline void clear() { hd = tl = 0; sz = 0; } inline void push(int x) { np-> t = x; np-> next = 0; if (sz) { tl-> next = np; tl = np; } else { hd = np; tl = np; } ++ np; ++ sz; } inline void merge(chain a) { if (a....

<div class="post_brief"><p> 盯idy发现的题，之前想学然后放弃了，于是今天几乎写了一天。有种紧迫感啊。然后发现好多认识的人都是最近过的。</p>   思路比较简单，树上莫队。因为要修改，所以要把块的大小变成n2/3，然后用1086的方法分块。好像也可以直接按dfs序分块。两个端点和时间为三个关键字跑莫队。复杂度可以感受一下反正我也不会证。   要注意千万要控制LCA的用量，必需只能是O(n)级别的。在爬树的时候必需O(1)。我就是在移动时间的时候不小心手贱每次用一遍LCA，然后去检查在移动端点花了好久的时间。   比较不开心的是发现mac没法改栈空间？有两个点始终暴栈。而且拿另一台电脑的openSUSE跑，结果发现它的cpu没有mac好，跑得还比mac快！我猜是操作系统在捣鬼。mac还是比较坑啊不开心。然后在bzoj上跑的时间几乎是本地的5倍也是比较厉害啊。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100009; const int maxl = 19; typedef struct node { int t; node *next; } edge; node nlst[maxn], *np(nlst); struct chain { int sz; node *hd, *tl; chain() { hd = tl = 0; sz = 0; } inline void clear() { hd = tl = 0; sz = 0; } inline void push(int x) { np-> t = x; np-> next = 0; if (sz) { tl-> next = np; tl = np; } else { hd = np; tl = np; } ++ np; ++ sz; } inline void merge(chain a) { sz += a....