静态主席树，动态主席树(一种可持久化线段树)

前置知识：

动态开点

study from：

静态主席树：https://blog.csdn.net/a1351937368/article/details/78884526

动态主席树：https://blog.csdn.net/WilliamSun0122/article/details/77885781

原理：

静态主席树

1~i和1~i+1的相似性

动态主席树

树状数组

记录变化

得到1~i的结果

时间上是两个log

第一个log为树状数组（k->k-lowbit(k)->...）

第二个log为每个数（k,k-lowbit(k),...）的线段树操作

静态主席树

https://www.luogu.org/problemnew/show/P3834

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <ext/rope>
 15 #include <algorithm>
 16 #include <iostream>
 17 using namespace std;
 18 #define ll long long
 19 #define minv 1e-6
 20 #define inf 1e9
 21 #define pi 3.1415926536
 22 #define nl 2.7182818284
 23 const ll mod=1e9+7;//998244353
 24 const int maxn=2e5+10;
 25 
 26 struct rec
 27 {
 28     int a,b;
 29 }f[maxn];
 30 
 31 struct node
 32 {
 33     int l,r,sum,number;
 34 }tr[maxn*20];
 35 
 36 int a[maxn],_index=0,value,tnum=0,result;
 37 int be[maxn],v[maxn];
 38 
 39 int cmp(rec a,rec b)
 40 {
 41     return a.a<b.a;
 42 }
 43 
 44 void ini_build(int l,int r)
 45 {
 46     tr[_index].sum=0;
 47     if (l==r)
 48     {
 49         tr[_index].l=0;
 50         tr[_index].r=0;
 51         tr[_index].number=++tnum;
 52     }
 53     else
 54     {
 55         int m=(l+r)>>1,cur=_index;
 56         tr[cur].l=++_index;
 57         ini_build(l,m);
 58 
 59         tr[cur].r=++_index;
 60         ini_build(m+1,r);
 61     }
 62 }
 63 
 64 void build(int l,int r,int pos)
 65 {
 66     if (l==r)
 67     {
 68         tr[_index].l=0;
 69         tr[_index].r=0;
 70         tr[_index].sum=tr[pos].sum+1;   ///not 1
 71         tr[_index].number=tr[pos].number;
 72     }
 73     else
 74     {
 75         int m=(l+r)>>1,cur=_index;
 76         tr[cur].sum=tr[pos].sum+1;
 77         if (value<=m)
 78         {
 79             tr[cur].l=++_index;
 80             tr[cur].r=tr[pos].r;
 81             build(l,m,tr[pos].l);
 82         }
 83         else
 84         {
 85             tr[cur].l=tr[pos].l;
 86             tr[cur].r=++_index;
 87             build(m+1,r,tr[pos].r);
 88         }
 89         tr[cur].sum=tr[tr[cur].l].sum+tr[tr[cur].r].sum;
 90     }
 91 }
 92 
 93 void query(int _indexl,int _indexr,int z)
 94 {
 95     if (tr[_indexl].l==0)
 96     {
 97         result=tr[_indexl].number;
 98         return;
 99     }
100     if (tr[tr[_indexr].l].sum-tr[tr[_indexl].l].sum>=z)
101         query(tr[_indexl].l,tr[_indexr].l,z);
102     else
103         query(tr[_indexl].r,tr[_indexr].r,z-tr[tr[_indexr].l].sum+tr[tr[_indexl].l].sum);
104 }
105 
106 int main()
107 {
108     int n,m,i,num,x,y,z;
109     scanf("%d%d",&n,&m);
110     for (i=1;i<=n;i++)
111     {
112         scanf("%d",&f[i].a);
113         f[i].b=i;
114     }
115     sort(f+1,f+n+1,cmp);
116     num=0;
117     f[0].a=2e9;
118     for (i=1;i<=n;i++)
119     {
120         if (f[i].a!=f[i-1].a)
121         {
122             num++;
123             v[num]=f[i].a;
124         }
125         a[f[i].b]=num;
126     }
127     be[0]=++_index;
128     ini_build(1,num);
129     for (i=1;i<=n;i++)
130     {
131         be[i]=++_index;
132         value=a[i];
133         build(1,num,be[i-1]);
134     }
135 
136     while (m--)
137     {
138         scanf("%d%d%d",&x,&y,&z);
139         query(be[x-1],be[y],z);
140         printf("%d
",v[result],m);
141     }
142     return 0;
143 }
144 /*
145 5 100
146 1 5 1 5 5
147 1 5 2
148 1 5 3
149 */

动态主席树

P2617 Dynamic Rankings

数值离散化

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=1e9+7;
 14 const int maxn=1e5+10;
 15 const int maxm=1e5+10;
 16 
 17 /**
 18 T*m*log(n)*log(value_range)
 19 1*1e5*17*18=
 20 **/
 21 
 22 /**
 23 离散化，减少范围
 24 可减少空间，时间
 25 
 26 1e9->1e5+1e5
 27 log
 28 30(actually slight larger)->18
 29 **/
 30 
 31 int maxv=1e5+1e5;
 32 
 33 struct node
 34 {
 35     int l,r,siz;
 36 }f[(maxn+maxm)*17*20];
 37 ///17:log(n) 20:log(value_range)
 38 
 39 int be[maxn],a[maxn],num[maxn],add[maxn],id;
 40 ///num: max log(n)*2
 41 
 42 int in[maxm][3];
 43 char in_mode[maxm][5];
 44 
 45 struct rec
 46 {
 47     int x,y;
 48     bool operator<(const rec &b) const
 49     {
 50         return x<b.x;
 51     }
 52 }ls[maxn+maxm];
 53 int value_rev[maxn+maxm];
 54 
 55 void update(int ind,int l,int r,int x,int y)
 56 {
 57     f[ind].siz+=y;
 58     if (l==r)   ///not l==x
 59         return;
 60     int m=(l+r)>>1;
 61     if (x<=m)
 62     {
 63         if (!f[ind].l)
 64         {
 65             f[ind].l=++id;
 66             f[id].l=f[id].r=f[id].siz=0;    ///init
 67         }
 68         update(f[ind].l,l,m,x,y);
 69     }
 70     else
 71     {
 72         if (!f[ind].r)
 73         {
 74             f[ind].r=++id;
 75             f[id].l=f[id].r=f[id].siz=0;    ///init
 76         }
 77         update(f[ind].r,m+1,r,x,y);
 78     }
 79 }
 80 
 81 int main()
 82 {
 83     char mode[5];
 84     int t,n,m,i,j,k,pos,g,l,r,v,M,cnt_ls;
 85     t=1;
 86 //    scanf("%d",&t);
 87     while (t--)
 88     {
 89 //        memset(f,0,sizeof(f));  ///or each point initialize
 90 
 91         scanf("%d%d",&n,&m);
 92         for (i=1;i<=n;i++)
 93         {
 94             be[i]=i;
 95             f[i].l=f[i].r=f[i].siz=0;
 96         }
 97         id=n;
 98 
 99         for (i=1;i<=n;i++)
100         {
101             scanf("%d",&a[i]);
102             ls[i]={a[i],i};
103         }
104         cnt_ls=n;
105         for (M=1;M<=m;M++)
106         {
107             scanf("%s",in_mode[M]);
108             if (in_mode[M][0]=='Q')
109                 scanf("%d%d%d",&in[M][0],&in[M][1],&in[M][2]);
110             else
111             {
112                 scanf("%d%d",&in[M][0],&in[M][1]);
113                 ls[++cnt_ls]={in[M][1],n+M};
114             }
115         }
116 
117         sort(ls+1,ls+cnt_ls+1);
118         pos=0;
119         ls[0].x=ls[1].x-1;
120         for (i=1;i<=cnt_ls;i++)
121         {
122             if (ls[i].x!=ls[i-1].x)
123             {
124                 pos++;
125                 value_rev[pos]=ls[i].x;
126             }
127             if (ls[i].y<=n)
128                 a[ls[i].y]=pos;
129             else
130                 in[ls[i].y-n][1]=pos;
131         }
132 
133         for (i=1;i<=n;i++)
134         {
135 //            scanf("%d",&a[i]);
136             k=i;
137             while (k<=n)
138             {
139                 update(be[k],1,maxv,a[i],1);
140                 k+=k&-k;
141             }
142         }
143 
144         for (M=1;M<=m;M++)
145 //        while (m--)
146         {
147 //            scanf("%s",mode);
148             strcpy(mode,in_mode[M]);
149             if (mode[0]=='Q')
150             {
151 //                scanf("%d%d%d",&i,&j,&pos);
152                 i=in[M][0],j=in[M][1],pos=in[M][2];
153                 g=0;
154 
155                 k=i-1;
156                 while (k)
157                 {
158                     num[++g]=be[k];
159                     add[g]=-1;
160                     k-=k&-k;
161                 }
162 
163                 k=j;
164                 while (k)
165                 {
166                     num[++g]=be[k];
167                     add[g]=1;
168                     k-=k&-k;
169                 }
170 
171                 l=1,r=maxv;///也可以设置叶子标志
172                 while (l!=r)
173                 {
174                     v=0;
175                     for (i=1;i<=g;i++)
176                         v+=f[f[num[i]].l].siz*add[i];
177                     if (v>=pos)
178                     {
179                         for (i=1;i<=g;i++)
180                             num[i]=f[num[i]].l;
181                         r=(l+r)>>1;
182                     }
183                     else
184                     {
185                         pos-=v;
186                         for (i=1;i<=g;i++)
187                             num[i]=f[num[i]].r;
188                         l=((l+r)>>1)+1;
189                     }
190                 }
191                 printf("%d
",value_rev[l]);
192             }
193             else
194             {
195 //                scanf("%d%d",&i,&j);
196                 i=in[M][0],j=in[M][1];
197 
198                 k=i;
199                 while (k<=n)
200                 {
201                     update(be[k],1,maxv,a[i],-1);
202                     update(be[k],1,maxv,j,1);
203                     k+=k&-k;
204                 }
205                 a[i]=j;
206             }
207         }
208     }
209 
210     return 0;
211 }
212 /*
213 1
214 5 13
215 100000000 100000000 100000000 100000000 100000000
216 Q 1 5 1
217 Q 1 5 2
218 Q 1 5 3
219 Q 1 5 4
220 Q 1 5 5
221 C 3 10123445
222 Q 1 5 1
223 Q 1 5 2
224 Q 1 5 3
225 Q 1 5 4
226 Q 1 5 5
227 Q 2 2 1
228 Q 3 3 1
229 */

不离散化，TLE了

==============================

不同的数据范围

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2112

使用上述方法，会超空间

空间优化：

读入a[1]~a[n]，

使用静态主席树的方式建树

n[5e4]*log(value_range)[18]

然后对于每个询问（与之前一样）

m[1e4]*2[修改数字，删除原来，增加现在]*log(n)[16]*log(value_range)[18]

即使优化了，然而还是会超空间的，感觉数据不严谨。