单点更新
成都地区优秀IDC服务器托管提供商(成都创新互联).为客户提供专业的四川雅安服务器托管,四川各地服务器托管,四川雅安服务器托管、多线服务器托管.托管咨询专线：18982081108
/*
* @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
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
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)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区间合并
#include
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
#include
#include
#include
#include
#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;i1)
{
lisan[m++]=lisan[i-1]+1;
}
}
sort(lisan,lisan+m);
for(int i=0;i主席树
#include
#include
#include
#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
#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>1;
if(l>=r)return rt;
if(l>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);
}
}
}
}
分享文章：线段树与可持久化
分享网址：http://cdxtjz.com/article/jhdjsp.html
