線段樹與可持久化

單點更新

/*
*?@Author:?qin_peng
*?@Date:???2018-08-20?23:22:08
*?@Last?Modified?by:???qin_peng
*?@Last?Modified?time:?2018-08-29?23:22:34
*/
#include<bits/stdc++.h>
using?namespace?std;
typedef?long?long?ll;
typedef?unsigned?long?long?ull;
#define?lson?l,m,rt<<1
#define?rson?m+1,r,rt<<1|1
const?int?maxn=55555;
int?sum[maxn<<2]={0};
void?pushup(int?rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
void?build(int?l,int?r,int?rt)
{
????if(l==r){scanf("%d",&sum[rt]);return?;}
????int?m=(l+r)>>1;
????build(lson),build(rson);
????pushup(rt);
}
void?update(int?pos,int?val,int?l,int?r,int?rt)
{
????if(l==r)
????{
????????sum[rt]+=val;return?;
????}
????int?m=(l+r)>>1;
????if(pos<=m)update(pos,val,lson);
????else?update(pos,val,rson);pushup(rt);
}
int?query(int?L,int?R,int?l,int?r,int?rt)
{
????if(L<=l?and?r<=R)return?sum[rt];?
????int?m=(l+r)>>1;
????int?res=0;
????if(L<=m)res+=query(L,R,lson);?
????if(R>m)res+=query(L,R,rson);
????return?res;
}

區間更新

#include<bits/stdc++.h>
using?namespace?std;
typedef?long?long?ll;
typedef?unsigned?long?long?ull;
#define?lson?l,m,rt<<1
#define?rson?m+1,r,rt<<1|1
const?int?maxn=200005;
ll?sum[maxn<<2|1]={0};
ll?add[maxn<<2|1]={0};
void?pushup(int?rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
void?pushdown(int?rt,int?m)
{
????if(add[rt])
????{
????????add[rt<<1]+=add[rt];
????????add[rt<<1|1]+=add[rt];
????????sum[rt<<1]+=add[rt]*(m-(m>>1));
????????sum[rt<<1|1]+=add[rt]*(m>>1);
????????add[rt]=0;
????}
}
void?build(int?l,int?r,int?rt)
{
????if(l==r){scanf("%lld",&sum[rt]);return;}
????int?m=(l+r)>>1;
????build(lson),build(rson);
????pushup(rt);
}
void?update(int?L,int?R,int?val,int?l,int?r,int?rt)
{
????if(l>=L?and?r<=R)
????{
????????add[rt]+=val;
????????sum[rt]+=(ll)val*(r-l+1);return?;
????}
????pushdown(rt,r-l+1);
????int?m=(l+r)>>1;
????if(L<=m)update(L,R,val,lson);
????if(m<R)update(L,R,val,rson);
????pushup(rt);
}
ll?query(int?L,int?R,int?l,int?r,int?rt)
{
????if(L<=l&&R>=r)return?sum[rt];
????pushdown(rt,r-l+1);
????int?m=(l+r)>>1;
????ll?res=0;
????if(m>=L)res+=query(L,R,lson);
????if(m<R)res+=query(L,R,rson);
????return?res;
}

區間合并

#include<bits/stdc++.h>
using?namespace?std;
typedef?long?long?ll;
typedef?unsigned?long?long?ull;
#define?root?1,n,1
#define?lson?l,m,rt<<1
#define?rson?m+1,r,rt<<1|1
const?int?N=5e4+10;
int?lsum[N<<2],rsum[N<<2],head[N],n,q;
void?push_up(int?rt,int?m)
{
????lsum[rt]=lsum[rt<<1];
????rsum[rt]=rsum[rt<<1|1];
????if(lsum[rt<<1]==m-(m>>1))lsum[rt]+=lsum[rt<<1|1];
????if(rsum[rt<<1|1]==m>>1)rsum[rt]+=rsum[rt<<1];
}
void?build(int?l,int?r,int?rt)
{
????lsum[rt]=rsum[rt]=r-l+1;
????if(l==r)return?;
????int?m=l+r>>1;
????build(lson),build(rson);
}
void?update(int?p,int?val,int?l,int?r,int?rt)
{
????if(l==r){lsum[rt]=rsum[rt]=val;return;}
????int?m=l+r>>1;
????if(p<=m)update(p,val,lson);
????else?update(p,val,rson);
????push_up(rt,r-l+1);
}
int?query(int?p,int?l,int?r,int?rt)
{
????if(l==r)return?0;
????int?m=l+r?>>1;
????if(p>=m-rsum[rt<<1]+1&&p<=m+lsum[rt<<1|1])
????return?rsum[rt<<1]+lsum[rt<<1|1];
????if(p<=m)?return?query(p,lson);
????else?return?query(p,rson);
}

經典染色

#include<cstring>??
#include<algorithm>??
#include<cstdio>??
#include<cmath>??
#include<queue>??
#define?MAXN?40010??
#define?inf?0x3f3f3f3f??
using?namespace?std;??
int?li[MAXN];
int?ri[MAXN];
int?lisan[MAXN<<2];
int?tree[MAXN<<2];?
int?vis[MAXN<<2];
int?ans;
void?pushdown(int?p)
{
????tree[p<<1]=tree[(p<<1)|1]=tree[p];
????tree[p]=-1;
}
void?update(int?p,int?l,int?r,int?x,int?y,int?a)
{
????if(x<=l&&y>=r)
????{
????????tree[p]=a;
????????return?;
????}
????if(tree[p]!=-1)
????pushdown(p);
????int?mid=(l+r)>>1;???if(y<=mid)
????update(p<<1,l,mid,x,y,a);
????else?if(x>mid)
????update((p<<1)|1,mid+1,r,x,y,a);
????else
????{
????????update(p<<1,l,mid,x,mid,a);
????????update((p<<1)|1,mid+1,r,mid+1,y,a);
????}
}
void?query(int?p,int?l,int?r)
{
????if(l==r)
????{
????????if(!vis[tree[p]]&&tree[p]!=-1)
????????{
???????????ans++;
???????????vis[tree[p]]=1;
????????}
????????return?;
????}
????if(tree[p]!=-1)
????pushdown(p);
????int?mid=(l+r)>>1;
????query(p<<1,l,mid);
????query((p<<1)|1,mid+1,r);
}
int?main()??
{??
????int?t;
????scanf("%d",&t);
????int?n;
????while(t--)
????{
????????scanf("%d",&n);
????????memset(tree,-1,sizeof(tree));
????????memset(vis,0,sizeof(vis));
????????int?tot=0;
????????for(int?i=0;i<n;i++)
????????{
????????????scanf("%d%d",&li[i],&ri[i]);
????????????lisan[tot++]=li[i];
????????????lisan[tot++]=ri[i];
????????}
????????sort(lisan,lisan+tot);
????????int?m=unique(lisan,lisan+tot)-lisan;
????????int?tem=m;
????????for(int?i=1;i<tem;i++)
????????{
????????????if(lisan[i]-lisan[i-1]>1)
????????????{
????????????????lisan[m++]=lisan[i-1]+1;
????????????}
????????}
????????sort(lisan,lisan+m);
????????for(int?i=0;i<n;i++)
????????{
????????????int?x=lower_bound(lisan,lisan+m,li[i])-lisan;
????????????int?y=lower_bound(lisan,lisan+m,ri[i])-lisan;
????????????update(1,0,m-1,x,y,i);
????????}
????????ans=0;
????????query(1,0,m-1);
????????printf("%d\n",ans);
????}
????return?0;??
}

主席樹

#include<cstdio>
#include<cstring>
#include<algorithm>
#define?mid?(l+r)/2
using?namespace?std;
const?int?N?=?100010;
int?n,?q,?m,?cnt?=?0;
int?a[N],?b[N],?T[N];
int?sum[N<<5],?L[N<<5],?R[N<<5];
int?getid(int?x){return?lower_bound(b+1,b+1+m,x)-b;}
inline?int?build(int?l,?int?r)
{
????int?rt?=?++?cnt;
????sum[rt]?=?0;
????if?(l?<?r){
????????L[rt]?=?build(l,?mid);
????????R[rt]?=?build(mid+1,?r);
????}
????return?rt;
}
inline?int?update(int?pre,?int?l,?int?r,?int?x)
{
????int?rt?=?++?cnt;
????L[rt]?=?L[pre];?R[rt]?=?R[pre];?sum[rt]?=?sum[pre]+1;
????if?(l?<?r){
????????if?(x?<=?mid)?L[rt]?=?update(L[pre],?l,?mid,?x);
????????else?R[rt]?=?update(R[pre],?mid+1,?r,?x);
????}
????return?rt;
}
inline?int?query(int?u,?int?v,?int?l,?int?r,?int?k)
{
????if?(l?>=?r)?return?l;
????int?x?=?sum[L[v]]?-?sum[L[u]];
????if?(x?>=?k)?return?query(L[u],?L[v],?l,?mid,?k);
????else?return?query(R[u],?R[v],?mid+1,?r,?k-x);
}
int?main()
{
?int?t;scanf("%d",&t);
?while(t--){
??cnt=0;
?????scanf("%d%d",?&n,?&q);
?????for?(int?i?=?1;?i?<=?n;?i?++){
?????????scanf("%d",?&a[i]);
?????????b[i]?=?a[i];
?????}
?????sort(b+1,?b+1+n);
?????m?=?unique(b+1,?b+1+n)-b-1;
?????T[0]?=?build(1,?m);
?????for?(int?i?=?1;?i?<=?n;?i?++){
?????????T[i]?=?update(T[i-1],?1,?m,?getid(a[i]));
?????}
?????while?(q?--){
?????????int?x,?y,?z;
?????????scanf("%d%d%d",?&x,?&y,?&z);
?????????printf("%d\n",?b[query(T[x-1],?T[y],?1,?m,?z)]);
?????}
?}
}

動態可持久化線段樹

#include<bits/stdc++.h>
#define?me(a,x)?memset(a,x,sizeof(a))
#define?scnaf?scanf?
#define?itn?int
#define?lson?l,mid
#define?rson?mid+1,r
using?namespace?std;
const?int?o_o=6e4+5;
const?int?mod=1e9+7;
const?int?oo=0x7fffffff;
const?int?sup=0x80000000;
typedef?long?long?ll;
typedef?unsigned?long?long?ull;
int?n,m,sz;
int?Hash[o_o],a[o_o],cnt=0;
int?root[o_o<<5],T[o_o],S[o_o];
int?L[o_o<<5],R[o_o<<5],UR[o_o],UL[o_o];
struct?node{
?int?flag;
?int?id,val;
?int?l,r,k;
}Q[10005];
int?getid(int?x){return?lower_bound(Hash+1,Hash+1+sz,x)-Hash;}
int?build(int?l,int?r){
?int?rt=++cnt;
?root[rt]=0;
?int?mid=l+r>>1;
?if(l<r){
??L[rt]=build(lson);
??R[rt]=build(rson);
?}
?return?rt;
}
int?insert(int?u,int?l,int?r,int?pos,int?val){
?int?rt=++cnt;
?root[rt]=root[u]+val;
?L[rt]=L[u],R[rt]=R[u];
?int?mid=l+r>>1;
?if(l>=r)return?rt;
?if(l<r){
??if(pos<=mid)L[rt]=insert(L[u],lson,pos,val);
??else?R[rt]=insert(R[u],rson,pos,val);
?}
?return?rt;
}
void?add(int?x,int?val){
?int?id=getid(a[x]);
?for(int?i=x;i<=n;i+=i&(-i)){
??S[i]=insert(S[i],1,sz,id,val);
?}
}
int?getsum(int?x,int?flag){
?int?res=0;
?for(int?i=x;i;i&=i-1){
??if(flag)res+=root[L[UR[i]]];
??else?res+=root[L[UL[i]]];
?}
?return?res;
}
int?query(int?st,int?ed,int?u,int?v,int?l,int?r,int?k){
?int?num=getsum(ed,true)-getsum(st,false)+root[L[v]]-root[L[u]];
?int?mid=l+r>>1;
?if(l>=r)return?l;
?if(k<=num){
??for(int?i=ed;i;i&=i-1)UR[i]=L[UR[i]];
??for(int?i=st;i;i&=i-1)UL[i]=L[UL[i]];
??return?query(st,ed,L[u],L[v],lson,k);
?}else{
??for(int?i=ed;i;i&=i-1)UR[i]=R[UR[i]];
??for(int?i=st;i;i&=i-1)UL[i]=R[UL[i]];
??return?query(st,ed,R[u],R[v],rson,k-num);
?}
}
int?main(){
?int?t;cin>>t;
?while(t--){
??cnt=0;
??scanf("%d%d",&n,&m);sz=n;
??for(int?i=1;i<=n;i++)scnaf("%d",a+i),Hash[i]=a[i];
??for(int?i=1;i<=m;i++){
???char?str[2];
???scnaf("%s",str);
???if(str[0]=='Q'){
????Q[i].flag=true;
????scnaf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].k);
???}else{
????int?pos,val;
????scnaf("%d%d",&pos,&val);
????Q[i].flag=false;
????Q[i].id=pos,Q[i].val=val;
????Hash[++sz]=val;
???}
??}
??sort(Hash+1,Hash+1+sz);
??sz=unique(Hash+1,Hash+1+sz)-Hash-1;
??T[0]=build(1,sz);
??for(int?i=1;i<=n;i++)T[i]=insert(T[i-1],1,sz,getid(a[i]),1);
??for(int?i=0;i<=n;i++)S[i]=T[0];
??for(int?i=1;i<=m;i++){
???if(Q[i].flag){
????for(int?j=Q[i].r;j;j&=j-1)UR[j]=S[j];
????for(int?j=Q[i].l-1;j;j&=j-1)UL[j]=S[j];
????printf("%d\n",Hash[query(Q[i].l-1,Q[i].r,T[Q[i].l-1],T[Q[i].r],1,sz,Q[i].k)]);
???}else{
????add(Q[i].id,-1);
????a[Q[i].id]=Q[i].val;
????add(Q[i].id,1);
???}
??}
?}
}