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

一堆标记的线段树。 翻过的，没翻过的，都分开记下来。然后还要注意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 {...

最近都在认真写Noip难度题（虽然跑题有点严重）。 专题大概是差不多了。 今天换个口味写数据结构好了。 就这么愉快地决定了。    

跑题了。 好像刷了几道水水的图论吧。估计也不会考到Msc或者极大团之类的玩意，所以也没写。 然后就刷了一天bzoj。第一次一天10道，好开心。 noip也不远了，感受到了各路大神的压力。 想要生存下去，唯一的出路是让自己不断变得更强。

比较神奇的数学题。 重要的结论是<n且与n素质的数的和是phi(n)*n/2。 所以就枚举一下gcd就好了。 #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 #define _l (qw) #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 1000009; qw ans[maxn]; int tp, pn[maxn], phi[maxn]; bool pr[maxn]; void pre() { memset(pr, 0, sizeof(pr));...

补昨天的题。 比较好想的计算几何。就看每个点在不在另一个颜色的点形成的上凸壳下面，下凸壳上面。这个用二分可以做到单次log。用单调应该也能O(n)。 但是写起来非常坑，要用long long，还有各种等号啥的。 写win32 app来显示点的代码比交上去的代码还长。开心。      #include <cstdio> #include <algorithm>   usingnamespacestd;   typedeflonglongqw;   #define _l (qw)   structpoint {     intx, y;     point (intx0 = 0, inty0 = 0) {         x = x0, y = y0;     }     inlinevoidread() {         scanf("%d%d", &x, &y);     } }; structvect {     intx, y;     vect(intx0 = 0, inty0 = 0) {         x = x0, y = y0;     }     vect(constpoint& a, constpoint& b) {...

因为运动会，好像时间又变少了。 早上本来想补觉来着，打开电脑就睡不着了。 上午先补题吧。 然后今天就去刷图论好了。最小生成树啊最短路啊还有各种神奇的东西都去写一写。 美好的一天。