BZOJ 2161 布娃娃(权值线段树)

题意

给n<1e5个娃娃，每个娃娃有属性\(p\),\(c\),\(l\),\(r\)(均在ll范围内)，问你对每个娃娃\(i\)，满足所有\(l_j\leq p_i\leq r_j\)的娃娃\(j\)中第\(i\)大的\(c_i\)是多少

思路

离散化后

扫描线段上的所有点，对当前点覆盖的所有线段所在的娃娃的\(c_i\)建权值线段树，\(log\)查询即可

代码

int n;

int a[maxn];

ll C[maxn];

vector<ll>v;

int find(ll x){

    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;

}

ll P[maxn],L[maxn],R[maxn];

vector<ll>in[maxn],out[maxn],hv[maxn];

ll Padd, Pfirst, Pmod, Pprod, Cadd, Cfirst, Cmod, Cprod, Ladd, Lfirst, Lmod, Lprod, Radd, Rfirst, Rmod, Rprod;

void add(int p, int x, int l, int r, int root){

    int mid = l+r>>1;

    if(l==r){

        a[root]+=x;return;

    }

    if(p<=mid)add(p,x,lson);

    else add(p,x,rson);

    a[root]=a[lc]+a[rc];

    return;

}

int ask(int k, int l, int r, int root){

    int mid = l+r>>1;

    if(k>a[root])return 0;

    if(l==r)return l;

    if(a[rc]>=k)return ask(k,rson);

    else return ask(k-a[rc],lson);

}

int main() {

    scanf("%d", &n);

    scanf("%lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld",&Padd,&Pfirst,&Pmod,&Pprod,&Cadd,&Cfirst,&Cmod,&Cprod,&Ladd,&Lfirst,&Lmod,&Lprod,&Radd,&Rfirst,&Rmod,&Rprod);

    P[1]=Pfirst%Pmod;C[1]=Cfirst%Cmod;L[1]=Lfirst%Lmod;R[1]=Rfirst%Rmod;

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

        if(i>1){

            P[i] = (P[i-1] * Pprod + Padd + i) % Pmod;

            C[i] = (C[i-1] * Cprod + Cadd + i) % Cmod;

            L[i] = (L[i-1] * Lprod + Ladd + i) % Lmod;

            R[i] = (R[i-1] * Rprod + Radd + i) % Rmod;

        }

    }

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

        if(L[i]>R[i])swap(L[i],R[i]);

        v.pb(P[i]);v.pb(C[i]);v.pb(L[i]);v.pb(R[i]+1);

    }

    sort(v.begin(),v.end());

    v.erase(unique(v.begin(),v.end()),v.end());

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

        in[find(L[i])].pb(find(C[i]));

        out[find(R[i]+1)].pb(find(C[i]));

        hv[find(P[i])].pb(i);

    }

    int tot = v.size();

    ll sum = 0;

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

        for(int j = 0; j < (int)in[i].size(); j++){

            add(in[i][j],1,1,tot,1);

        }

        for(int j = 0; j < (int)out[i].size(); j++){

            add(out[i][j],-1,1,tot,1);

        }

        for(int j = 0; j < (int)hv[i].size(); j++){

            int now = ask(hv[i][j],1,tot,1);

            if(now)sum=(sum+v[now-1])%19921228;

        }

    }

    printf("%lld",sum%19921228);

    return 0;

}