C.帮助

本蒟蒻在考场上写了主席树，但是没调出来，赛后才过。。。

首先题目中的 $t, a, b, c, d$ 都是要离散化的。

之后按照 $t$ ，从小到大排序，依次建立值域主席树，统计当前成绩能够被最多帮助的题数。

接下来对于每一个询问，在所有 $t$ 中找到第一个小于 $a$ 的位置，再找到最后一个小于等于 $b$ 的位置，查询当前的成绩所能获得的最大题数即可。

注意：最后要判断自己是否有被算过，如否还要加上自己的题数。

最后，此题空间为 $n (20 + 2 log_2 ( n \times 5 ) )$ ，不能盲目的 :

#define int long long

Ac code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+1;
int n,i,MAX_N,cnt;
int h[N*5],rt[N],b[N];
struct node{
    int a,b,c,d,t,id,f;
}a[N];
struct tree{
    int l,r,ls,rs;
    ll sum,add;//永久标记
}tr[N*61];//(N*5)*4+N*20*2
bool cmp(node x,node y){
    return x.t<y.t;
}
void build(int &p,int l,int r){
    p=++cnt;
    tr[p]=(tree){l,r,0,0,0,0};
    if(l==r)return;
    int mid=(l+r)>>1;
    build(tr[p].ls,l,mid);
    build(tr[p].rs,mid+1,r);
}
bool cmp1(node a,node b){
    return a.id<b.id;
}
void add(int &p,int pr,int l,int r,int c){
    p=++cnt;
    tr[p]=tr[pr];
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].add+=c;
        tr[p].sum+=c*(tr[p].r-tr[p].l+1);
        return;
    }
    int mid=(tr[p].l+tr[p].r)>>1;
    if(l<=mid) add(tr[p].ls,tr[pr].ls,l,r,c);
    if(r>mid) add(tr[p].rs,tr[pr].rs,l,r,c);
    tr[p].sum=tr[tr[p].l].sum+tr[tr[p].r].sum+tr[p].add*(tr[p].r-tr[p].l+1);
}
ll ask(int p,int pr,int x,ll c){
    if(tr[p].l==tr[p].r)return tr[p].sum-tr[pr].sum+c*(tr[p].r-tr[p].l+1);
    int mid=(tr[p].l+tr[p].r)>>1;
    ll ans;
    if(x<=mid)ans=ask(tr[p].ls,tr[pr].ls,x,c+tr[p].add-tr[pr].add);
    else ans=ask(tr[p].rs,tr[pr].rs,x,c+tr[p].add-tr[pr].add);
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i].f,a[i].id=i;
    for(i=1;i<=n;i++)cin>>a[i].t,h[++MAX_N]=a[i].t;
    for(i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b>>a[i].c>>a[i].d;
        h[++MAX_N]=a[i].a;h[++MAX_N]=a[i].b;h[++MAX_N]=a[i].c;h[++MAX_N]=a[i].d;
    }
    sort(h+1,h+1+MAX_N);
    MAX_N=unique(h+1,h+1+MAX_N)-h-1;
    for(i=1;i<=n;i++){//离散化
        a[i].a=lower_bound(h+1,h+1+MAX_N,a[i].a)-h;
        a[i].b=lower_bound(h+1,h+1+MAX_N,a[i].b)-h;
        a[i].c=lower_bound(h+1,h+1+MAX_N,a[i].c)-h;
        a[i].d=lower_bound(h+1,h+1+MAX_N,a[i].d)-h;
        a[i].t=lower_bound(h+1,h+1+MAX_N,a[i].t)-h;
    }
    sort(a+1,a+1+n,cmp);
    build(rt[0],1,MAX_N);
    for(i=1;i<=n;i++)
        add(rt[i],rt[i-1],a[i].c,a[i].d,a[i].f),b[i]=a[i].t;//主席树
    sort(a+1,a+1+n,cmp1);
    for(i=1;i<=n;i++){
        int s1=lower_bound(b+1,b+1+n,a[i].a)-b;
        if(s1==n+1){//小特判
            cout<<a[i].f<<" \n"[i==n];continue;
        }
        s1--;//找起点，类似前缀和的思想，往前多找一位，本来是找第一位大于等于 a 的位置
        int s2=upper_bound(b+1,b+1+n,a[i].b)-b;
        s2--;//找最后一个小于等于 b 的位置
        cout<<ask(rt[s2],rt[s1],a[i].t,0)+(a[i].a<=a[i].t&&a[i].t<=a[i].b&&a[i].c<=a[i].t&&a[i].t<=a[i].d?0:a[i].f)<<" \n"[i==n];//判断自己是否算进
    }
    return 0;
}

题解 | #帮助#

C.帮助