线段树区间离散化——牛客多校E

素颜马尾好姑娘i 2023-10-11 09:14 15阅读 0赞

这个区间离散化把我调死了。。

总之用vector来离散化，然后叶子节点维护的是一段区间，记录下每个叶子结点的起点+长度

千万要注意下标不能弄错！

#include<bits/stdc++.h>
    #define MAXN 400005
    #define INF 1000000000
    #define MOD 1000000007
    #define F first
    #define S second
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> P;
    int N;
    int X[MAXN],Y[MAXN],L[MAXN],R[MAXN];
    vector<int> v;
    int X1,X2,Y1,Y2,A1,A2,B1,B2,C1,C2,M1,M2;
    struct segtree
    {
        ll sum[8*MAXN];
        int lazy[8*MAXN],len[8*MAXN];
        void pushup(int k)
        {
            sum[k]=sum[k*2]+sum[k*2+1];
        }
        void pushdown(int k)
        {
            if(!lazy[k]) return;
            for(int i=k*2;i<=k*2+1;i++)
            {
                lazy[i]+=lazy[k];
                sum[i]+=lazy[k]*len[i];
            }
            lazy[k]=0;
            return;
        }
        void build(int k,int l,int r)
        {
            if(l==r)
            {
                len[k]=v[l]-v[l-1];
                return;
            }
            int mid=(l+r)/2;
            build(k*2,l,mid); build(k*2+1,mid+1,r);
            pushup(k);
            len[k]=len[k*2]+len[k*2+1];
        }
        void update(int k,int l,int r,int x,int y)
        {
            if(x>r||l>y) return;
            if(l>=x&&r<=y)
            {
                lazy[k]++;
                sum[k]+=len[k];
                return;
            }
            pushdown(k);
            int mid=(l+r)/2;
            update(k*2,l,mid,x,y); update(k*2+1,mid+1,r,x,y);
            pushup(k);
        }
        int query(int k,int l,int r,ll x)
        {
            if(l==r)
            {
                int cnt=sum[k]/len[k];
                int id=(x-1)/cnt;
                return v[l-1]+id;
            }
            pushdown(k);
            int mid=(l+r)/2;
            if(sum[k*2]>=x) return query(k*2,l,mid,x); else return query(k*2+1,mid+1,r,x-sum[k*2]);
        }
    }seg;
    int main()
    {
        scanf("%d",&N);
        scanf("%d%d%d%d%d%d",&X1,&X2,&A1,&B1,&C1,&M1);
        scanf("%d%d%d%d%d%d",&Y1,&Y2,&A2,&B2,&C2,&M2);
        X[1]=X1; X[2]=X2; Y[1]=Y1; Y[2]=Y2;
        for(int i=3;i<=N;i++)
        {
            X[i]=(1LL*A1*X[i-1]+1LL*B1*X[i-2]+C1)%M1;
            Y[i]=(1LL*A2*Y[i-1]+1LL*B2*Y[i-2]+C2)%M2;
        }
        for(int i=1;i<=N;i++)
        {
            L[i]=min(X[i],Y[i])+1;
            R[i]=max(X[i],Y[i])+1; R[i]++;
            v.push_back(L[i]); v.push_back(R[i]);
        }
        
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
    
        int sz=(int)v.size()-1;
        seg.build(1,1,sz);
        ll sum=0;
        for(int i=1;i<=N;i++)
        {
            int posl=lower_bound(v.begin(),v.end(),L[i])-v.begin();
            int posr=lower_bound(v.begin(),v.end(),R[i])-v.begin();
            posl++;
            seg.update(1,1,sz,posl,posr);
            sum+=R[i]-L[i];
            printf("%d\n",seg.query(1,1,sz,(sum+1)/2));
        }
        return 0;
    }

update:其实用数组离散化也可以，，只是我的数组开小了一直不知道错在哪里。。

#include<bits/stdc++.h>
    #include<vector>
    using namespace std;
    #define maxn 800005
    #define MAXN 800005
    #define ll long long 
    ll x[maxn],y[maxn],l[maxn],r[maxn];
    ll n,a1,a2,b1,b2,c1,c2,m1,m2,m;
    vector<ll>v;
    ll h[maxn];
    
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    //叶子结点l代表第l个区间，即起点为v[l-1],长度为v[l]-v[l-1] 
    ll sum[maxn<<3],lazy[maxn<<3],len[maxn<<3];
    void pushup(int rt){
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    void pushdown(int rt){
        if(lazy[rt]){
            for(int i=(rt<<1);i<=(rt<<1|1);i++){
                lazy[i]+=lazy[rt];
                sum[i]+=lazy[rt]*len[i];
            }
            lazy[rt]=0;
        }
    }
    void build(int l,int r,int rt){
        if(l==r){
            len[rt]=h[l+1]-h[l];
            return;
        }
        int m=l+r>>1;
        build(lson);build(rson);
        len[rt]=len[rt<<1]+len[rt<<1|1];
    }
    void update(int L,int R,int l,int r,int rt){
        if(L>R)return;
        if(L<=l && R>=r){
            lazy[rt]++;
            sum[rt]+=len[rt];
            return;
        }
        pushdown(rt);
        int m=l+r>>1;
        if(L<=m)update(L,R,lson);
        if(R>m)update(L,R,rson);
        pushup(rt);
    }
    ll query(ll k,int l,int r,int rt){
        if(l==r){
            int tmp=sum[rt]/len[rt];
            int tmp2=(k-1)/tmp;
            return h[l]+tmp2;
        }
        pushdown(rt);
        int m=l+r>>1;
        if(k<=sum[rt<<1])return query(k,lson);
        else return query(k-sum[rt<<1],rson); 
    }
    int main(){
        cin>>n;
        cin>>x[1]>>x[2]>>a1>>b1>>c1>>m1;
        cin>>y[1]>>y[2]>>a2>>b2>>c2>>m2;
        for(int i=3;i<=n;i++){
            x[i]=(a1*x[i-1]+b1*x[i-2]+c1)%m1;
            y[i]=(a2*y[i-1]+b2*y[i-2]+c2)%m2;
        }
        for(int i=1;i<=n;i++){
            l[i]=min(x[i],y[i])+1;
            r[i]=max(x[i],y[i])+1;
            r[i]++;
            h[++m]=l[i];h[++m]=r[i];
        }
        sort(h+1,h+1+m);
        m=unique(h+1,h+1+m)-h-1;
        build(1,m-1,1);
        
        
        ll sum=0; 
        for(int i=1;i<=n;i++){
            int posl=lower_bound(h+1,h+m+1,l[i])-h;
            int posr=lower_bound(h+1,h+m+1,r[i])-h;
            posr--;
            sum+=r[i]-l[i];
            update(posl,posr,1,m-1,1);
            cout<<query((sum+1)/2,1,m-1,1)<<'\n';
        }
    }

转载于:https://www.cnblogs.com/zsben991126/p/11324743.html