比较神奇的一道树的题。 做法是离线。想了好久的在线啊。 把询问拆成0~l-1和0~r。挨个从0开始加点。加点就是把从根到这个点的所有点权+1，询问就是询问这个点到根的点权和。好机智的做法。 代码还比较舒服。dfs+树链剖分+树状数组。 #include <cstdio> #include <memory.h> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; struct query { int p, v, n, c; inline query(int p0 = 0, int v0 = 0, int n0 = 0, int c0 = 0) { p = p0, v = v0, n = n0, c = c0; } }; const int maxn = 50009; const int mod = 201314;...
一堆标记的线段树。 翻过的，没翻过的，都分开记下来。然后还要注意flip标记与set标记的优先级关系和互相之间的影响。然后就完了。 虽说在这个颓废的下午还是花了好一会才调通。 #include <cstdio> #include <algorithm> using namespace std; struct dat { int l, r, s, t, m; }; struct seg { int l, r, f, z; dat d[2]; seg *ls, *rs; }; const int maxn = 100009; seg *rt, *sp; int n, m, a[maxn]; inline dat sgd(int v, int s = 1) { dat r; r. l = s * v; r. r = s * v; r. s = s * v;...
数据结构题总是很令人开心的。 这题据说可以主席树？好麻烦的说。 树链剖分+线段树+treap就好了吧。 #include <cstdio> #include <cstdlib> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; struct seg { int l, r, v; seg *ls, *rs; }; #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 80009; const int maxv = 1e8; namespace treap {...
啊啊看到动态树被吓尿了。 然后发现动的不是树的形态是点权。 树链剖分+dfs序么。 重点是我TLE了。 最初的写法是直接查询然后把访问过的点打个标记。一个询问做完再标记回去。然后，tle。 参考jason_yu的做法，找出所有dfs序上要询问的区间，合并之后询问，应该不会tle了吧？还是tle。 最后发现是线段树lazy标记的地方写成n^2了。开心啊。 事实证明第一种写法12秒左右，第二种写法3秒多。当然也要考虑我巨丑的常数。 所以我还是太naive了。 代码当然要粘快的。 #include <cstdio> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; struct seg { int l, r, a, v; seg *ls, *rs; }; struct rect { int l, r; inline rect(int l0 = 0, int r0 = 0) { l = l0, r = r0; } inline rect operator +(const rect& a) const {...
大概也不是很难。毕竟只有做水题的份。 就把原来的土地按x排个序，把能合并的合并，变成一个x单增y单减的序列。 然后就是dp。f[i] = min(f[j] + y[j+1]*x[i])，可以单调的斜率优化。 符号比较郁闷还搞错了好几次。 所以说我太弱了啊怎么办啊。 #include <cstdio> #include <algorithm> using namespace std; typedef long long qw; typedef long double exf; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) #define _f (exf) struct field { int x, y; }; inline bool cmpField(const field& a, const field& b) { return (a. x < b. x) || (a. x == b. x && a. y < b. y); }...
题意是严格次小生成树。 想了一下发现应该是一条不在最小生成树上的边构成的环上替换一条边就行了。感觉好想noi那道lct，哈。其实不用那么复杂的。 就用倍增就可以了。不过我还是比较倾向于用链剖。感觉链剖空间小而且写起来倍爽。不像倍增写挂了不只一次了。 要注意的是不仅要找最大值还要找严格次大值，因为要找严格次小。 #include <cstdio> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif struct edge_g { int a, b, v, mk; }; struct edge_t { int t, v; edge_t *next; }; struct dat { int a, b; dat(int v0 = -1) { a = v0, b = -1; } dat(int a0, int b0) { a = a0, b = b0;...
看上去挺水水水水水水水水的一道平衡树维护序列的数据结构题啊。 先用split-merge tree写，tle。 然后改用splay，tle。 最后据说把splay的裸数组改到struct node里就能过。于是再写了一个程序来改代码。 不 带 这 么 坑 的 ！ #include <cstdio> #include <cstdlib> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; /*#define readInt(_s_) {\ int _d_;\ bool _nag_ = 0;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()))\ if (_d_ == '-')\ _nag_ = 1;\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ if (_nag_)\ _s_ = - _s_;\ }*/ #define readInt(_s_) scanf("%d",&_s_); #define readOpt(_s_) {\ do\ _s_ = getchar();\ while (_s_ != 'I' && _s_ != 'D' && _s_ !...
考场上只想到暴力。 如果只是一条链的话怎么乱搞一搞？ 如果没有深度限制的话简单的斜率优化+链剖就行了。 有深度限制就把hull扔到线段树里用可持久化栈来维护一下。DFS的时候塞进线段树里，然后完了再扔出来。总的复杂度O(n*log^2(n))， 代码也不怎么复杂。 #include <cstdio> #include <cctype> #include <memory.h> #include <vector> #include <algorithm> using namespace std; struct edge { int t; edge* next; }; typedef long long qw; typedef long double exf; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } struct oper { int p, v, t;...