可持久化数据结构

起因是16长春CCPC遇到了一个全场万人过的主席树题目，然而我不会orz，哭哭 可持久化线段树的本质是很多棵形态完全相同的线段树。 也可以理解成是，保存了不同时刻版本的线段树的数据结构。

题目链接 题意： # 给定一个序列 n，有 m次查询，每次查询一个区间[l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。

Description # 给定一个含有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大数 思路： # 可持久化线段树。

题目链接 题意：给出 n 个数，然后 m 个询问，每个询问一个区间 [l,r]，问该区间中不同的数有多少个。 思路：离线处理+线段树的做法不多说了： 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :Fri 16 Sep 2016 11:34:32 PM CST 4File Name :code/spoj/dquery.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=3E4+7; 32const int M=2E5+7; 33int n,Q; 34int a[N]; 35int tree[N<<2]; 36map<int,int>mp; 37struct node 38{ 39 int l,r; 40 int id; 41 bool operator < (node b)const 42 { 43 if (r==b.r) return l<b.l; 44 return r<b.r; 45 } 46}q[M]; 47void PushUp( int rt) 48{ 49 tree[rt] = tree[rt<<1] + tree[rt<<1|1]; 50} 51void update( int p,int sc,int l,int r ,int rt) 52{ 53 if (l==r) 54 { 55 tree[rt]+=sc; 56 return; 57 } 58 int m = (l+r)>>1; 59 if (p<=m) update(p,sc,lson); 60 else update(p,sc,rson); 61 PushUp(rt); 62} 63int query(int L,int R,int l,int r,int rt) 64{ 65 if (L<=l&&r<=R) return tree[rt]; 66 int m = (l+r)>>1; 67 int ret = 0 ; 68 if (L<=m) ret += query(L,R,lson); 69 if (R>=m+1) ret+=query(L,R,rson); 70 return ret; 71} 72int ans[M]; 73int main() 74{ 75 #ifndef ONLINE_JUDGE 76 freopen("code/in.txt","r",stdin); 77 #endif 78 cin>>n; 79 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]); 80 cin>>Q; 81 for ( int i = 1 ; i <= Q ; i++) scanf("%d %d",&q[i].l,&q[i].r),q[i].id = i ; 82 sort(q+1,q+Q+1); 83 int cur = 1; 84 for ( int i = 1 ; i <= Q ; i++) 85 { 86 for ( ; cur <= q[i].r ; cur++) 87 { 88 if (mp[a[cur]]) update(mp[a[cur]],-1,1,n,1); 89 mp[a[cur]] = cur; 90 update(mp[a[cur]],1,1,n,1); 91 } 92 ans[q[i].id] = query(q[i].l,q[i].r,1,n,1); 93 } 94 for ( int i = 1 ; i <= Q ; i++) printf("%d\n",ans[i]); 95 #ifndef ONLINE_JUDGE 96 fclose(stdin); 97 #endif 98 return 0; 99} 之后补一个主席树的做法