CDQZ数据结构练习（持续更新中）

悠悠 2023-06-04 08:00 4阅读 0赞

[**challenge 0：**][challenge 0]

**水题，暴力修改都能过。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1000010;
    int n,m,k,p;
    char flag;
    int a[maxn];
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=m;i++)
        {
            cin>>flag;
            if(flag=='Q')
            {
                scanf("%d",&p);
                printf("%d\n",a[p]);
            }
            else
            {
                scanf("%d%d",&k,&p);
                a[k]=p;        
            }
        }
        return 0;
    }

[**challenge 1：**][challenge 1]

**查询某个版本，肯定是可持久化数据结构，单点修改，用可持久化线段树即可，每次修改时新开一条链，这样就大大减少了空间的开销。**

**查询某个版本，从某次操作的根节点向下查询即可。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    int a[maxn];
    int n,m;
    int cnt;
    struct node{
        int lson,rson,val;//左儿子，右儿子，权值 
    }tree[maxn*4];
    int root[maxn]; 
    char opt;
    int x,y;
    int tim;
    void copynode(int neww,int old){
        tree[neww].lson=tree[old].lson;
        tree[neww].rson=tree[old].rson;
        tree[neww].val=tree[old].val;
    }
    void build(int rt,int l,int r){
        if(l==r){
            tree[rt].val=a[l];
            return;
        }
        tree[rt].lson=++cnt;//动态开点 
        tree[rt].rson=++cnt;
        int mid=l+r>>1;
        build(tree[rt].lson,l,mid);
        build(tree[rt].rson,mid+1,r);
    }
    void update(int rt,int l,int r,int ori,int pos,int x){
        copynode(rt,ori);
        if(l==r){
            tree[rt].val=x;
            return;
        }
        int mid=l+r>>1;
        if(pos<=mid){
            tree[rt].lson=++cnt;
            update(tree[rt].lson,l,mid,tree[ori].lson,pos,x);
        } 
        else{
            tree[rt].rson=++cnt;
            update(tree[rt].rson,mid+1,r,tree[ori].rson,pos,x);
        }
    }
    int query(int rt,int l,int r,int pos){
        if(l==r) return tree[rt].val;
        int mid=(l+r)>>1;
        if(pos<=mid) return query(tree[rt].lson,l,mid,pos);
        else return query(tree[rt].rson,mid+1,r,pos);
    }
    int main(){
        scanf("%d%d",&n,&m);
        root[0]=++cnt;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        build(root[0],1,n);
        while(m--){
            cin>>opt>>x>>y;
            if(opt=='Q'){
                tim++;
                root[tim]=root[tim-1];
                printf("%d\n",query(root[y],1,n,x));
            }
            if(opt=='M'){
                tim++;
                root[tim]=++cnt;//新开节点 
                update(root[tim],1,n,root[tim-1],x,y);
            }
        }
        return 0;
    }

**[challenge 3：][challenge 3]**

**线段树单点修改。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    struct node{
        int l,r;
        long long sum;
    }tree[maxn*20];
    int a[maxn],n,m;
    int x,v,l1,r1;
    char opt[5];
    void build(int now,int l,int r){
        tree[now].l=l,tree[now].r=r;
        if(l==r){
            tree[now].sum=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
    }
    void update(int now,int x,int v){
        if(tree[now].l==tree[now].r){
            tree[now].sum=v;
            return;
        } 
        int mid=(tree[now].l+tree[now].r)>>1;
        if(x<=mid) update(now<<1,x,v);
        else update(now<<1|1,x,v);
        tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
    }
    long long query(int now,int l,int r){
        if(tree[now].l>=l&&tree[now].r<=r) return tree[now].sum;
        long long val=0;
        int mid=(tree[now].l+tree[now].r)>>1;
        if(l<=mid) val+=query(now<<1,l,r);
        if(r>mid) val+=query(now<<1|1,l,r);
        return val;
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        build(1,1,n);
        for(int i=1;i<=m;i++){
            scanf("%s",opt);
            if(opt[0]=='M'){
                scanf("%d%d",&x,&v);
                update(1,x,v);
            }
            else{
                scanf("%d%d",&l1,&r1);
                printf("%d\n",query(1,l1,r1));
            }
        }
        return 0;
    }

[**challenge 5：**][challenge 5]

**线段树区间赋值。**

**FBI Warning：此题数据有毒，赋值时会有负的，注意lazy标记的初始化。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    struct node{
        int l,r;
        long long lazy;
        long long sum;
    }tree[maxn*25];
    int n,m;
    long long a[maxn];
    int l,r;
    long long v;
    char opt[666];
    void build(int now,int l,int r){
        tree[now].l=l,tree[now].r=r,tree[now].lazy=-99999999;
        if(l==r){
            tree[now].sum=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
    }
    void pushdown(int now){
        if(tree[now].lazy!=-99999999){
            tree[now<<1].sum=(tree[now<<1].r-tree[now<<1].l+1)*tree[now].lazy;
            tree[now<<1|1].sum=(tree[now<<1|1].r-tree[now<<1|1].l+1)*tree[now].lazy;
            tree[now<<1].lazy=tree[now].lazy;
            tree[now<<1|1].lazy=tree[now].lazy;
            tree[now].lazy=-99999999;
        }
    }
    void update(int now,int l,int r,long long v){
        if(tree[now].l>=l&&tree[now].r<=r){
            tree[now].sum=(tree[now].r-tree[now].l+1)*v;
            tree[now].lazy=v;
            return;
        }
        pushdown(now);
        int mid=(tree[now].l+tree[now].r)>>1;
        if(l<=mid) update(now<<1,l,r,v);
        if(r>mid) update(now<<1|1,l,r,v);
        tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
    }
    long long query(int now,int l,int r){
        if(tree[now].l>=l&&tree[now].r<=r) return tree[now].sum;
        pushdown(now);
        int mid=(tree[now].l+tree[now].r)>>1;
        long long val=0;
        if(l<=mid) val+=query(now<<1,l,r);
        if(r>mid) val+=query(now<<1|1,l,r);
        return val;
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        build(1,1,n); 
        for(int i=1;i<=m;i++){
            scanf("%s",opt);
            if(opt[0]=='M') scanf("%d%d%lld",&l,&r,&v),update(1,l,r,v);
            else scanf("%d%d",&l,&r),printf("%lld\n",query(1,l,r));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11432197.html

[challenge 0]: http://cdqz.openjudge.cn/ds/1000/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/891fbcdf6c4342e99ba3c5f837765fba.png
[challenge 1]: http://cdqz.openjudge.cn/ds/1001/
[challenge 3]: http://cdqz.openjudge.cn/ds/1003/
[challenge 5]: http://cdqz.openjudge.cn/ds/1005/