oi

退役了之后智商下降严重啊。今天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;...

本来想做点英语作业的。想10分钟把这题搞定的。结果傻了去写trie树dp又傻了没有考虑终点也可以有子结点。 我真是无药可救了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int tcnt; struct trie_node { int d, e, t[26]; inline trie_node(int d0 = 0) { e = 0; d = d0 + 1; memset(t, 0, sizeof(t)); } inline int ins(char c) { if (!t[c - 97]) t[c - 97] = ++ tcnt; return t[c - 97]; } inline int trans(char c) { return t[c - 97]; } }; const int inf = 0x3f3f3f3f; const int maxs = 15009;...

老早之前就听说过的题。好像讲过不只一遍。不过才从bzoj上翻出来。 记得是神奇的dp优化。为啥这年头卡常数的题这么多。 首先肯定这玩意多项式可解。六维状态肯定能搞定。然后会mle+tle。 首先考虑从高到低放书，那么后面的如果不新开一行的话对高度没有影响。瞬间少了3维状态。 然后发现只要知道两维的总宽度和当前是第几位，就能知道第三维的宽度。于是一维2100缩70，开滚动可过。 当然还是需要一些常数优化的技艺。比如用宽度直接判断这一行有没有书。这样可以省下不少时间，而且好像只能这样才存得下。64MB太紧了点。另外把函数里的int改成const int&会变慢，不知为何。 居然花了这么久才搞出来。我太年轻了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct book { int w, h; }; inline bool cmpBook(const book& a, const book& b) { return a. h > b. h; } const int maxn = 71; const int maxw = 2109; const int inf = 0x3f3f3f3f; int n, f[2][maxw][maxw], sw; book a[maxn]; inline void upmin(int& _a_, int _b_) { if (_a_ > _b_) _a_ = _b_;...

不久之后要会考了，再过不久要期末了。教育部在放风，大概以后如果noi拿不到金牌的话就得和别人一样地高考了。 一直在oi里面坚持也没有怎么想过高考的事，一直只是当作一个额外的好处。如果让我不上大学给我一次ioi的机会，我想我也不会犹豫的。 本来，上什么大学，也不是什么重要的事情。作为oier，我知道，只向上看，是个很好的品质，但是不是什么好的策略。如果你非要落魄到拿着期末成绩去让大学收你，那你该考虑换个差点的大学了。 因为做过鸡头，所以对做凤尾产生了抵触吧。 当然，显然，学校，老师都不这么想。虽然我来这里的目的也完全不是因为高考，但是既然穿上这身校服，你也没有办法。 背起包走回教室的感觉真的很像退役了。 大本的崭新的练习册让人很压抑。如何在两周内补完一个学期的内容是一个很艰巨的问题。也许多看书多刷题是个不错的选择。 既然有人要来挑战，那就让他们看看。

好一道卡常数。不仅卡时间，还卡空间。堪称丧心病狂的极致。 首先因为空间小所以得用莫队。然后不知为何树状数组没有直接分块跑得快。 没有救啦。 #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];...

乍一看矩阵水题，然后发现不能走回头路。 于是改一下把边当做点，把点当作转移，转移的时候就可以避免走过去就走回来的情况了。 说好的复习会考呢？ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) const int mod = 45989; const int maxn = 123; class matrix { public: int n, a[maxn][maxn]; inline matrix() { } inline matrix(int n0, bool one = 0) { n = n0; memset(a, 0, sizeof(a)); if (one) for (int i = 0; i < n; ++ i) a[i][i] = 1; } void operator =(const matrix& x) { n = x....

贪心。从小到大每个灯泡找个小于等于它的最接近的房间去照。 剩下的照不亮的房间直接换。 剩下的背包空间把已经匹配的差最大的换掉。 第一步要拿堆维护一下。剩下的直接排序。 然后把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;...