16493 推销员(线段树尝试)

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
struct node{
    int l,r,add;
    ll maxx,s,a,max_id,id;
}tr[4*N];
struct node1{
    int s,a;
}p[N];
int pos,pos_i=1;
bool cmp(node1 a,node1 b)
{
    if(a.s!=b.s) return a.s<b.s;
    return a.a<b.a;
}

void pushup(node &u,node &l,node &r)
{
    if(l.maxx>=r.maxx) u.maxx=l.maxx,u.max_id=l.max_id,u.id=l.id;
    else u.maxx=r.maxx,u.max_id=r.max_id,u.id=r.id;
}
void pushup(int u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add)
    {
        left.add += root.add, left.maxx += root.add;
        right.add += root.add, right.maxx +=  root.add;
        root.add = 0;
    }
}

void build(int u,int l,int r)
{
    tr[u]={l,r};
    if(l==r) tr[u].maxx=p[l].a+p[l].s*2,tr[u].a=p[l].a,tr[u].s=p[l].s,tr[u].max_id= p[l].s,tr[u].id=l;
    else{
        int mid = l+r >>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r,int d)
{
    if(l>r) return;
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].maxx+=d;
        tr[u].add+=d;
    }
    else{
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if (l <= mid) modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

node query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
    pushdown(u);
    int mid = tr[u].l+tr[u].r >>1;
    if(r<=mid) return tr[u<<1];
    else if(l>mid) return tr[u<<1|1];
    else{
        auto left = query(u<<1,l,r);
        auto right = query(u<<1|1,l,r);
        node res;
        pushup(res,left,right);
        return res;
    }
}

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&p[i].s);
    for(int i=1;i<=n;i++) scanf("%d",&p[i].a);
    sort(p+1,p+1+n,cmp);
    build(1,1,n);
    ll ans=0;
    for(int j=0;j<n;j++)
    {
        node t=query(1,1,n);
        ans+=t.maxx;
        printf("%lld\n",ans);
        if(t.max_id>pos){
            for(;pos_i<=n;pos_i++)
            {
                if(p[pos_i].s<=t.max_id) modify(1,pos_i,pos_i,-2*p[pos_i].s);
                else break;
            }
           modify(1,pos_i,n,-2*(t.max_id-pos));
           pos=t.max_id;
        }
        modify(1,t.id,t.id,-p[t.id].a);
    }
    return 0;
}