数据结构-个人总结

i207M · 2018-08-03 23:15:52 · 个人记录

并查集维护深度、合并时间

要维护这些数据，我们要保持树的形态，所以我们要按秩合并，开几个数组记录额外信息；

注意，先find(f[x])，再更新dep

int find(int x) {
    if (x == f[x]) {
        dep[x] = 0;
        return x;
    }
    int y = find(f[x]);
    dep[x] = dep[f[x]] + 1;
    return y;
}

数据结构优化DP、决策

今年购入了 1 只呆河马。她们制定了从今年(即第 0 年)到第 n-1 年的养殖呆河马的计划。其中她们确定了一个繁殖系数 x_i，其中 x_i代表着在第 i 年，若第 i 年年初时有 h 只呆河马，则第 i 年年末(第 i+1 年年初)会有 h\cdot x_i只呆河马，且这个时候养殖园可以杀掉一些呆河马赚钱，每只呆河马的可以赚到的利润为 p_i。

修改操作：一次修改一个x_i或p_i；N<=10^5

对于每次修改，询问全局最大利润；

首先一点：一定是一次性卖出所有货物；

考虑第i天的答案f[i]=\Pi{x_i}\cdot p_i

此题精髓：通过数学方法（差分），维护数据结构得出答案

如果用线段树直接维护f[i]，我们需要实现区间乘一个实数，而这会丢失很多精度，而且要取模；

对于连乘，改变一个数貌似不好维护：取对数！

同时，取对数可以防止答案过大；

用权值线段树维护两数差的绝对值的最小值

注意是权值线段树

维护区间出现的数字的最大值，最小值；

所求s[x]=min(s[ls],s[rs],mn[rs]-mx[ls])

il void up(int x) {
    mx[x] = max(mx[ls], mx[rs]);
    mn[x] = min(mn[ls], mn[rs]);
    s[x] = min(mn[rs] - mx[ls], min(s[ls], s[rs]));
}

STL-multiset也可解决

代码

核心是：移动右区间：插入它与前驱后继的差；移动左区间：精确删除；

求中位数（无修改）

logn数据结构？no！

nth_element(first,nth,last)

JZOJ 观察

给出一棵以1为根的树，一开始每个节点都是一颗棋子，一面白一面黑，白色的面朝上；

接下来q次操作，操作分两种：

0操作 将一颗棋子翻转；

1操作 询问一颗棋子与所有面朝上为黑色的棋子lca最深的那个的编号。N,q<=8×10^5

Solution：

对于每个修改可以在这个点到根的路径上的点+(-)1；

对于每个询问找到这个点到根路径的第一个有值的点。

法一：硬上链剖，注意卡常；

法二：找出这棵树的欧拉序，对于一个点与它lca最深的在它欧拉序最近两个之一；set维护一下；

找到两个点后分别求lca找最深的就可以了；时间复杂度 O(n log n)

卡常**题

每当有一个黑点，就加入set，每次查询dfn的前后；

递增数列，对于每个数，求出它与其他数的差的绝对值第k小的位置

使用单调队列维护，size为k+1；

可以这样考虑，我们从左往右考虑，实际上是不断的接近a[r+1]的过程，当a[r+1]-a[i]<a[i]-a[l]，就将滑动窗口整体右移；

    int l = 1, r = k + 1;
    for (ri i = 1; i <= n; ++i) {
        while (r < n && a[r + 1] - a[i] < a[i] - a[l]) ++l, ++r;
        f[0][i] = (a[r] - a[i] > a[i] - a[l] ? r : l);
        // printf("F %d %d\n", i, f[0][i]);
    }

二维树状数组，二维差分

二维差分：矩形加，单点求；转化为差分求前缀和；

int tre[N][N];
void upd(int x, int y, int k)
{
    for (; x <= n; x += x & -x)
        for (ri i = y; i <= m; i += i & -i)
            tre[x][i] ^= k;
}
int ask(int x, int y)
{
    int res = 0;
    for (; x; x -= x & -x)
        for (ri i = y; i; i -= i & -i)
            res ^= tre[x][i];
    return res;
}

