线段树与可持久化
单点更新
/** @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|1const 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|1const 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|1const 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)/2using 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,rusing 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); } } }}
声明：本站所有文章资源内容，如无特殊说明或标注，均为采集网络资源。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
