data\xa0structure

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

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) {...

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

好恶心的数据结构题。 考虑单个询问。把(视作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;...

好厉害的数据结构题，时限太吓人了。 最初想写莫队的，但是在数据范围下屈服了。 用可持久化线段树套可持久化线段树来维护可过。虽然跑了97s。本机跑得快得多，虽然有两个点被卡到了18s。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; struct seg { int v, ls, rs; }; #define readInt(_s_) {\ _s_ = 0;\ int _d_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 100009; const int maxl = 20; const int maxnd = maxn * maxl * maxl; seg s[maxnd]; int n, m, t, a[maxn], d[maxn], c[maxn], *r[maxn], sp, rt[maxn];...

前天晚上的best coder的题。 数据太弱暴力都放过去了，而且还是错的。当然我也太naive了TT。 我没管k<=10，直接硬上树状数组套平衡树，用二分搞的。然后数组开小了不开心啊。 #include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <set> #include <memory.h> using namespace std; struct query { int x, y, k, n; }; struct tower { int x, y, h; }; inline bool cmpTower(const tower& a, const tower& b) { return a. x < b. x; } inline bool cmpQuery(const query& a, const query& b) { return a. x < b. x; } inline bool cmpP(int* a, int* b) {...

这题就是考你怎么把能优化常数的地方都优化一下。 做法比较清晰，分块加持久化值域线段树。大块预处理，小块暴力算。虽然最初不想写持久化数据结构就试图用平衡树去做，结果发现做法是错的，单次复杂度是O(n*lgn)的。看来我太年轻了。后来改了但是常数巨大也没法跑。 本来是一次询问里有若干次在持久化线段树上查询的。然后首先发现可以预处理出从开头到一块末尾这一段里有多少个比后面任意一个位置大的数的个数。还有一个数前面比它大的数的个数。这俩加起来常数差不多就小到能过了。 丧心病狂！ #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int maxn = 50009; const int maxb = 259; const int maxnd = maxn * 30; struct seg { int v; seg *ls, *rs; }; inline bool cmpP(const int* a, const int* b) { return *a < *b; } #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\...

暑假的时候就听zhx讲过这题，不过好像当时讲复杂了。 很容易知道答案就是每次减去被出列的人里面没有出过列的人在原序列里右边的比她矮的人的个数。 所以每个人只会被算一次，均摊下来是O(n)的。然后就是怎么很快地找到这些人。我觉得用线段树比较方便，时间可以做到log。不知道是不是能用并查集。 好写好调。 #include <cstdio> #include <cstdlib> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; #define readInt(_s_) {\ int _d_;\ while (!isdigit(_d_ = getchar()));\ _s_ = 0;\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif struct seg { int l, r, v, p; seg *ls, *rs; }; const int maxn = 500009;...

很久之前就看过的题。不过一直没有勇气去做。爱真的需要勇气。 mex这个函数的性质比较奇妙。一端确定的话一定是单增的。两段和起来也一定是增加的。 可以很方便地求出从1到任何一个位置的mex。考虑把询问离线。按左端点排序。如果去掉一个数，那么对于右端点在（从这个数到下一个等于这个数的位置）这一段里的询问，它的值至多是这个数。 所以用线段树维护区修单查维护一下区间最小值就好了。注意如果没有下一个数了那么右端点是n。 据说要离散不过被我用map给水过去了。 #include <cstdio> #include <cctype> #include <memory.h> #include <map> #include <algorithm> using namespace std; #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } struct seg { int l, r, z; seg *ls, *rs; }; struct query { int l, r, n; }; inline bool cmpQuery(const query& a, const query& b) { return a. l < b....