双指针

以NTOJ1012（？？？考试）为例：

适合于在有序数列中求<=某个数的个数，且询问的数字单调的情况；

while()指针跑一发即可；

如何像这个题一样防止重叠呢？开一个数组记录每个数字被覆盖了几次即可，防止出锅最好两个标记的数字相差大一点；

不能把

        mrk[p[i].id] += 2;
        if(mrk[p[i].id] == 2) ++tmp;

加上条件判断（mrk==0）再执行，不然会少算很多；

    int tmp = 0, pt = 1;
    double res = sqrt(f / ks);
    while(pt <= n && b[pt].b <= res)
    {
        mrk[b[pt].id] = 1;
        ++pt;
        ++tmp;
    }
    --pt;
    ans = max(ans, tmp);
    for(ri i = 1; i <= n; ++i)
    {
        if(kh * p[i].a * p[i].a > f) break;
        res = sqrt((f - kh * p[i].a * p[i].a) / ks);
        mrk[p[i].id] += 2;
        if(mrk[p[i].id] == 2) ++tmp;
        while(pt >= 1 && b[pt].b > res)
        {
            --mrk[b[pt].id];
            if(mrk[b[pt].id] == 0) --tmp;
            --pt;
        }
        ans = max(ans, tmp);
    }

P2824 [HEOI2016/TJOI2016]排序

给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。

询问排名的题目， 往往需要二分；

二分排名，大于等于mid设为1，小于mid的设为0；排序就变成了区间查询和区间修改；

ans即为使q为1的最大数字；

注意：每次要清空lazy标记！！！

自己YY的

给定一些区间，对于每个询问，给定一个区间[ql,qr]，询问与这个区间相交的区间+这个区间包含的区间的数量；

维护三个树状数组，通过加减，我们把所有答案算了两遍，除以2即可；

        in(op), in(l), in(r);
        if(op == 1)
        {
            lp.upd(l, 1);
            rp.upd(r, 1);
            ap.upd(l, 1);
            ap.upd(r + 1, -1);
        }
        else
        {
            int ans = 0;
            ans += lp.ask(r - 1) - lp.ask(l);
            ans += rp.ask(r - 1) - rp.ask(l);
            ans += ap.ask(l) + ap.ask(r);
            printf("%d\n", ans >> 1);
        }

树状数组区间加区间和

就不放代码了

上面那个问题的二维版本

维护四个数组d[i][j],d[i][j]*i,d[i][j]*j,d[i][j]*i*j，从而实现区间查询

POJ 2442 序列

给定m个序列，每个包含n个非负整数。现在我们可以从每个序列中选择一个数字以形成具有m个整数的序列。很明显，我们可能得到这种序列。然后我们可以计算每个序列中的数字之和，并得到n ^ m个值。我们需要的是最小的n个总和。

李煜东的书P77

两两合并

区间加等差数列，求单点

两次差分，区间加等差数列相当于在差分数列上，L加首项，L+1~R加公差，R+1减末项

再差分一遍就好；

自己的单调队列博客

权值线段树找中位数

在离散化的时候，不用unique，给不同位置的相同值按位置升序给予编号；尤其是维护区间权值和的时候！

原因！！！把很多点缩成一个位置，在求和的时候，边界就会混乱！！！P3466 [POI2008]KLO-Building blocks

P3792 由乃与大母神原型和偶像崇拜

毒瘤题面

给定一个数列，支持单点修改，查询区间内的数是不是连续的（4123这种）；

也就是说，我们只要求区间内出现了这些数字，但是不要求连续：无序Hash！而且我们还要很快的算出期望结果，所以我们维护区间min,max,和，平方和，异或和；

并查集路径压缩时，记录的其他数据最好不包括自身， 例如，up[x]表示在x上方的块数；这样在每次find后，都+up[f[x]]才正确

CF221D，EOJ强制在线

给定一个数列，有若干次询问，每次给定 [l,r]，问有多少个 x，在 [l,r] 中出现恰好 x 次

