data\xa0structure

全局二分+树状数组，其实还是比较水。 比较坑的一点是直接求和会暴long long。如果≥Pi了要直接break掉。好坑啊。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std;  int _d_; #define readInt(_x_) { \ int& _s_ = (_x_ = 0); \ while (!isdigit(_d_ = getchar())); \ while (_s_ = (_s_ << 3) + (_s_ << 1) + _d_ - 48, isdigit(_d_ = getchar())); \ } typedef long long dint; const int maxn = 300009; struct node { int v; node *next; }; struct rain { int l, r, a; }; struct bintree { dint t[maxn]; int n; bintree() {...

水一发。 本来可以直接拿主席树找中位数的，但是因为main上只有32MB，所以只好写了个splay。感觉现在是爱上指针了。然后kth的时候少打个等号又wa又re好爽。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (long long int) const int maxn = 100009; #define nsz(p) ((p)?(p->sz):0) #define sof(p) ((p)?(p->s):0) struct splay_node {    int v, sz;    dint s;    splay_node *ls, *rs, *pt;    inline void init(int v0) {    v = v0;    sz = 1;    s = v0;    pt = ls = rs = 0;...

英语阅读题。做完去翻译题面然后写英语作业了。 就维护一下区间里的距离和and忽略一个点的收益的最大值。完了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct seg { int l, r; int s, v; seg *ls, *rs; }; const int maxn = 100009; int n, m, x[maxn], y[maxn], d[maxn], v[maxn]; seg *rt, *sp; inline void upDis(int i) { if (i < n) d[i] = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]); else d[i] = 0; } inline void upVal(int i) { if (i > 1 && i < n) v[i] = d[i - 1] + d[i] - abs(x[i + 1] - x[i - 1]) - abs(y[i + 1] - y[i - 1]);...

退役了之后智商下降严重啊。今天bc死惨了。这比较水的题也是去看了题解才反应过来的。 先把序列改成不降。 然后把原来的序列分成一些段，每段的中位数递增。   考虑新加入一个ai，如果它比前一段的中位数小，那么就把它和前一段合并，再拿合并之后的段去和再前一段比较一下。其实我也不能证明为啥是这样，只是感觉比较有道理。我肯定是没救了。 中位数的话用可合并的堆来维护比较方便。orz各种神级堆，然后我还是用的左偏树。 以后树要拿指针写所以代码巨长。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; int _d_; #define readInt(_x_) { \ int& _s_ = _x_; \ while (!isdigit(_d_ = getchar())); \ _s_ = 0; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } #define sof(p) ((p)?(p->s):0) struct node { int v, s; node *ls, *rs; inline void init(int x) { v = x; s = 1; ls = 0; rs = 0;...

大概是今天不宜刷题来着。应该好好做作业。 用线段树套单调队列可以把复杂度降到O(nlogn)。然后deque严重不靠谱，得用list才行。 然后还是跑得巨慢。前面的人是排序搞定的么？表示不明觉厉。 #include <cstdio> #include <cctype> #include <cstring> #include <deque> #include <list> #include <algorithm> using namespace std; int _d_; #define readInt(_x_) { \ int& _s_ = _x_; \ while (!isdigit(_d_ = getchar())); \ _s_ = 0; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } //typedef deque <int> dque_i; typedef list <int> dque_i; struct seg { int l, r; dque_i u, d; seg *ls, *rs; }; const int maxn = 250009;...

zhx+主席出的题，恐怖至极。 写此题需要极高的常数优化技巧+耐心。 本地跑到50s才在bzoj上压80s跑过。 其实思路就是拿线段树套AVL把询问的时间复杂度优化到O(logn)。 然后首先用treap会t爽+mle爽。 然后avl需要各种常数优化。 然后要在xxxxx地方优化。 加上zhx牌读入优化+块状内存+抄std的AVL+.....终于在81s过了。 orz比我快一倍的wangyisong神犇。 #include <cstdio> #include <cstdlib> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int BUF_SIZE = 300; char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1; #define PTR_NEXT() \ { \ buf_s ++; \ if (buf_s == buf_t) \ { \ buf_s = buf; \ buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \ } \ } #define readInt(_n_) \ { \ while (*buf_s != '-' && !isdigit(*buf_s)) \ PTR_NEXT(); \ bool register _nega_ = false; \ if (*buf_s == '-') \...

全局二分的经典题。 最初试图用持久化线段树和分块，然后欢快地tle+mle了。看到jason_yu和mhy过了，只能说自己的常数优化还不过关啊。 第一次写这种二分。就是把所有东西扔进来快速排序，顺便考虑每个询问应该被扔到哪边。然后加树状数组来统计就好了。 代码巨丑。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; struct query { int x1, y1, x2, y2, k, n; }; int _d_; #define readInt(_x_) { \ int& _s_ = _x_; \ while (!isdigit(_d_ = getchar())); \ _s_ = 0; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } const int maxn = 509; const int maxq = 310009; int n, m, t, maxa, a[maxn][maxn], b[maxn][maxn], ttm;...

好一道卡常数。不仅卡时间，还卡空间。堪称丧心病狂的极致。 首先因为空间小所以得用莫队。然后不知为何树状数组没有直接分块跑得快。 没有救啦。 #include <cstdio> #include <cctype> #include <cmath> #include <cstring> #include <algorithm>   usingnamespacestd;   structqry {     intl, r, a, b, n; };   int_d_; #define readInt(_x_) { \     int& _s_ = _x_; \     while(!isdigit(_d_ = getchar())); \     _s_ = 0; \     while((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ }   constintmaxn = 100009; constintmaxm = 1000009;   intn, m, bsz, a[maxn], c[maxn], w[maxn], b[maxn], ans[maxm];...

贪心。从小到大每个灯泡找个小于等于它的最接近的房间去照。 剩下的照不亮的房间直接换。 剩下的背包空间把已经匹配的差最大的换掉。 第一步要拿堆维护一下。剩下的直接排序。 然后把nie写成-1了，no save。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; typedef long long di; #ifdef WIN32 #define difmt "%I64d" #else #define difmt "%lld" #endif const int maxn = 500009; int _d_; #define readInt(_x_) { \ int& _s_ = _x_; \ while (!isdigit(_d_ = getchar())); \ _s_ = 0; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } int n, k, p[maxn], w[maxn], x[maxn], t;...

前两天还在YY动态DFS序呢，这就冒了一个出来。 动态DFS序的郁闷之处在于不好维护dfs序上的end。而把反括号建出来正好能解决这个问题。 然后就splay写得飞慢不知道怎么回事。 用两个栈就可以迭代做出括号序列，自己YY出来的给自己赞一个。 然后是目前最长的代码和倒数第二慢的时间。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; int _d_; #define readInt(_x_) { \ int &_s_ = _x_; \ while (!isdigit(_d_ = getchar())); \ _s_ = 0; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } #define readOpt(_x_) { \ while (!isupper(_d_ = getchar())); \ _x_ = _d_; \ } typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif struct edge { int t;...