Problem

传送门

一个长度为n的序列，支持一堆操作，大致操作如下：

1.k在区间的排名(由小到大)2.区间第k小；3.单点修改；4&5：k的在区间上的前驱/后继。

Solution

右边大佬说树套树很简单，就是两个基本操作套起来即可。

然后我码了一个半小时才码完。

虽然话没说错，树状数组套主席树……

但是这代码……

算了，还是太菜了……

2,3操作：

其实做法比较好理解，树状数组具有前缀性，主席树也是利用前缀

所以可以将树状数组的每一个节点上建一颗主席树

这样就可以完美的实现修改操作了

具体实现……就是把原本的树状数组一般操作改为主席树上的修改操作

询问的时候将树状数组上\(lowbit\)到的点全部带进去主席树里去询问就可以了。

以上是第2,3操作(搞了半天才完成2,3操作)

1操作：

考虑线段树的遍历过程

如果当前权值线段树的\(mid\)大于当前询问的权值k，那么我们会走向左儿子，否则往走向右儿子

而且，当我们走向右儿子时k一定大于左边的所有数

所以我们只要在此时加左子树的数的个数即可

4,5操作：

既然知道了任意数在区间里的\(rank\)前驱和后继就很好处理了

\(k\)前驱只需要查\(k\)在区间里的\(rank\)，区间排名为\(rank - 1\)的数即为所求

\(k\)的后继则需要知道\(k\)在区间中的\(rank\)与\(k\)在区间中出现的次数\(num\)，再求区间中排名为\(rank+num\)的数即可。

放一份奇丑的代码，以后再改。

Code

#include <bits/stdc++.h> using namespace std; #define DEBUG(...) fprintf(stderr, __VA_ARGS__) #define mp make_pair #define fst first #define snd second template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } inline int read(){ int res = 0, fl = 1; char r = getchar(); for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1; for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48; return res * fl; } typedef long long LL; typedef pair<int, int> pii; const int Maxn = 4e5 + 10; struct CMtree{ int ls, rs, sum; }tre[Maxn << 7]; struct SGT{ int ch[20],siz; SGT(){ siz = 0;} SGT Ls(){ SGT B; for (int i = 1; i <= siz; ++i) B.ch[i] = tre[ch[i]].ls; B.siz = siz; return B; } SGT Rs(){ SGT B; for (int i = 1; i <= siz; ++i) B.ch[i] = tre[ch[i]].rs; B.siz = siz; return B; } int sum(){ int num = 0; for (int i = 1; i <= siz; ++i) num += tre[ch[i]].sum; return num; } }; int A[Maxn], n, m, cnt, root[Maxn << 6]; int INF = 1e8 + 10; pii operator + (const pii a, const pii b){ return mp(a.fst + b.fst, a.snd + b.snd); } namespace CMT{ inline void modify(int &rt,int l, int r, int pos, int v){ if(!rt) rt = ++cnt; tre[rt].sum += v; if(l == r) return; int mid = l + r >> 1; if(mid >= pos) modify(tre[rt].ls, l, mid, pos, v); else modify(tre[rt].rs, mid + 1, r, pos, v); } inline void build(int &rt, int grt,int l, int r, int pos){ tre[rt = ++cnt] = tre[grt]; tre[rt].sum++; if(l == r) return; int mid = l + r >> 1; if(mid >= pos) build(tre[rt].ls, tre[grt].ls, l, mid, pos); else build(tre[rt].rs, tre[grt].rs, mid + 1, r, pos); } inline int Query(SGT a, SGT b, int l, int r, int k){ if(l == r) return l; int mid = l + r >> 1, t = b.Ls().sum() - a.Ls().sum(); //printf("%d %d %d %d\n", l, r, t, k); if(k <= t) return Query(a.Ls(), b.Ls(), l, mid, k); else return Query(a.Rs(), b.Rs(), mid + 1, r, k - t); } inline pii rank(SGT a, SGT b,int l,int r, int k){ if(l == r) { return mp(1,b.sum() - a.sum()); } int mid = l + r >> 1; if(k <= mid) return rank(a.Ls(), b.Ls(), l, mid, k); else return mp(b.Ls().sum() - a.Ls().sum(), 0) + rank(a.Rs(), b.Rs(), mid + 1, r, k); } } namespace BIT{ int lst[Maxn]; inline int lowbit(int x) {return x & -x;} inline void change(int pos,int a, int b){ for (; pos <= n; pos += lowbit(pos)) CMT :: modify(root[pos], 1,INF, a, -1), CMT :: modify(root[pos], 1,INF, b, 1); } inline void add(int pos,int a){ for (; pos <= n; pos += lowbit(pos)){ CMT :: build(root[pos], lst[pos], 1, INF, a), lst[pos] = root[pos]; } } inline pii Query(int l, int r, int k, bool fl){ SGT a, b; for (int i = l - 1; i > 0; i -= lowbit(i)) a.ch[++a.siz] = root[i]; for (int i = r; i > 0; i -= lowbit(i)) b.ch[++b.siz] = root[i]; if(fl) return mp(CMT :: Query(a, b, 1, INF, k), 0); else return CMT :: rank(a, b, 1, INF, k); } } void Front(int l, int r, int k) { pii Rank = BIT::Query(l, r, k, 0); if(Rank.fst == 1) printf("-2147483647\n"); else printf("%d\n",BIT::Query(l, r, Rank.fst - 1, 1).fst); } void Next(int l, int r, int k){ pii Rank = BIT::Query(l, r, k, 0); int all = r - l + 1; if(Rank.fst + Rank.snd > all) printf("2147483647\n"); else printf("%d\n",BIT::Query(l, r, Rank.fst + Rank.snd, 1).fst); } int main() { n = read(), m = read(); for (int i = 1; i <= n; ++i) A[i] = read(), BIT::add(i, A[i]); while(m--){ int opt = read(); if(opt == 3) {int pos = read(), k = read(); BIT::change(pos,A[pos],k); A[pos] = k; continue;} int l = read(), r = read(), k = read(); if(opt == 1) printf("%d\n",BIT::Query(l, r, k, 0).fst); if(opt == 2) printf("%d\n",BIT::Query(l, r, k, 1).fst); if(opt == 4) Front(l, r, k); if(opt == 5) Next(l, r, k); } return 0; }

转载于:https://www.cnblogs.com/LZYcaiji/p/10397860.html