P3369 【模板】普通平衡树
#include <bits/stdc++.h>
#define int long long
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;
const int N = 1e5+5;
const int MOV = 1e7;
struct node{
int v,l,r;
} t[N<<4];
int tot,root;
inline void newnode(int &i){
if(!i) i=(++tot);
}
void update(int p,int v,int &i,int l,int r){
newnode(i);
t[i].v+=v;
if(l==r){
if(t[i].v<0) t[i].v=0;
return;
}
if(p<=mid) update(p,v,ls,l,mid);
else update(p,v,rs,mid+1,r);
}
int rnk(int ql,int qr,int &i,int l,int r){
if(!i) return 0;
if(ql<=l&&r<=qr) return t[i].v;
int ans=0;
if(ql<=mid) ans+=rnk(ql,qr,ls,l,mid);
if(qr>mid) ans+=rnk(ql,qr,rs,mid+1,r);
return ans;
}
int kth(int k,int &i,int l,int r){
if(l==r) return l;
if(t[ls].v>=k) return kth(k,ls,l,mid);
else return kth(k-t[ls].v,rs,mid+1,r);
}
int n;
signed main(){
cin>>n;
while(n--){
int op,x;
cin>>op>>x;
if(op==1) update(x+MOV,1,root,1,MOV<<1);
if(op==2) update(x+MOV,-1,root,1,MOV<<1);
if(op==3) cout<<(rnk(1,x+MOV-1,root,1,MOV<<1)+1)<<'\n';
if(op==4) cout<<(kth(x,root,1,MOV<<1)-MOV)<<'\n';
if(op==5) cout<<(kth(rnk(1,x+MOV-1,root,1,MOV<<1),root,1,MOV<<1)-MOV)<<'\n';
if(op==6) cout<<(kth(rnk(1,x+MOV,root,1,MOV<<1)+1,root,1,MOV<<1)-MOV)<<'\n';
}
return 0;
}
P3834 【模板】可持久化线段树 2
#include <bits/stdc++.h>
#define int long long
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;
const int N = 2e5+5;
struct node{
int v,l,r;
} t[N<<5];
int tot,root[N];
inline void newnode(int &i){
t[++tot]=t[i];i=tot;
}
void update(int p,int v,int &i,int l,int r){
newnode(i);
t[i].v+=v;
if(l==r) return;
if(p<=mid) update(p,v,ls,l,mid);
else update(p,v,rs,mid+1,r);
}
int query(int ql,int qr,int k,int l,int r){
if(l==r) return l;
int delta=t[t[qr].l].v-t[t[ql].l].v;
if(delta>=k) return query(t[ql].l,t[qr].l,k,l,mid);
else return query(t[ql].r,t[qr].r,k-delta,mid+1,r);
}
int n,m,a[N],b[N];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) b[i]=a[i];
sort(b+1,b+n+1);
int top=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){
int p=root[i-1];
update(lower_bound(b+1,b+top+1,a[i])-b,1,root[i-1],1,top);
root[i]=root[i-1],root[i-1]=p;
}
while(m--){
int l,r,k;
cin>>l>>r>>k;
cout<<b[query(root[l-1],root[r],k,1,top)]<<'\n';
}
return 0;
}
P3567 [POI2014]KUR-Couriers
#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;
const int N = 5e5+5;
struct node{
int v,l,r;
} t[N<<5];
int tot,root[N];
inline void newnode(int &i){
t[++tot]=t[i];i=tot;
}
void update(int p,int v,int &i,int l,int r){
newnode(i);
t[i].v+=v;
if(l==r) return;
if(p<=mid) update(p,v,ls,l,mid);
else update(p,v,rs,mid+1,r);
}
int query(int ql,int qr,int v,int l,int r){
if(l==r) return l;
int lsiz=t[t[qr].l].v-t[t[ql].l].v,rsiz=t[t[qr].r].v-t[t[ql].r].v;
if((lsiz<<1)>v) return query(t[ql].l,t[qr].l,v,l,mid);
if((rsiz<<1)>v) return query(t[ql].r,t[qr].r,v,mid+1,r);
return 0;
}
int n,m,a[N];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
int p=root[i-1];
update(a[i],1,root[i-1],1,n);
root[i]=root[i-1],root[i-1]=p;
}
while(m--){
int l,r;
cin>>l>>r;
cout<<query(root[l-1],root[r],r-l+1,1,n)<<'\n';
}
return 0;
}
P1972 [SDOI2009] HH的项链
#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;
const int N = 1e6+5;
struct node{
int v,l,r;
} t[N<<5];
int tot,root[N];
inline void newnode(int &i){
t[++tot]=t[i];i=tot;
}
int update(int p,int v,int i,int l,int r){
newnode(i);
t[i].v+=v;
if(l==r) return i;
if(p<=mid) ls=update(p,v,ls,l,mid);
else rs=update(p,v,rs,mid+1,r);
return i;
}
int query(int ql,int qr,int vl,int vr,int l,int r){
if(ql<=l&&r<=qr) return t[vr].v-t[vl].v;
int res=0;
if(ql<=mid) res+=query(ql,qr,t[vl].l,t[vr].l,l,mid);
if(qr>mid) res+=query(ql,qr,t[vl].r,t[vr].r,mid+1,r);
return res;
}
int n,m,a[N],last[N],top[N];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
last[i]=top[a[i]];
top[a[i]]=i;
}
for(int i=1;i<=n;i++) root[i]=update(last[i],1,root[i-1],0,n);
cin>>m;
while(m--){
int l,r;
cin>>l>>r;
cout<<(r-l+1-query(l,r,root[l-1],root[r],0,n))<<'\n';
}
return 0;
}
P4587 [FJOI2016]神秘数
#include <bits/stdc++.h>
#define int long long
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;
const int N = 2e5+5;
struct node{
int v,l,r;
} t[N<<5];
int tot,root[N];
inline void newnode(int &i){
t[++tot]=t[i];i=tot;
}
int update(int p,int v,int i,int l,int r){
newnode(i);
t[i].v+=v;
if(l==r) return i;
if(p<=mid) ls=update(p,v,ls,l,mid);
else rs=update(p,v,rs,mid+1,r);
return i;
}
int query(int ql,int qr,int vl,int vr,int l,int r){
if(ql<=l&&r<=qr) return t[vr].v-t[vl].v;
int res=0;
if(ql<=mid) res+=query(ql,qr,t[vl].l,t[vr].l,l,mid);
if(qr>mid) res+=query(ql,qr,t[vl].r,t[vr].r,mid+1,r);
return res;
}
int n,m,a[N];
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) root[i]=update(a[i],a[i],root[i-1],1,1e9);
cin>>m;
while(m--){
int ans=1,l,r;
cin>>l>>r;
while(1){
int res=query(1,ans,root[l-1],root[r],1,1e9);
if(res>=ans) ans=res+1;
else break;
}
cout<<ans<<'\n';
}
return 0;
}
P3293 [SCOI2016]美味
#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;
const int N = 2e5+5;
struct node{
int v,l,r;
} t[N<<5];
int tot,root[N];
int update(int p,int v,int i,int l,int r){
t[++tot]=t[i];i=tot;
t[i].v+=v;
if(l==r) return i;
if(p<=mid) ls=update(p,v,ls,l,mid);
else rs=update(p,v,rs,mid+1,r);
return i;
}
int query(int ql,int qr,int vl,int vr,int l,int r){
if(qr<l||ql>r) return 0;
if(ql<=l&&r<=qr) return t[vr].v-t[vl].v;
int res=0;
if(ql<=mid) res+=query(ql,qr,t[vl].l,t[vr].l,l,mid);
if(qr>mid) res+=query(ql,qr,t[vl].r,t[vr].r,mid+1,r);
return res;
}
int n,m,a[N];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int N = *max_element(a+1,a+n+1);
for(int i=1;i<=n;i++) root[i]=update(a[i],1,root[i-1],0,N);
while(m--){
int b,x,l,r,ans=0;
cin>>b>>x>>l>>r;
for(int i=20;~i;i--){
if(b&(1<<i)){
if(!query(ans-x,ans-x+((1<<i)-1),root[l-1],root[r],0,N)) ans+=(1<<i);
}
else{
if(query(ans-x+(1<<i),ans-x+((1<<(i+1))-1),root[l-1],root[r],0,N)) ans+=(1<<i);
}
}
cout<<(ans^b)<<'\n';
}
return 0;
}
P2617 Dynamic Rankings
#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;
const int N = 1e6+5;
int n,m;
int a[N];
struct node{
int v,l,r;
} t[N<<5];
int tot,root[N];
void update(int p,int v,int &i,int l,int r){
if(!i) i=(++tot);
t[i].v+=v;
if(l==r) return;
if(p<=mid) update(p,v,ls,l,mid);
else update(p,v,rs,mid+1,r);
}
inline int lowbit(int x){return x&(-x);}
void update(int p,int v){
for(int i=p;i<=n;i+=lowbit(i)) update(a[p],-1,root[i],0,1e9);
a[p]=v;
for(int i=p;i<=n;i+=lowbit(i)) update(a[p],1,root[i],0,1e9);
}
int lr[N],rr[N],tl,tr;
inline void split(int l,int r){
l--,tl=0,tr=0;
for(int i=l;i;i-=lowbit(i)) lr[++tl]=root[i];
for(int i=r;i;i-=lowbit(i)) rr[++tr]=root[i];
}
int kth(int k,int l,int r){
if(l==r) return l;
int siz=0;
for(int i=1;i<=tl;i++) siz-=t[t[lr[i]].l].v;
for(int i=1;i<=tr;i++) siz+=t[t[rr[i]].l].v;
if(k<=siz){
for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].l;
for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].l;
return kth(k,l,mid);
}
else{
for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].r;
for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].r;
return kth(k-siz,mid+1,r);
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int j=1;j<=n;j++){
cin>>a[j];
for(int i=j;i<=n;i+=lowbit(i)) update(a[j],1,root[i],0,1e9);
}
while(m--){
char op;int x,y,z;
cin>>op>>x>>y;
if(op=='Q'){
cin>>z;
split(x,y);cout<<kth(z,0,1e9)<<'\n';
}
else update(x,y);
}
return 0;
}
P3380 【模板】二逼平衡树(树套树)
#include <bits/stdc++.h>
#define ls (t[i].l)
#define rs (t[i].r)
#define mid ((l+r)>>1)
using namespace std;
const int N = 1e5+5, INF = 2147483647;
int n,m;
int a[N],b[N],btot;
struct node{
int v,l,r;
} t[N<<10];
int tot,root[N];
void update(int p,int v,int &i,int l,int r){
if(!i) i=(++tot);
t[i].v+=v;
if(l==r) return;
if(p<=mid) update(p,v,ls,l,mid);
else update(p,v,rs,mid+1,r);
}
inline int lowbit(int x){return x&(-x);}
void update(int p,int v,bool clear=true){
if(clear){for(int i=p;i<=n;i+=lowbit(i)) update(a[p],-1,root[i],1,btot);}
a[p]=v;
for(int i=p;i<=n;i+=lowbit(i)) update(a[p],1,root[i],1,btot);
}
int lr[N],rr[N],tl,tr;
inline void split(int l,int r){
l--,tl=0,tr=0;
for(int i=l;i;i-=lowbit(i)) lr[++tl]=root[i];
for(int i=r;i;i-=lowbit(i)) rr[++tr]=root[i];
}
int kth(int k,int l=1,int r=btot){
if(l==r) return l;
int siz=0;
for(int i=1;i<=tl;i++) siz-=t[t[lr[i]].l].v;
for(int i=1;i<=tr;i++) siz+=t[t[rr[i]].l].v;
if(k<=siz){
for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].l;
for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].l;
return kth(k,l,mid);
}
else{
for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].r;
for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].r;
return kth(k-siz,mid+1,r);
}
}
int rnk(int v,int l=1,int r=btot){
if(l==r) return 1;
if(v<=mid){
for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].l;
for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].l;
return rnk(v,l,mid);
}
else{
int siz=0;
for(int i=1;i<=tl;i++) siz-=t[t[lr[i]].l].v;
for(int i=1;i<=tr;i++) siz+=t[t[rr[i]].l].v;
for(int i=1;i<=tl;i++) lr[i]=t[lr[i]].r;
for(int i=1;i<=tr;i++) rr[i]=t[rr[i]].r;
return siz+rnk(v,mid+1,r);
}
}
struct Query{
int op,x,y,z;
} qs[N];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int j=1;j<=n;j++){
cin>>a[j];
b[++btot]=a[j];
}
for(int j=1;j<=m;j++){
cin>>qs[j].op>>qs[j].x>>qs[j].y;
if(qs[j].op!=3){
cin>>qs[j].z;
if(qs[j].op!=2) b[++btot]=qs[j].z;
}
else b[++btot]=qs[j].y;
}
sort(b+1,b+btot+1);
btot=unique(b+1,b+btot+1)-b-1;
for(int i=1;i<=n;i++){
int v=lower_bound(b+1,b+btot+1,a[i])-b;
update(i,v,false);
}
for(int i=1;i<=m;i++){
int op=qs[i].op,x=qs[i].x,y=qs[i].y,z=qs[i].z;
if(op!=2&&op!=3) z=lower_bound(b+1,b+btot+1,z)-b;
if(op==3) y=lower_bound(b+1,b+btot+1,y)-b;
if(op==1){
split(x,y);cout<<rnk(z)<<'\n';
}
if(op==2){
split(x,y);cout<<b[kth(z)]<<'\n';
}
if(op==3) update(x,y);
if(op==4){
split(x,y);
int pre=rnk(z);
if(pre==1) cout<<(-INF)<<'\n';
else{
split(x,y);cout<<b[kth(pre-1)]<<'\n';
}
}
if(op==5){
split(x,y);
int pre=rnk(z+1);
split(x,y);
int nxt=kth(pre);
if(nxt!=z&&pre<=(y-x+1)) cout<<b[nxt]<<'\n';
else cout<<INF<<'\n';
}
}
return 0;
}
标签:return,int,线段,mid,cin,详解,ls,权值,define
From: https://www.cnblogs.com/zheyuanxie/p/wsgt-codes.html