用线段树扫描线的思想，维护每个后缀的答案，对每个权值开一个vector；

强制在线？主席树！

void prework()
{
    for(ri i=1;i<=n;++i) v[i].pb(0);
    for(ri i=1,t;i<=n;++i)
    {
        tre[i]=tre[i-1];
        if(a[i]>n||a[i]<=0) continue;
        v[a[i]].pb(i);
        t=v[a[i]].size()-1;
        if(t>=a[i])
        { 
            if(t>a[i]) upd(tre[i],tre[i],1,n,v[a[i]][t-a[i]-1]+1,v[a[i]][t-a[i]],-1);
            upd(tre[i],tre[i],1,n,v[a[i]][t-a[i]]+1,v[a[i]][t-a[i]+1],1);
        }
    }
}

替罪羊树

当一个点的一个儿子的大小超过了这个点的大小的alpha倍，就拍扁重构这个子树，重构一棵完全二叉树。

不要忘了树状数组的超小常数！可以用来优化求前缀的线段树

查询区间询问

1. 对区间建立数据结构

2. 离线cdq，线段树分治

3. 离线，直接分治。处理经过mid的区间询问

树上LCA贡献的一种求法

如果题目要求：\sum dep[x]\times\text{以x为LCA的点对个数}

可以将贡献分开算，统计LCA到根的链上每一条边的贡献。这样的好处是不用在意两个点的LCA是不是它，只用考虑两个点都在它的子树里即可。

树链待修第k大

写CTSC网络管理的时候求成了第k小

比较暴力的方法是树剖，对每个重链维护树状数组套主席树，O(n\log^3n)

优美的做法：我们参考不带修的做法：可持久化线段树维护这个点到根的权值，用lca做差求得。那么带修呢？相当于在子树内每个点的主席树的某个位置插入一个值，之间树状数组+主席树，维护dfs序，支持子树加即可。

为了减小常数，最初所有点可以不用当做插入，直接单独建一棵原始主席树即可。

难以删除的数据结构

如果一个数据结构难以支持在线删除，但是容易在线插入。那么对于需要删除的题，我们可以再建立一套数据结构，如果一个点被删除，就把它插入到第二个结构中。然后统计贡献的话相减即可。

求与dep[lca]有关的和

比方说：维护点集，支持在线加入点x，求\sum _{y\in S} dep[lca(x,y)]\times a_y

方法是到根链加a_y，到根求和。

使用平衡树可以方便的维护下标平移、区间加的操作

或者对于形如dp[i]=\max(dp[i-1]+v,dp[i])，发现在某些时候永远更新，那么可以区间平移+区间加。

CF809D

主席树回溯修改

维护一个数据结构，支持区间修改，单点撤回最近一次修改，维护区间信息。可以用主席树同时维护修改时间和修改信息。对于一次撤回，假如它是在第t时刻修改的，那么就到t-1的主席树上找答案。

扫描线新思想

通常的扫描线是从左往右扫描到r，维护每个[i,r]的答案。但是还有新的思路：

从左往右扫描到r，对于所有\le r的东西，维护另一种下标的线段树，把左端点放到线段树的值上去。有时候可以做更多的事。

可离线区间操作新思想

离线支持区间取max，求每个位置的值，n=10^6,m=10^7。

我们只能在n处带log。有一个离线处理区间询问的利器：倍增拆区间！对于取max这种可重的询问，把它像st表一样拆成两个询问；对于不可重复的，拆成log个（但是这样就在询问上带log了）。然后，我们面对的就只有log种长度的区间了，我们按长度递减扫一下，把区间的贡献pushdown到下一级区间。

对于可以快速合并的信息，往往数据结构会大显身手，比如线段树

高维数据结构切换维度

如果使用高维(>1)数据结构，一些操作做起来比较吃力，不妨交换维度，例如外层权值，内层位置。

矩形加，矩形求和，矩形指n\times m网格的一个区域

不可以k-D Tree做。可以树套树，以树状数组套线段树为例，外层的树状数组需要像“树状数组区间加区间求和”一样，在维护一个下标乘值的线段树。