广东品牌网站建设公司,上海装修公司投诉排行,太原市建设工程招投标信息网站,wordpress 播放大视频教程正题
题目链接:https://www.luogu.com.cn/problem/P3835 题目大意
一个空可重集#xff0c;要求支持
插入一个数xxx删除一个数xxx询问一个数xxx的排名询问排名第xxx的数字询问xxx的前驱询问xxx的后继
但是所有操作都是基于某个历史版本 1≤n≤5105,1≤∣x∣≤1091\leq n\l…正题
题目链接:https://www.luogu.com.cn/problem/P3835 题目大意
一个空可重集要求支持
插入一个数xxx删除一个数xxx询问一个数xxx的排名询问排名第xxx的数字询问xxx的前驱询问xxx的后继
但是所有操作都是基于某个历史版本
1≤n≤5×105,1≤∣x∣≤1091\leq n\leq 5\times 10^5,1\leq |x|\leq 10^91≤n≤5×105,1≤∣x∣≤109 解题思路
挺好写的就是一个FHQFHQFHQ可持久化部分分裂和主席树差不多合并和线段树合并差不多。 空间记得开大点。
时空间复杂度都是O(nlogn)O(n\log n)O(nlogn)的。 code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N3e710;
int n,rt[510000];
struct FHQ{int cnt,w[N],siz[N],rnk[N],t[N][2];int NewNode(int val){w[cnt]val;siz[cnt]1;rnk[cnt]rand();return cnt;}void PushUp(int x){siz[x]siz[t[x][0]]siz[t[x][1]]1;return;}void Cpy(int x,int y){siz[x]siz[y];rnk[x]rnk[y];w[x]w[y];t[x][0]t[y][0];t[x][1]t[y][1];return;}void Split(int x,int y,int p,int k){if(!p){xy0;return;}int nowcnt;Cpy(now,p);if(w[p]k)xnow,Split(t[now][1],y,t[p][1],k);else ynow,Split(x,t[now][0],t[p][0],k);PushUp(now);return;}int Merge(int x,int y){if(!x||!y)return x|y;int nowcnt;if(rnk[x]rnk[y]){Cpy(now,x);t[now][1]Merge(t[x][1],y);}else{Cpy(now,y);t[now][0]Merge(x,t[y][0]);}PushUp(now);return now;}int Find(int x,int k){if(siz[t[x][0]]k)return Find(t[x][0],k);if(siz[t[x][0]]1k)return x;return Find(t[x][1],k-siz[t[x][0]]-1);}void Insert(int rt,int val){int x,y;Split(x,y,rt,val);rtMerge(Merge(x,NewNode(val)),y);return;}void Delete(int rt,int val){int x,y,z;Split(x,z,rt,val);Split(x,y,x,val-1);yMerge(t[y][0],t[y][1]);rtMerge(Merge(x,y),z);return;}int GetRank(int rt,int val){int x,y;Split(x,y,rt,val-1);return siz[x]1;}int GetVal(int rt,int rk){return w[Find(rt,rk)];}int GetPre(int rt,int val){int x,y;Split(x,y,rt,val-1);return w[Find(x,siz[x])];}int GetNxt(int rt,int val){int x,y;Split(x,y,rt,val);return w[Find(y,1)];}
}T;
int main()
{scanf(%d,n);T.NewNode(-2147483647);T.NewNode(2147483647);rt[0]T.Merge(1,2);for(int i1,v,op,x;in;i){scanf(%d%d%d,v,op,x);rt[i]rt[v];if(op1)T.Insert(rt[i],x);else if(op2)T.Delete(rt[i],x);else if(op3)printf(%d\n,T.GetRank(rt[i],x)-1);else if(op4)printf(%d\n,T.GetVal(rt[i],x1));else if(op5)printf(%d\n,T.GetPre(rt[i],x));else if(op6)printf(%d\n,T.GetNxt(rt[i],x));}return 0;
}
