LCT的简单题。好久不写都手生了，还把rotate写错了一点点，导致找了半天错。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; int _d_; #define readInt(_s_) {\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 300009; int n, m; int ls[maxn], rs[maxn], pt[maxn], rv[maxn], vl[maxn], vs[maxn]; inline void update(const int& p) { vs[p] = vs[ls[p]] ^ vl[p] ^ vs[rs[p]]; } inline void fix(int p) { if (rv[p]) { swap(ls[p], rs[p]); if (ls[p])...

cdq分治第二题。 最初没看清题所以一直不会做。晕。 cdq教程里的模板题。 显然所有卖都是卖完，买都是把钱买光。 f[i]表示第i天结束后最多持有b卷的数量，ans表示当前最多能赚到的rmb。 方程是： f[i] = max(ans, f[j] * r[j] * a[i] + f[j] * b[i]) / (a[i] * r[i] + b[i])。 移项得： f[j] = -(a[i]/b[i]) * (r[j] * f[j]) + (r[i] * a[i] + b[i]) / b[i] * f[j]。 把r[j]*f[j]看作x，把f[j]看作y，好像可以斜率优化了。  不急，f[j]好像没有单调性吧？不对，好像a[i]/b[i]也没有单调性！？ 平衡树维护凸壳？想起了上回那道hnoi的作业，调了一晚上，怎么能这样。 然后，其实可以cdq。 每次对右边有影响的是左边的凸壳，所以先跑左边，计算左边对右边的影响，再跑右边。这回是中序遍历，而不是Mokia那题的后序。 原来cdq可以这么神奇。 然后又把凸壳写丑了TT。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100009; double ans, s, f[maxn], a[maxn], b[maxn], r[maxn]; int n, h[maxn], tmp[maxn], t; inline double getx(const int& i) { return f[i] * r[i]; } inline double gety(const int& i) { return f[i];...

好像要用二维AC自动机的样子！？不对，还要优化不然还会MLE！？ naive。 哈希水过之。 中途某处忘强转导致调了良久。 2462丧心病狂卡stl常数，差点写平衡树了，然后想了想二分水之。 #include <cstdio> #include <cstring> #include <set> #include <algorithm> using namespace std; typedef long long qw; typedef unsigned long long uqw; #define _l (qw) const int rmod = 345379; const int b1 = 3; const int b2 = 3153131; const int maxn = 1009; int pb1[maxn]; int n, m, x, y, q, hr[maxn][maxn], t; uqw hl[maxn][maxn], pb2[maxn]; char g[maxn]; uqw th[maxn * maxn]; void pre() { pb1[0] = 1; pb2[0] = 1;...

cdq分治第一题。 最近的主题是数据结构，这玩意应该也算一种和莫队一样厉害的黑暗大法吧。有些需要你把在线写得足够厉害的题可以用这玩意来水。 写起来很像归并排序，按时间分治，然后再按某个坐标之类的玩意归并一下，归并的时候像求逆序对一样做，计算一边对另一边的贡献，顺便用点啥数据结构维护一下之类的。 这题有点像上帝造题七分钟。不过w的范围显然不是让你写二维树状数组。感觉那题可以用cdq水过，不过cdq好像不能用简单的二维树状数组，至少要动态一下啥的，然后空间就bye了。 这题就是按x排序查询y。课件上的原题。 另外依然不会迗代，还是写的递归。（找到了fft的感觉） #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif struct query { int t, x, y, v; inline query(int t0 = 0, int x0 = 0, int y0 = 0, int v0 = 0) { t = t0, x = x0, y = y0, v = v0; } };...

出题人应该才是真正的机房语文竞赛冠军。 好厉害的数据结构。cdq的不会。 树状数组套平衡树跑得飞快。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct flower { int a, b, c; }; const int maxn = 100009; const int maxv = 200009; const int maxl = 17; #define update(p) (sz[p]=sz[ls[p]]+sz[rs[p]]+1) namespace sbt { const int maxnd = maxn * maxl; const int balc = 10; int tn, ls[maxnd], rs[maxnd], sz[maxnd], vl[maxnd]; void init() { tn = 0; sz[0] = 0; } inline void lRot(int& p) {...

BZOJ里的第二道noip题，今年防ak题，OTZ。 最初直接用大素数取模的方法要TLE，虽然本机不会。 用几个小质数pni，算出在模pni的同余系里0~pni-1的答案。如果x为原方程的解的话x%pni在模pni意义下也应该为0。 然后还是会TLE，最后发现小质数乘的时候不用取模了。bzoj上这题纯粹是丧心病狂卡常数啊。 ORZMHY #define PROC "equation" #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef unsigned long long uqw; typedef long long qw; const int maxn = 109; const int maxl = 10009; const int maxm = 1000009; const int cp = 5; //const int pn[cp] = {111119, 23333, 11113, 23251, 33329}; const int pn[] = {22861, 22871, 22877, 22901, 22907, 22921}; const int p10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};...

做过。但是不对。 迷之找负环。 初值直接赋为0，这样可以节省找没用的最短路的时间。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; double v; edge *next; }; const int maxn = 3009; const int maxm = 10009; const double eps = 1e-9; const double finf = 1e20;  int n, m; bool iq[maxn]; double d[maxn], ave; edge *ep, *head[maxn], elst[maxm]; bool dfs(int p) { iq[p] = 1; for (edge* e = head[p]; e; e = e-> next) if (d[e-> t] - (d[p] + e-> v) > eps) {...

数据结构题神马的最开心了。 乍一看动态树，其实不然。复杂度可以再乘一个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;...