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

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

本来以为是上回那道数正方形的原题的。结果发现不要求边与座标轴平行，于是我就naive了。然后数据结构变身计算几何一堆东西吼吼。 矩形的对角线相等且互相平分（来自初二数学书）。把所有点对的中点找出来，把所有相等且平分的放一起用单调性，有点像旋转卡(qia3)壳(qiao4)的做法。jason_yu说暴力枚举都能过，而且他跑得比我快！ 计算几何也写得比较naive。调了半天啊。 毕竟我弱嘛。 #include <cstdio> #include <cmath> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) const double eps = 1e-8; const int maxn = 1509; #define sqr(x) ((x)*(x)) #define dist(a,b) (sqr(a.x-b.x)+sqr(a.y-b.y)) #define nextele(_x_) ((_x_+1==r)?(l):(_x_+1)) struct point { qw x, y; point(qw x0 = 0, qw y0 = 0) { x = x0, y = y0; } inline point operator =(const point& a) {...

找到一道水题真是一件令人开心的事情。 最小生成树。完了。 #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define sqr(x) ((x)*(x)) struct edge { int a, b, v; edge(int a0 = 0, int b0 = 0, int v0 = 0) { a = a0, b = b0, v = v0; } }; const int maxn = 1009; int n, m, a[maxn], t, x[maxn], y[maxn], r[maxn]; edge e[maxn * maxn]; inline bool cmpE(const edge& a, const edge& b) { return a. v < b....