差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:die_java:front_page_treeintree [2020/05/17 21:32]
wxg
+++ 2020-2021:teams:die_java:front_page_treeintree [2020/06/02 17:35] (当前版本)
fyhssgss [例题 P3332 [ZJOI2013]K大数查询]
@@ 行 1: / 行 1: @@
+**格式**：英文/公式两边接汉字注意空格，有些地方未使用公式，如 $k$，$[l,r]$。
+**内容**：写得很棒。
 =======概述=======
 树套树，就是在一个树型数据结构上，每个点不再是一个节点，而是另外一个树形数据结构。
@@ 行 14: / 行 18: @@
 为了防止内存爆找，线段树采用动态开点。
+<hidden 代码查看>
 <code cpp>
 #include<iostream>
@@ 行 93: / 行 98: @@
 }
 </code>
+</hidden>
 ===== 线段树套平衡树 =====
@@ 行 99: / 行 105: @@
 让你维护一个有序数列，有以下操作：
-.查询k在区间内的排名
+.查询 $k$ 在区间内的排名
-.查询区间内排名为k的值
+.查询区间内排名为 $k$ 的值
 .修改某一位值上的数值
-.查询k在区间内的前驱
+.查询 $k$ 在区间内的前驱
-.查询k在区间内的后继
+.查询 $k$ 在区间内的后继
 就是平衡时问题加上了区间限制。我们外层建线段树，每一个节点维护该节点包含区间的平衡树。
@@ 行 113: / 行 119: @@
 操作一和操作三对线段树上包含区间的节点全部进行操作。
-操作四，五，外层线段树区间查询，对每个包含[l,r]的节点得到的前驱/后继求一个最大值/最小值即可。
+操作四，五，外层线段树区间查询，对每个包含 $[l,r]$ 的节点得到的前驱/后继求一个最大值/最小值即可。
 操作二 我们二分答案，和操作一类似，利用小于某数的个数进行二分。复杂度多一个 $log$ 。
+<hidden 代码查看>
 <code cpp>
 #include<iostream>
@@ 行 323: / 行 330: @@
 }
 </code>
