这题就是考你怎么把能优化常数的地方都优化一下。 做法比较清晰，分块加持久化值域线段树。大块预处理，小块暴力算。虽然最初不想写持久化数据结构就试图用平衡树去做，结果发现做法是错的，单次复杂度是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...

居然感冒了，嗓子痛死了。 8:00 进考场了，不准动机器，那还怎么配vim啊TT 8:30 这密码。看了下题好像也不是特别麻烦啊，除了最后一题有个10^10000。 8:35 第一题敲完了？ 8:45 第二题敲完了？ 8:50 第三题想不出其它的做法啊。哈希吧。 9:10 花了四十分钟就做完了？点开扫雷的时候看到了身旁某兄怨念的眼神。 10:00 第三题极限数据居然会tle。想打数据分治但是觉得不好的。发现可以先用自然溢出，如果没有暴再用模质数检查。这样好像0.5s能跑完。希望评测机不要比这个机子慢太多。 11:00 第一题居然把++ x写scanf上面了，作死。 12:00 终于交卷了。又老了一岁的感觉。 12:15 照相，讨论。jason_yu好像第三题写得不太一样，其他人基本都想得一样。看谁长得帅了。 然后某人的第六次noip就结束了。

记得noi的时候写了日记，那么noip也那么写一写。 听说今天的题很水，虽然我心里总有种不确定的感觉。 6:00 醒了。好像下雨了，有点冷。再睡会。 6:30 起床。 7:40 到考场了。因为下雨所以外面的广场上都没站什么人。倒是看到了徐老和初中的小伙伴。 8:10 开始配vim。好像我的键盘和旁边的同学不太一样，敲起来手感比较不错。 8:25? 发密码了。很淡定地输入，打开。好像之前已经重复做这个动作做了很多遍了，异常淡定。 8:30 第一题n才200？直接模拟？打表，写。 8:40 原来第二题是树。写。 8:55 第三题n*m^2会tle?难道不应该是f[i]-i=max(f[j]-j)?写！ 9:10 写完好晕，怎么过不了样例啊。打印中间变量发现如果上升的话就不会下降了，囧。 9:40 好像写完了，对拍吧。 10:xx 第二题居然乘暴了。原来要取模。 11:xx 第三题拍出错了！？仔细一看暴力有bug。 12:00 终于交卷了，尿胀慌了。 出来看到小伙伴们也比较开心。心里还是那种很不确定的感觉。估分的时候扔了个300，大概是在向flag学说发出挑战。还好有mhy陪我挑战。 day1就这么过去了。原来我是如此之年轻。

好奇怪的题目。 明天就要考noip了。第六年了，该成熟点了。 仿佛也在几个小时前有一些紧张。这么多年这么些路走过来了，这算是最后一博了吧？ 更多的是一种成长的感觉吧。这一年，改变了太多太多了。从noip2013的惨败开始，有wc的奇奇怪怪的noip后遗症，然后是省选莫名其妙自己扔了一百多分，然后混进noi又疏忽地把au拿去喂狗了。没有什么好看的成绩，只有一双越来越快的敲键盘的手。 这两天的集训考得还是将就。但是也没有九月那么绝对了。也许是我的心态也没有经受住挑战，也许是大家都进步了吧。两者都有。总觉得过去的一切离我好遥远，好像去年的我和今年的我是老死不相识的两个人似的。这叫作成长？或者是太专注一件事情导致的沧桑？ oi就是那么玄妙。不见到ccf官网上的成绩，一切就是未知数。即使考前能场场ak，也说不准考场上会发生什么，何况我也没有那个实力去ak。换个角度说，noip，考的是细心。 只能说调整好自己的心态， 淡定地去战斗吧。 预祝所有人能成功，即使没有什么人会看到这句话。

居然写了一半手贱就把所有东西都弄没了。严重地不开心。 既然这样那么简单说吧。 长度≤10^5这个条件在bzoj上没说。 用fft求出长度和为leni的组数。 枚举第三根火柴，可行的是（它作为最长的总组合数 - （长度≤它的组合数））那么多组。 fft必需常数够小。不写蝴蝶会tle。 #include <cstdio> #include <cmath> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; typedef long long qw; #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } struct cplx { double r, i; inline cplx() { r = 0, i = 0; } inline cplx(double r0, double i0) { r = r0, i = i0;...

很久之前就看过的题。不过一直没有勇气去做。爱真的需要勇气。 mex这个函数的性质比较奇妙。一端确定的话一定是单增的。两段和起来也一定是增加的。 可以很方便地求出从1到任何一个位置的mex。考虑把询问离线。按左端点排序。如果去掉一个数，那么对于右端点在（从这个数到下一个等于这个数的位置）这一段里的询问，它的值至多是这个数。 所以用线段树维护区修单查维护一下区间最小值就好了。注意如果没有下一个数了那么右端点是n。 据说要离散不过被我用map给水过去了。 #include <cstdio> #include <cctype> #include <memory.h> #include <map> #include <algorithm> using namespace std; #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } struct seg { int l, r, z; seg *ls, *rs; }; struct query { int l, r, n; }; inline bool cmpQuery(const query& a, const query& b) { return a. l < b....

比较神奇的一道树的题。 做法是离线。想了好久的在线啊。 把询问拆成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;...

离noip只有12天了。这是我的倒数第二次noip中，正数第六次。 作为一个老人不需要太多的惊慌或者什么的。保持一颗平和与淡定的心是最重要的。 接下来都是连续的考试了。总共有10套题。这个时候也不是大规划地去补算法的时候。更多的是要调整好自己，学会怎样去应试。 oi中的一系列赛事里只有noip是三个半小时，而不是五个小时。当然它的难度与普及度决定了这一点。所以你没有更多的时间去思考和感受。更多需要的是准确的直觉和高效的代码。 任何一个小处的失误，都是致使的。唯一的办法是检查，检查，再检查。后面的考试里尽量要多坐一会，能对拍的都多拍一些数据。可能考试的时候还是会用windows，虽然这几天还是在noi-linux下练习。不过这也只是写bash脚本对拍和写bat对拍的小小区别而已。当然不要在这些小细节上浪费时间。不行用cpp就好。 noip的题目更多的在于思维难度，而不是代码难度。所以也要养成多动笔多打草稿多yy的习惯。 每天的安排也就是上午写题下午补题顺便刷题晚上刷题跑步散心睡觉。 嗯，哦，唉，×，fighting。