[补题][线段树][权值区间离散化] 2019牛客第七场 E Find the median

本质上是一个离散化的权值线段树，其实很简单，比赛时候没写出来是个遗憾，主要当时没考虑清楚离散化的对象，结果和之后的处理方式。

刚开始看题面里一个数据生成公式，以为是强制在线的，后来发现其实是假的，输入是可以全部离线处理出来的。这样的话就可以先把每一步中的L，R求出来了。之后的话，注意到题目的操作实质上相当于权值线段树的操作就可以计数了，我这里当时以为是add值的操作，其实只是增加了数字的个数而已。但是数字范围会很大，所以要离散化一下。这里要特别注意的是在这种区间的离散化之后，就不是原来线段树了（原来的我们所谓正常的线段树其实相当于是个点树），因此要用[l,r)这种左闭右开的区间来计算，否则二分的时候会漏掉中间的一段[mid,mid+1]。

wa点的话有一个是查询的时候参考值要用long long，因为他最大可能是4e5*1e9的,另一个是要开8倍空间，因为4e5个操作其实有8e5个l(r)值。。。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 400010;

ll X[maxn],Y[maxn],lrsa[maxn][2],lrs[maxn<<1];
ll L[maxn],R[maxn];

struct node{
    int l,r;
    ll sum,lazy;
}tree[maxn<<3];//<<2 or << 3?

void build(int o,int l,int r){
    tree[o].l=l,tree[o].r=r;
    tree[o].sum=tree[o].lazy=0;
    if(l+1==r) return ;
    build(o<<1,l,(l+r)>>1);
    build(o<<1|1,(l+r)>>1,r);

}

void pushdown(int o){
    if(tree[o].l+1==tree[o].r||tree[o].lazy==0) return ;
    else{
        tree[o<<1].lazy+=tree[o].lazy;
        tree[o<<1|1].lazy+=tree[o].lazy;
        tree[o<<1].sum+=tree[o].lazy*(lrs[tree[o<<1].r]-lrs[tree[o<<1].l]);
        tree[o<<1|1].sum+=tree[o].lazy*(lrs[tree[o<<1|1].r]-lrs[tree[o<<1|1].l]);//error2 o<1????
        tree[o].lazy=0;
    }
}

void maintain(int o){
    if(tree[o].l+1==tree[o].r) return ;
    tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum;
}


int ql,qr;
void update(int o,int l,int r){
    if(ql<=l&&r<=qr){
        tree[o].lazy+=1;
        tree[o].sum+=lrs[r]-lrs[l];
    }
    else{
        int mid=(l+r)>>1;
        pushdown(o);
        if(ql<mid) update(o<<1,l,mid);
        if(mid<qr) update(o<<1|1,mid,r);
        maintain(o);
    }
}

int query(int o,ll v){//error3 long long v!
    if(tree[o].l+1==tree[o].r){
        ll unit=tree[o].sum/(lrs[tree[o].r]-lrs[tree[o].l]);//error1 lrs
        return (int)(lrs[tree[o].l]+ceil(1.0*v/unit)-1);
    }
    else{
        pushdown(o);
        if(v<=tree[o<<1].sum) return query(o<<1,v);
        else return query(o<<1|1,v-tree[o<<1].sum);
    }
}

void solve(int n){
    int tot=0;
    for(int i=1;i<=n;i++){
        lrsa[i][1]++;//[l,r]->[l,r+1)
        lrs[tot++]=lrsa[i][0];
        lrs[tot++]=lrsa[i][1];
    }
    sort(lrs,lrs+tot);
    tot=unique(lrs,lrs+tot)-lrs;
    for(int i=1;i<=n;i++){
        L[i]=lower_bound(lrs,lrs+tot,lrsa[i][0])-lrs;
        R[i]=lower_bound(lrs,lrs+tot,lrsa[i][1])-lrs;
    }
    build(1,0,tot-1);
    ll tp=0;
    for(int i=1;i<=n;i++){
        tp+=lrsa[i][1]-lrsa[i][0];
        ql=L[i],qr=R[i];
        update(1,0,tot-1);
        printf("%d\n",query(1,(tp+1)>>1));
    }
}

int main() {
    int n;
    while(scanf("%d",&n)==1){
        ll A,B,C,M;
        scanf("%lld%lld%lld%lld%lld%lld",&X[1],&X[2],&A,&B,&C,&M);
        for(int i=3;i<=n;i++){
            X[i]=(A*X[i-1]+B*X[i-2]+C)%M;
        }
        scanf("%lld%lld%lld%lld%lld%lld",&Y[1],&Y[2],&A,&B,&C,&M);
        for(int i=3;i<=n;i++){
            Y[i]=(A*Y[i-1]+B*Y[i-2]+C)%M;
        }
        for(int i=1;i<=n;i++){
            lrsa[i][0]=1+min(X[i],Y[i]);
            lrsa[i][1]=1+max(X[i],Y[i]);
        }
        solve(n);
    }
    return 0;
}