简易版第k大（权值线段树）

 

 

 

 

比较简单的权值线段树模板题，主要用来学一下动态开点

一般权值线段树模板AC_Code

 1 include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1e6+10;
 5 const int inf=0x3f3f3f3f;
 6 #define rep(i,first,last) for(int i=first;i<=last;i++)
 7 #define dep(i,first,last) for(int i=first;i>=last;i--)
 8 int n,q;
 9 int a[maxn];
10 int tree[maxn<<3];
11  
12 void updata(int rt,int l,int r,int pos,int val){
13     if( l==r ){
14         tree[rt]+=val;
15         return ;
16     }
17     int mid=(l+r)>>1;
18     if( pos>mid ) updata(rt<<1|1,mid+1,r,pos,val);
19     else updata(rt<<1,l,mid,pos,val);
20     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
21 }
22  
23 int Kth(int rt,int l,int r,int k){
24     if( l==r ) return l;
25     int mid=(l+r)>>1;
26     if( tree[rt<<1]<k ) return Kth(rt<<1|1,mid+1,r,k-tree[rt<<1]);
27     else return Kth(rt<<1,l,mid,k);
28 }
29  
30 int main()
31 {
32     scanf("%d%d",&n,&q);
33     rep(i,1,n){
34         scanf("%d",&a[i]);
35         updata(1,1,maxn-5,a[i],1);
36     }
37     rep(i,1,q){
38         int t,x,y;
39         scanf("%d",&t);
40         if( t==1 ){
41             scanf("%d",&x);
42             printf("%d\n",Kth(1,1,maxn-5,x));
43         }
44         else{
45             scanf("%d%d",&x,&y);
46             updata(1,1,maxn-5,a[x],-1);
47             a[x]=y;
48             updata(1,1,maxn-5,y,1);
49         }
50     }
51     return 0;
52 }

 

 

动态开点权值线段树模板AC_Code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define rep(i,first,last) for(int i=first;i<=last;i++)
 4 #define dep(i,first,last) for(int i=first;i>=last;i--)
 5 typedef long long ll;
 6 const int Rc=1e6+5;
 7 const int maxn=3e5+5;
 8 int cnt,k;
 9 int sum[maxn<<2],rc[maxn<<2],lc[maxn<<2],a[maxn];
10  
11 void updata(int &k,int l,int r,int pos,int w){
12     if(!k){
13         k=++cnt;
14     }
15     sum[k]+=w;
16     if( l==r ){
17         return ;
18     }
19     int mid=(l+r)>>1;
20     if( pos>mid ) updata(rc[k],mid+1,r,pos,w);
21     else updata(lc[k],l,mid,pos,w);
22     sum[k]=sum[rc[k]]+sum[lc[k]];
23 }
24  
25 int query(int k,int l,int r,int kth){
26     if( l==r ) return l;
27     int mid=(l+r)>>1;
28     if( sum[lc[k]]>=kth ) return query(lc[k],l,mid,kth);
29     else return query(rc[k],mid+1,r,kth-sum[lc[k]]);
30 }
31  
32 int main()
33 {
34     int n,q;
35     scanf("%d%d",&n,&q);
36     rep(i,1,n){
37         scanf("%d",&a[i]);
38         updata(k,1,Rc,a[i],1);
39     }
40     int kth;
41     while(q--){
42         int op;
43         scanf("%d",&op);
44         if( op&1 ){
45             scanf("%d",&kth);
46             printf("%d\n",query(k,1,Rc,kth));
47         }
48         else{
49             int x,y;
50             scanf("%d%d",&x,&y);
51             updata(k,1,Rc,a[x],-1);
52             a[x]=y;
53             updata(k,1,Rc,y,1);
54         }
55     }
56     return 0;
57 }

 

 可以发现动态开点比普通的节省了很多时间