+</hidden>
+===== 线段树套线段树 =====
+==== 例题 P3332 [ZJOI2013]K大数查询 ====
+=== 题目大意 ===
+有$N$个位置，$M$个操作，操作有2种。
+  * 操作1：''%%1 a b c%%'' 在第 $a$ 个位置到第 $b$个位置，每个位置加入一个数$c$
+  * 操作2：''%%2 a b c%%'' 询问从第 $a$ 个位置到第 $b$ 个位置中第 $c$ 大的数。 $n,m\leq5*10^4,|c|\leq n$
+=== 题解 ===
+权值线段树套位置线段树。其中第一维记录权值，第二维记录位置。对于第一维线段树上的一个节点维护的权值区间 $[L, R]$ ，它所指向的那颗线段树中记录的是每个位置包含了几个值在 $[L, R]$ 范围内的数。
+之所以这题不能像上文一样用线段树套平衡树（外层记录位置，内层维护权值）的原因是：对于套在外面那一层的线段树是很难进行区间操作的，所以这题就需要换一个思路，把位置信息放在内层的线段树中。
+PS:以下代码用到了一个小技巧，就是线段树标记永久化，相比与正常线段树的pushdown,我们在路过该节点的时候把修改对答案的影响加上，这样能优化不少常数，<del>否则这题你很难卡过去</del>
+<hidden 代码查看>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+#define mem(a,b) memset(a,b,sizeof(a))
+typedef long long LL;
+typedef pair<int,int> PII;
+#define X first
+#define Y second
+inline int read()
+{
+    int x=0,f=1;char c=getchar();
+    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
+    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
+    return x*f;
+}
+const int maxn=50010,maxnode=20000005;
+int T,tp,n,tot,lc[maxnode],rc[maxnode],ql,qr,v,rt[maxn<<3];;
+LL addv[maxnode],sumv[maxnode];
+void add(int& o,int L,int R)
+{
+    if(!o)o=++tot;
+    if(ql<=L && R<=qr){sumv[o]+=(R-L+1);addv[o]++;return;}
+    int mid=L+R>>1;
+    if(ql<=mid)add(lc[o],L,mid);
+    if(qr>mid)add(rc[o],mid+1,R);
+    sumv[o]=sumv[lc[o]]+sumv[rc[o]]+addv[o]*(R-L+1);
+    return;
+}
+LL query(int o,int L,int R,LL Add)
+{
+    if(!o)
+    {
+        int l=max(L,ql),r= min(R,qr);
+        return Add*(r-l+1);
+    }
+    if(ql<=L && R<=qr) return sumv[o]+Add*(R-L+1);
+    int mid=L+R>>1;
+    LL ans=0;
+    if(ql<=mid)ans+=query(lc[o],L,mid,Add+addv[o]);
+    if(qr>mid)ans+=query(rc[o],mid+1,R,Add+addv[o]);
+    return ans;
+}
+void update()
+{
+    int o=1,L=1,R=n<<1|1;
+    while(L<R)
+    {
+        add(rt[o],1,n);
+        int mid=L+R>>1,lo=o<<1,ro=lo|1;
+        if(v<=mid)R=mid,o=lo;
+        else L=mid+1,o=ro;
+    }
+    return add(rt[o],1,n);
+}
+int query()
+{
+    int o=1,L=1,R=n<<1|1;
+    while(L<R)
+    {
+        int mid=L+R>>1,lo=o<<1,ro=lo|1;
+        LL res=query(rt[ro],1,n,0);
+        if(v<=res)L=mid+1,o=ro;
+        else R=mid,o=lo,v-=res;
+    }
+    return L;
+}
+int main()
+{
+    n=read();T=read();
+    while(T--)
+    {
+        tp=read();ql=read();qr=read();v=read();
+        if(tp==1)v+=n+1,update();
+        else if(tp==2)printf("%d\n",query()-n-1);
+    }
+    return 0;
+}
+</code>
+</hidden>
+===== 树状数组套可持久化线段树 =====
+话不多说，上题
+==== 题目 ====
+给定一个含有n个数的序列$a[1],a[2],a[3]……a[n]$，程序必须回答这样的询问：对于给定的$i,j,k$，在$a[i],a[i+1],a[i+2]……a[j]$中第$k$小的数是多少$(1≤k≤j-i+1)$，并且，你可以改变一些$a[i]$的值，改变后，程序还能针对改变后的$a$继续回答上面的问题。
+==== 题解 ====
+题目询问的是区间第 $k$ 小
+如果不考虑区间，求第 $k$ 小的话，用线段维护权值数量即可。求第 $k$ 大只需在线段树上走，如果左区间权值和 $L_v \geq k$ ，就往左走，否则往右走，直到一个叶子节点，即为答案。
+现在考虑区间，我们可以将线段树可持久化，就可以支持作差处理，如果要求一段区间 $[l,r]$ 的第 $k$ 小，我们只需在 $r$ 处的线段树和 $l - 1$ 处线段树作差后求出第 $k$ 大。
+如果还要支持单点修改，我们线段树的建立就不能单纯的在区间的基础上。如果仍然如此建树，则每次修改区间都要修改该点之后的线段树，数目是
+ $O(n)$ 的。这个时候我们可以在树状数组的每个点上建树。如此，每个点有关的线段树只有 $O(logn)$ 总复杂度降到 $O(nlog^2n)$
+<hidden 代码查看>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<algorithm>
+#define REP(i,n) for (int i = 1; i <= (n); i++)
+#define lbt(x) (x & -x)
+using namespace std;
+const int maxn = 10005,maxm = 10000005,INF = 1000000000;
+inline int read(){
+    int out = 0,flag = 1; char c = getchar();
+    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
+    while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}
+    return out * flag;
+}
+int rt[maxn],A[maxn],B[2 * maxn],n,m,tot = 1,siz,N;
+int sum[maxm],ls[maxm],rs[maxm],a[2][20];
+struct Que{int opt,l,r,k;}Q[maxn];
+int getn(int x){
+    int l = 1,r = tot,mid;
+    while (l <= r){
+        mid = l + r >> 1;
+        if (B[mid] < x) l = mid + 1;
+        else r = mid - 1;
+    }
+    return l;
+}
+void update(int& u,int l,int r,int pos,int v){
+    if (!u) u = ++siz; sum[u] += v;
+    if (l == r) return;
+    int mid = l + r >> 1;
+    if (mid >= pos) update(ls[u],l,mid,pos,v);
+    else update(rs[u],mid + 1,r,pos,v);
+}
+int query(int l,int r,int k){
+    if (l == r) return l;
+    int mid = l + r >> 1,t = 0;
+    for (int i = 1; i <= a[0][0]; i++) t += sum[ls[a[0][i]]];
+    for (int i = 1; i <= a[1][0]; i++) t -= sum[ls[a[1][i]]];
+    if (t >= k){
+        for (int i = 1; i <= a[0][0]; i++) a[0][i] = ls[a[0][i]];
+        for (int i = 1; i <= a[1][0]; i++) a[1][i] = ls[a[1][i]];
+        return query(l,mid,k);
+    }else {
+        for (int i = 1; i <= a[0][0]; i++) a[0][i] = rs[a[0][i]];
+        for (int i = 1; i <= a[1][0]; i++) a[1][i] = rs[a[1][i]];
+        return query(mid + 1,r,k - t);
+    }
+}
+void add(int u,int x,int v){while (u <= n) update(rt[u],1,tot,x,v),u += lbt(u);}
+int solve(int l,int r,int k){
+    a[0][0] = a[1][0] = 0;
+    for (int i = r; i; i -= lbt(i)) a[0][++a[0][0]] = rt[i];
+    for (int i = l - 1; i; i -= lbt(i)) a[1][++a[1][0]] = rt[i];
+    return query(1,tot,k);
+}
+int main(){
+    n = read(); m = read(); char c;
+    REP(i,n) A[i] = B[++N] = read();
+    REP(i,m){
+        c = getchar(); while (c != 'Q' && c != 'C') c = getchar();
+        if (c == 'Q') Q[i].opt = 0,Q[i].l = read(),Q[i].r = read(),Q[i].k = read();
+        else Q[i].opt = 1,Q[i].l = read(),Q[i].k = B[++N] = read();
+    }
+    sort(B + 1,B + 1 + N);
+    for (int i = 2; i <= N; i++) if (B[i] != B[tot]) B[++tot] = B[i];
+    REP(i,n) A[i] = getn(A[i]),add(i,A[i],1);
+    REP(i,m){
+        if (!Q[i].opt) printf("%d\n",B[solve(Q[i].l,Q[i].r,Q[i].k)]);
+        else{
+            Q[i].k = getn(Q[i].k);
+            add(Q[i].l,A[Q[i].l],-1);
+            A[Q[i].l] = Q[i].k;
+            add(Q[i].l,A[Q[i].l],1);
+        }
+    }
+    return 0;
+}
+</code>
+</hidden>
+以上就是树状数组套可持久化线段树的应用，通常用于一个二维空间的整体查询单点修改的操作。
+再贴一道板题
+[[https://www.luogu.com.cn/problem/P3759|[TJOI2017]不勤劳的图书管理员]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具