相信各位都在OI的比赛中因为分数没有达到分数线而错失省一和保送名额。保送肯定人人都想,但分数怎么搞呢?
神犇可能直接上手打AC,而蒟蒻只能在一旁默默的WA
这时候就应该由泉一学府wyx带来新排版《骗分导论》了
相信各位都在OI的比赛中因为分数没有达到分数线而错失省一和保送名额。保送肯定人人都想,但分数怎么搞呢?
神犇可能直接上手打AC,而蒟蒻只能在一旁默默的WA
这时候就应该由泉一学府wyx带来新排版《骗分导论》了
在wmf大佬怂恿
一天学习一个数据结构每天划水下,大概理清可持久化线段树,又名主席树的大致思路和代码实现。今天JZ的雨,下得更加的猛烈了QAQ
先来一波可持久化线段树,又名主席树。在可持久化数据结构中,能够支持查询历史版本的数据。是对原数据结构的进一步加深与理解,代码和原理也只能算是锦上添花。借用某大犇的话讲就是,“主席树难不是在于它自身,而是难在于如何把一道题跟它扯上关系”
下面进入正题:
在某些题目中,我们可能需要不断地对线段树修改,并且有可能需要查询的是某一次修改前的事情,而在线段树中,修改即意味着是数据丢失,是难以查询到从前的东西。而可持久化的基本理念就是不将其修改,而是扩建。
初步的想法是对于一次修改就重新搞一棵树出来,但是这在空间上是极度不允许的。我们能够联想到,对于一次修改,复杂度是log(n)级别的,这说明了一次修改所涉及到的区间只有log(n)个,故我们没有必要每次完整地建一棵线段树,只需要新建log(n)个被修改的区间,其他的未被操刀过的区间借用前者的区间即可。每一次修改扩建log(n)个,这是能够勉强接受的。
在此顺便注一句:一定要计算好空间!!!不要像我一样空间算错了开太小然后查了一小时错都没查出来!!!!!!!!后来跟标程一字一字进行了一场“代码优先性逐行逐字比较型工程”才发现标程空间比我多了一点点......
【代码环节】
例题:洛谷P3834
这是我阅览了十多份代码中,风格最为人性化的一种
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67 #include<cstdio>
#include<algorithm>
#include<iostream>
#define mid (l+r)/2
#define N 200005
using namespace std;
struct node
{
int val,id;
};
struct chariman
{
int l,r;
int sum;
}tree[N*20];
bool cmp(node aa,node bb)
{
return aa.val<bb.val;
}
int n,q,a[N],root[N],cnt;
node b[N];
void updata(int &st,int l,int r,int p)
{
tree[++cnt]=tree[st];
st=cnt;
tree[st].sum++;
if (l==r) return;
if (p<=mid) updata(tree[st].l,l,mid,p);
else updata(tree[st].r,mid+1,r,p);
return;
}
int query(int i,int j,int k,int l,int r)
{
if (l==r) return l;
int ltot=tree[tree[j].l].sum-tree[tree[i].l].sum;
if (k<=ltot) return query(tree[i].l,tree[j].l,k,l,mid);
else return query(tree[i].r,tree[j].r,k-ltot,mid+1,r);
}
int main()
{
scanf("%d %d",&n,&q);
for (int i=1; i<=n; i++)
{
scanf("%d",&b[i].val);b[i].id=i;
}
sort(b+1,b+1+n,cmp);
for (int i=1; i<=n; i++) a[b[i].id]=i;
for (int i=1; i<=n; i++)
{
root[i]=root[i-1];
updata(root[i],1,n,a[i]);
}
int x,y,k;
while (q--)
{
scanf("%d %d %d",&x,&y,&k);
printf("%d\n",b[query(root[x-1],root[y],k,1,n)].val);
}
return 0;
}
【PAUSE】
【最长上升子序列】
题意:对一个序列进行操作,可以在序列最后加上一个数,可以回到k时的序列,求每次操作后序列的最长上升子序列长度。
【LIS求法】:通常求最长上升子序列都是n^2动规,当n较大时便要考虑nlogn的算法。
设f[k]表示长度为k的LIS最末尾的元素,易知f是单调递增的,对于新加入的x,如果f[k] < x, 意味着最长上升子序列的长度可以加1。如果f[k] > x,那么 对于f[i] > x > f[i - 1]考虑f第i位的值哪个更优?显然要取x。求i可以用二分优化,LIS便能在nlongn的时间内求出。
这题需要回到第k时的序列,由上述算法可知,对于操作j、j - 1,f数组的变化只有一个数,于是用可持久化线段树来维护这个数组,使修改和查询的时间变成logn, 时间复杂度是O(nlog^2n)。
由于时间复杂度和空间复杂度与题目要求十分相近,要考虑常数与每个结点的线段树子节点数量。
正解对于每个回到k序列的操作建一棵树,直接在这棵树上跑LIS,时间复杂度O(nlogn)。
【图的X匹配】
题意:对于一个多边形,使取出的边没有交点(即没有相邻的边)的方案数。
打表可以发现答案的规律类似斐波那契数列, 由于没有取模, 需要用高精度完成加法操作, n的值最大为10000, 最好用滚动数组。
证明:
【努力】
题意:使n个点形成一棵树的连边方法。
由prufer数列可得n个点的无向图有n^(n-2)种, n个点的树有n-1条边,答案便是n^(n-2)*(n-1)!。
代码如下:
【匹配】
简单的模拟题,这里略过。
【矩形】
题意:给出n条直线,求组成的矩形个数。
60%的做法,先枚举两条平行的直线,再枚举垂直于前两条直线且有交点的线,用排列组合求出答案。这个做法是O(n^3)。
由数据范围可知O(n^3)的时间复杂度刚好超时,考虑优化上面的算法,用bitset记录每两条直线是否相交,那么,求垂直于两条直线且相交就变成了求两条直线bitset的和(&)。由于直线分为两种,垂直于x轴与平行于x轴,可以枚举直线少的来进行&操作。时间复杂的为O(n^3/128)。
正解为树状数组(线段树)来维护两条平行直线间共有的相交直线数。时间复杂度O(n^2longn)。
【历史】
题意:每次连一条边,询问两个点是否在t之前不联通,在当前时刻联通,强制在线。
由于强制在线的是连接的边,对于询问并没有要求强制在线,那么,先将询问存下来,对于t之前的状态可在t时记录,t的状态可直接得到。
正解是可持久化并查集, 用可持久化线段树维护可持久化数组,由于修改的只能是一个数,所以合并并查集时不能用路径压缩,需要用启发式合并,那么,对于每个询问只需查找当前数组和前t的数组即可。
代码如下(可持久化并查集代码明天补充)
主席树又称函数式线段树,就是通过函数来实现的线段树,可以处理一些神奇的问题。
【例题】K-th Number
1
2
3
4
5
6
7
8
9 void add(int &cnt, int last, int l, int r, int v) {
cnt = ++tot;
tr[cnt] = tr[last];
tr[cnt].sum++;
if (l < r) {
if (v <= (l + r) / 2) add(tr[cnt].ls, tr[last].ls, l, (l + r) / 2, v);
else add(tr[cnt].rs, tr[last].rs, (l + r) / 2 + 1, r, v);
}
}
那么对于每一个询问,代码就显而易见了:
1
2
3
4
5
6
7 int que(int pas, int now, int l, int r, int k) {
if (l == r) return l;
int s = tr[tr[now].ls].sum - tr[tr[pas].ls].sum;
if (k <= s) return que(tr[pas].ls, tr[now].ls, l, (l + r) / 2, k);
return que(tr[pas].rs, tr[now].rs, (l + r) / 2 + 1, r, k - s);
}
具体代码如下:
树状数组套主席树。
考虑无修改求区间第 K 大的情况:因为主席树之间支持相加减,故可以维护一些包含 1~i 的线段树,计算它们的树前缀和,从而快速得到区间 [l, r] 中的第 K 大数。
考虑对于数的静态区间和与动态区间和的关系——前缀和与树状数组。
类似地,我们可以维护一个树状数组,但线段树记录的不再是前缀和,而是树状数组的辅助数组的值。
这样就能做到带修改的区间第 K 大值查询了。
Reference:
http://blog.csdn.net/u014664226/article/details/47839973
代码如下:
求树上路径上节点权值k小。
可以发现树上两点u,v之间的第k小点权等价于(root <-> u) + (root <-> v) - (root <-> lca(u, v)) - (root <-> father[lca(u, v)])上的第k小点权,其中root为根节点,lca(u, v)为u和v的最近公共祖先,father[lca(u, v)]为lca(u, v)的父节点。
那么可以维护root到所有节点的权值,显然root到某个点x的权值和root到x父节点的权值只有点x这个点权的差别,那么可以用主席树维护这个东西了。
10%:枚举每个数字作为神秘数,搜索判断
30%:显然可以发现一个性质:假设当前神秘数为ans,那么可以被表示的区间为[1, ans - 1]。若加入一个数x,且x满足1x
ans + 1,则神秘数变为ans + x。初始的神秘数为0。那么对于每个询问,将区间内的数排序,依次判断即可。
60%:迷之写法,或者是写丑的100%。
100%:30%的方法不容易维护,考虑对于一个数x,若x不可被表示,条件为区间内所有小于x的数的和小于x,这个东西可以用树套树或者主席树维护。(看神犇们的代码好像可以不用离散化,时间少一个log