bzoj

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

好像要用二维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) {...