据说是男人八题。 状态太差调了一节宝贵的晚自习，严重不开心。 异常裸的点分治。然后里面还是套的sbt。 卡空间比较丧病，不能开nlogn，要想办法开到n。其实就是找重心分治完再bfs一遍。最初没有写，所以mle爽，在poj上还显示的是re。 然后各种逗的错误调啊调。把代码调得怪丑。我还是naive啊。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, v; edge *next; }; const int maxn = 40009; int n, k, ans; int d[maxn], tvis, vis[maxn], vd[maxn], sz[maxn], qu[maxn]; edge *ep, *head[maxn], elst[maxn * 2]; #define update(_p_) (sz[_p_]=sz[ls[_p_]]+sz[rs[_p_]]+1) namespace sbt { const int maxnd = maxn * 2; const int balc = 5; int nst[maxnd], tn; int ls[maxnd], rs[maxnd], vl[maxnd], sz[maxnd]; inline void lRot(int& p) {...

jason_yu表示是kd-tree的裸题。 拿个堆维护一下答案，然后剪剪枝啥的，写起来轻松愉快还比lct短。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; typedef long long qw; typedef pair <qw, int> hele; #define _l (qw) int _d_; bool _nag_; #define readInt(_x_) { \ int &_s_ = _x_; \ _s_ = 0; \ _nag_ = 0; \ while (!isdigit(_d_ = getchar())) \ if (_d_ == '-') \ _nag_ = 1; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ if (_nag_) \ _s_ = - _s_;\ } const int maxn = 100009;...

写完Kdtree感觉整个人都要离散了。 这题比较神，之前连题都没看懂。每个位置的方案数就是上下左右的数量的组合数的乘积。把x离散之后维护区间中左×右的和，上下y相同的扫一遍搞定。（感觉说了像没说） #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct point { int x, y; }; const int maxn = 100009; const int maxk = 13; inline bool cmpP(int* a, int* b) { return *a < *b; } inline bool cmpy(const point& a, const point& b) { return (a. y < b. y) || (a. y == b. y && a. x < b. x); } point a[maxn]; int n, m, c[maxn][maxk], cx[maxn], tx[maxn], t[maxn], maxx, ans;...

Log^2的cdq分治怎么也跑不过。优化常数优化到底了也不行。所以kd大法好。 怎么都觉得kd树就一暴力+剪枝=log。 思想就是先按x二分，然后再按y二分，然后再按x二分。然后这玩意比较像平衡树，中间那个点是要代表一个真实的结点的而不是一个值。然后insert的时候感觉复杂度完全没有保证啊。如果要保证可能要替罪羊一类的东西吧。虽然这题好像不用保证。 询问的时候就更迷了，就是估计一个离哪边近，然后先搜。然后另一边如果估计值还小于答案就再搜一遍。好诡异，时间复杂度是怎么来的。 然后代码略丑，加了zhx式读入优化后长度xxxxx。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; #define READ_OPTIMIZE #ifdef READ_OPTIMIZE /*int _d_; #define readInt(_s_) {\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ }*/ const int BUF_SIZE = 30; char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1;    #define PTR_NEXT() \ { \ buf_s ++; \ if (buf_s == buf_t) \ { \ buf_s = buf; \ buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \...

看时间比较宽么，写一个log^2的cdq+树状数组么。 然后被2648卡了。学kd-tree吧。 naive。 #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()));\ } struct point { int x, y, t, i; }; const int maxn = 500009; const int maxz = 1000009; const int inf = 0x3f3f3f3f; inline bool cmpPoint(const point& a, const point& b) { return a....

看到取模瞬间想到了昨天的bc。 应该这是取模然后求啥玩意的时候的比较通用的解法吧。p<=sqrt(maxv)的预处理，剩下的直接暴力。结果预处理又写丑了一回。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100009; const int maxv = 10000; const int bsz = 100; const int maxb = 103; int n, m; int a[maxn], vb[maxb][maxb], ve[maxb][maxb]; int xb[maxn], xe[maxn]; int i_buf[maxn * maxb * 2], tib; void pre() { memset(ve, 0, sizeof(ve)); memset(xe, 0, sizeof(xe)); for (int i = 1; i <= n; ++ i) ++ xe[a[i]]; for (int i = 0; i <= maxv; ++ i) {...

数位DP好麻烦啊不想写啊怎么办啊。 利用trie树思想直接做好了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif const int maxn = 15; qw p10[maxn]; qw x, y, ans[10], c[10]; int n; char a[maxn]; void calc(qw val, int sgn) { if (!val) return; sprintf(a + 1, lld, val); int n = strlen(a + 1); memset(c, 0, sizeof(c)); qw cz, cm, cr; cz = 1;...

乍一看不会。 想了想，求出每一个数的前一个相同的数的位置和后一个相同的数的位置，然后询问就是L<=i<=R && next[i]>=R && last[i] <= L的最大的a[i]。这三层树套树啊！？ 好像不带修改，那可以把一个Log的树优化成1的前缀和。 然后最值不满足减法，所以就把L<=i<=R拿动态建的线段树套里面好了。 卡空间400+MB过了，我对拍的大数据把网上的某人的程序干掉了哈哈。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct seg { int v, ls, rs; }; const int maxn = 100009; const int maxnd = maxn * 409; int n, m, a[maxn], v[maxn], ls[maxn], nx[maxn], o[maxn]; int t[maxn], sp; seg sl[maxnd]; inline bool cmpO(const int& a, const int& b) { return ls[a] < ls[b]; } int getLa(int l0) { int l = 1, r = n;...

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];...