The Stream of Corning 2( 权值线段树/(树状数组+二分) )

题意:

有两种操作:1.在[l,r]上插入一条值为val的线段 2.问p位置上值第k小的线段的值(是否存在)

特别的，询问的时候l和p合起来是一个递增序列

1<=l,r<=1e9；1<=val<=1e6; 1<=k<=1e9

思路:

因为l和p总体是递增的，第i个询问的p一定大于i之前所有操作的l，而前面能影响到i的答案的只有r>=p的线段。由此可以想到将l,r,p合起来离散化，从左往右扫描，遇到l,就在权值线段树上插入对应的val，遇到r就删除对应的val，而遇到询问时，当前的线段树必然对应了P点的所有线段，求一下全局第k小就能得到答案。

全局第k小除了利用权值线段树外，还能通过二分树状数组求得，复杂度比线段树多logn，但是实际测试好像还是树状数组快。

权值线段树

#include <bits/stdc++.h>

#define lson  rt<<1

#define rson rt<<1|1

using namespace std;

const int maxn=2e5+5;//离散化值可能有两倍

struct node {

    int opt,p,val,id;

    operator<(node b) {

        if(p!=b.p)

            return p<b.p;

        else if(opt==2)

            return true;

        else if(b.opt==2)

            return false;

        else

            return id<b.id;

    }

} P[maxn];

int cnt=0,n;

int T[maxn<<2];

inline void push_now(int k){

    T[k]=T[k<<1]+T[k<<1|1];

}

void add(int rt,int l,int r,int p,int val){//[l,r]

    if(l==r){

        T[rt]+=val;

        return;

    }

    int mid=(l+r)>>1;

    if(p<=mid) add(lson,l,mid,p,val);

    if(p>mid) add(rson,mid+1,r,p,val);

    push_now(rt);

}

int query(int rt,int l,int r,int k){

    if(T[rt]<k) return -1;

    if(l==r) return l;

    int mid=(l+r)>>1;

    if(T[lson]>=k)

        return query(lson,l,mid,k);

    else

        return query(rson,mid+1,r,k-T[lson]);

}

int lisan[maxn],tot=0;

int ans[maxn],acnt=0;

int main() {

    int t,E;

    cin>>t;

    for(int kase=1; kase<=t; kase++) {

        scanf("%d",&E);

        tot=0;acnt=0;cnt=0;

        for(int i=1; i<=E; i++)

            T[i]=0;

        int x,val,y,opt;

        for(int i=1; i<=E; i++) {

            scanf("%d%d%d",&opt,&x,&val);

            if(opt==1) {

                lisan[++tot]=val;

                scanf("%d",&y);

                P[++cnt]= {1,x,val,i};

                P[++cnt]= {-1,y,val,i};

            } else {

                P[++cnt]= {2,x,val,i};

            }

        }

        sort(lisan+1,lisan+1+tot);

        n=unique(lisan+1,lisan+1+tot)-(lisan+1);

        for(int i=1; i<=cnt; i++) {

            if(P[i].opt!=2)

                P[i].val=lower_bound(lisan+1,lisan+1+n,P[i].val)-lisan;

        }

        sort(P+1,P+1+cnt);

        for(int i=1; i<=cnt; i++) {

            if(P[i].opt!=2) {

                add(1,1,n,P[i].val,P[i].opt);

            }

            else {

                int temp=query(1,1,n,P[i].val);

                if(temp==-1)

                    ans[++acnt]=-1;

                else

                    ans[++acnt]=lisan[temp];

            }

        }

        printf("Case %d:\n",kase);

        for(int i=1; i<=acnt; i++) {

            printf("%d\n",ans[i]);

        }

    }

}

树状数组+二分

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=2e5+5;//离散化值可能有两倍

struct node {

    int opt,p,val,id;

    operator<(node b) {

        if(p!=b.p)

            return p<b.p;

        else if(opt==2)

            return true;

        else if(b.opt==2)

            return false;

        else

            return id<b.id;

    }

} P[maxn];

int cnt=0,n;

int T[maxn];

int lowbit(int x) {

    return x&(-x);

}

int getsum(int p) {

    int res=0;

    while(p>0) {

        res+=T[p];

        p-=lowbit(p);

    }

    return res;

}

void add(int p,int val) {

    while(p<=n) {

        T[p]+=val;

        p+=lowbit(p);

    }

}

int query(int x) {

    int l=0,r=n,mid;

    while(r-l>1) {

        mid=(r+l+1)/2;

        if(getsum(mid)>=x)

            r=mid;

        else

            l=mid;

    }

    return r;

}

int lisan[maxn],tot=0;

int ans[maxn],acnt=0;

int main() {

    int t,E;

    cin>>t;

    for(int kase=1; kase<=t; kase++) {

        scanf("%d",&E);

        tot=0;

        acnt=0;

        cnt=0;

        for(int i=1; i<=E; i++)

            T[i]=0;

        int x,val,y,opt;

        for(int i=1; i<=E; i++) {

            scanf("%d%d%d",&opt,&x,&val);

            if(opt==1) {

                lisan[++tot]=val;

                scanf("%d",&y);

                P[++cnt]= {1,x,val,i};

                P[++cnt]= {-1,y,val,i};

            } else {

                P[++cnt]= {2,x,val,i};

            }

        }

        sort(lisan+1,lisan+1+tot);

        n=unique(lisan+1,lisan+1+tot)-(lisan+1);

        for(int i=1; i<=cnt; i++) {

            if(P[i].opt!=2)

                P[i].val=lower_bound(lisan+1,lisan+1+n,P[i].val)-lisan;

        }

        sort(P+1,P+1+cnt);

        for(int i=1; i<=cnt; i++) {

            if(P[i].opt!=2) {

                add(P[i].val,P[i].opt);

            }

            else {

                int temp=query(P[i].val);

                if(getsum(n)<P[i].val)

                    ans[++acnt]=-1;

                else

                    ans[++acnt]=lisan[temp];

            }

        }

        printf("Case %d:\n",kase);

        for(int i=1; i<=acnt; i++) {

            printf("%d\n",ans[i]);

        }

    }

}

巴特西

The Stream of Corning 2( 权值线段树/(树状数组+二分) )

权值线段树

树状数组+二分

最新文章

热门文章