数据结构题神马的最开心了。 乍一看动态树，其实不然。复杂度可以再乘一个log的。 启发式合并。然后合并的时候直接暴力重构整棵子树，建主席树只和父亲节点有关，所以还是能搞定。 写了一个机智的垃圾回收把log^2的空间变成了log。然后发现空间有512MB。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; edge* next; }; struct seg { int v, c; 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 maxl = 33; const int maxnd = maxn * maxl;...

只有两个星期。 第一个星期（也就是现在）先在bzoj上写些水题来找找感觉。 根据卷子再看一遍半期之前的知识点。然后看一看历史书。 第二个星期去学习kd-tree，然后写题。顺便可以研究一下高维树套树的问题。 开始做文化课的作业。数理化生跟着进度，自己选择性多做一些作业。

好恶心的数据结构题。 考虑单个询问。把(视作1，把)视作-1，设minprefix为最小前缀和，设cp=(minprefix+1)/2，那么答案为(sum/2+cp*2)，使劲想想想得出来。 所以就是用个splay或者smt来维护一下一段的最小前缀和以及总和。因为有两种操作所以写起来比较麻烦。要注意不要把操作看反了，还要注意标记的优先级和更新的问题。 恶心了一下午。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct dat { int sm, t[2][2]; inline void operator =(const dat& a) { sm = a. sm; t[0][0] = a. t[0][0]; t[0][1] = a. t[0][1]; t[1][0] = a. t[1][0]; t[1][1] = a. t[1][1]; } }; const int maxn = 100009; int n, m, cr, a[maxn], sz[maxn], ls[maxn], rs[maxn], pt[maxn], vl[maxn]; bool flip[maxn], rev[maxn]; dat d[maxn]; dat sgd(int v) { dat r; r. sm = v;...

好厉害的数据结构题，时限太吓人了。 最初想写莫队的，但是在数据范围下屈服了。 用可持久化线段树套可持久化线段树来维护可过。虽然跑了97s。本机跑得快得多，虽然有两个点被卡到了18s。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; struct seg { int v, ls, rs; }; #define readInt(_s_) {\ _s_ = 0;\ int _d_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 100009; const int maxl = 20; const int maxnd = maxn * maxl * maxl; seg s[maxnd]; int n, m, t, a[maxn], d[maxn], c[maxn], *r[maxn], sp, rt[maxn];...

前天晚上的best coder的题。 数据太弱暴力都放过去了，而且还是错的。当然我也太naive了TT。 我没管k<=10，直接硬上树状数组套平衡树，用二分搞的。然后数组开小了不开心啊。 #include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <set> #include <memory.h> using namespace std; struct query { int x, y, k, n; }; struct tower { int x, y, h; }; inline bool cmpTower(const tower& a, const tower& b) { return a. x < b. x; } inline bool cmpQuery(const query& a, const query& b) { return a. x < b. x; } inline bool cmpP(int* a, int* b) {...

做事总得有点计划性。 省选是第二步。noip这步逗了，所以后面要加油。 十一月和十二月重点搞数据结构。毕竟天冷不适合思考太复杂的数学问题TT比如kd-tree之类的东西拿来看一看，bzoj上以前wc的数据结构也不少。争取多刷些题。 一月份大概会有会考，就乱刷些题当休闲了。 二月有wc。然后到时候大神应该也比较多，可以多学习一下数学题和dp。还要把计算几何认真学习一下。 三月大概会开始集训了。图论题比较重要。很多题就是看你记不记得那些结论。当然也有不少的烧脑题。需要多刷题来弥补智商的不足。 四月么，加油！

想起有这么一个总结，但是忘了带本子了，只好这样写了。 半个学期在学习文化课的时间也不超过20天。大概是没有多少好总结的。 半期的时候考懞了。虽然也花了三天的时间预习，不过那也只是简单地补补知识点，完全不能挽回任何东西。毕竟在高中的文化课里，书本和考试的差距还是有那么一些大的。感觉数学英语的差距要稍微小一些，另外四科就比较惨淡了。下半学期没有noip那么要紧的事情了，虽然还要停课，但是每天晚上也还是要做下作业，补一补知识点。数学物理和英语争取能跟上进度，这样压力应该会小一些。然后前半期的知识，每天做完作业之后也按顺序去前面把相应的作业做一做。班上有不少人批判刷题，但是现在血淋淋的事实就是，不刷题根本没有办法应付考试。 另外就是竞赛吧。其实这半期也没有写多少议论文，题解和总结倒写了不少。noip考得应该还将就，明天出正式成绩。反正第一步是迈出去了，后面的路会更艰险，不过我有信心和决心去实现自己的愿望。选择了便认定这一条路走下去，剩者为王！ 好像虽然在停课，也参与了一些活动。比如运动会啥的，然后成绩也不错以至于被rp攻击了好几天。长跑教会了我不只是长跑。也许有许多人会和你在路上相遇，但是只有你自己坚持下来去冲击终点的红线。也许有人会跑得很快，但是你也不要怕，也许他们过会就会体力不支。也许有人会跑得很慢，但是也不要骄傲，他们也许是在保存实力。至于总有些人会战胜你，要保持一颗平和的心，因为有很多人也在以同样的视角看你。总之，你要做的就是不断地努力。即使是在你累得不能呼吸的时候，只要终点还在前方，你就得跑下去。长跑如是，竞赛如是，人生亦如是。当然长跑这个项目也不能停。好的身体在后面的学习中还是很重要的。 另外在停课搞竞赛的时候也还是学到了很多其它的东西。比如如何去协助老师管理同学，如何组织大家做事，以及如何应对各种突发情况等等。这些也是人生宝贵的财富吧。管理人是比管理程序更麻烦也更有挑战性的一件事情，也是必需要学会的一件事情。 下半学期的任务更加复杂。没有像noip一样的重大事件了，但是这半个学期将会深远地影响到高中结业以及省选，所以也要抓紧时间，提高效率。 最后希望明天++ rp，也希望我不会再写一篇同样题目的总结。 Historical Comments Unknown friend at 2014-11-16T22:56:11 OTL OTL OTL OTL OTL Unknown friend at 2014-11-16T22:57:13 现在还在赶……

这题就是考你怎么把能优化常数的地方都优化一下。 做法比较清晰，分块加持久化值域线段树。大块预处理，小块暴力算。虽然最初不想写持久化数据结构就试图用平衡树去做，结果发现做法是错的，单次复杂度是O(n*lgn)的。看来我太年轻了。后来改了但是常数巨大也没法跑。 本来是一次询问里有若干次在持久化线段树上查询的。然后首先发现可以预处理出从开头到一块末尾这一段里有多少个比后面任意一个位置大的数的个数。还有一个数前面比它大的数的个数。这俩加起来常数差不多就小到能过了。 丧心病狂！ #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int maxn = 50009; const int maxb = 259; const int maxnd = maxn * 30; struct seg { int v; seg *ls, *rs; }; inline bool cmpP(const int* a, const int* b) { return *a < *b; } #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\...

暑假的时候就听zhx讲过这题，不过好像当时讲复杂了。 很容易知道答案就是每次减去被出列的人里面没有出过列的人在原序列里右边的比她矮的人的个数。 所以每个人只会被算一次，均摊下来是O(n)的。然后就是怎么很快地找到这些人。我觉得用线段树比较方便，时间可以做到log。不知道是不是能用并查集。 好写好调。 #include <cstdio> #include <cstdlib> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; #define readInt(_s_) {\ int _d_;\ while (!isdigit(_d_ = getchar()));\ _s_ = 0;\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif struct seg { int l, r, v, p; seg *ls, *rs; }; const int maxn = 500009;...

连yjq都会做，简直是水暴了。 #include <cstdio> #include <cstring> #include <algorithm>   usingnamespacestd;   constintmaxn = 20009;   intn, m, a[maxn], t[maxn], *r[maxn], s;   intbtQry(int* t, intp) {     ints = 0;     while(p)         s += t[p], p -= (p & -p);     returns; }   voidbtChg(int* t, intp, intv) {     while(p < maxn)         t[p] += v, p += (p & -p); }   inlineboolcmpP(constint* a, constint* b) {     return*a < *b; }   intmain() { #ifndef ONLINE_JUDGE     freopen("in.txt", "r", stdin); #endif...