题解：CF2200F Mooclear Reactor 2

· · 题解

闲话

本题解请谨慎观看。

正文

思路

发现每个粒子都有两个属性，然后我赛时直接想到了主席树（没错）。

发现对于答案产生限制的是 y 属性，产生贡献的是 x 属性，不如称为限制和贡献。

如果你知道把一些有着二维属性的问题看作是二维数点问题，将限制看作是 x 轴，将贡献看作是 y 轴，那么本题的一个重要思路就是：假设买的点的限制与贡献分别是 x 和 y，我们很容易在上述二维图中看出，可以对答案产生贡献的点的限制肯定都至少大于买的点的限制，就是在直线 x=y_{i} 的右边或者就是在这条线上。

根据上述的描述，我们进而可以想到，假设一个数组 sum 表示使用 i 个粒子（肯定是合法的）可以产生的最大贡献，那么 sum_i 的求解其实就是求解满足上面限制的前 i 大数的和，如果不理解，可以自己画个图，就会发现产生贡献的点都在右上方。

那么对于答案，我们就发现，如果不取这个点，答案就是 sum 数组的最大值；取这个点，答案就是 \max_{i=1}^{y}sum_{i-1}+x，然后两者取最大值就是答案了。

对于上述过程，很容易发现，只要先建出一棵主席树，用来维护区间前 k 大和，然后对于 sum 的求解明显就是主席树上二分就可以解决了，然后维护前缀最大值什么的，答案就可以 \Theta(1) 求了。

总复杂度 \Theta(n\log n+m)。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10,N=2e5+10;
struct node{
    int ls,rs,time;
    ll w;
}a[N*35];
int root[N],tot=0;
#define mid ((l+r)>>1)
void push_up(int x){
    a[x].w=a[a[x].ls].w+a[a[x].rs].w;
    a[x].time=a[a[x].ls].time+a[a[x].rs].time;
}
void update(int &x,int last,int l,int r,int pos){
    x=++tot;
    a[x]=a[last];
    if(l==r){
        a[x].w+=l;
        a[x].time++;
        return;
    }
    if(pos<=mid) update(a[x].ls,a[last].ls,l,mid,pos);
    else update(a[x].rs,a[last].rs,mid+1,r,pos);
    push_up(x);
}
ll query_sum(int L,int R,int l,int r,int k){//前K大的数的和 
    if(k==0)return 0ll;
    if(a[R].time-a[L].time==0) return 0ll;
    if(a[R].time-a[L].time<=k) return a[R].w-a[L].w;
    if(l==r){
        return min(k,a[R].time-a[L].time)*1ll*l;
    } 
    int tot=a[a[R].rs].time-a[a[L].rs].time;
    ll sum=a[a[R].rs].w-a[a[L].rs].w;
    if(tot>=k) return query_sum(a[L].rs,a[R].rs,mid+1,r,k);
    else return query_sum(a[L].ls,a[R].ls,l,mid,k-tot)+sum;
}
#undef mid
ll ans2[N],premax[N],maxn=-1;//用i个粒子产生的最大值 
struct LLS{
    int x,y;
    friend bool operator <(const LLS &l1,const LLS &l2){
        if(l1.y!=l2.y)return l1.y<l2.y;
        return l1.x<l2.x;
    }
}val[N],num[N];
//有的，商店的 
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){
        tot=0;maxn=-1ll;
        int n,m;cin>>n>>m;
        FOR(i,1,n)cin>>val[i].x>>val[i].y;
        sort(val+1,val+1+n);
        FOR(i,1,m)cin>>num[i].x>>num[i].y;
        FOR(i,1,n){
            update(root[i],root[i-1],0,INF,val[i].x);
        } 
        FOR(i,0,n){
            LLS fin={0,i};
            int it=lower_bound(val+1,val+1+n,fin)-val;
            ans2[i]=query_sum(root[it-1],root[n],0,INF,i);
            if(i!=0)premax[i]=max(premax[i-1],ans2[i]);
            else premax[i]=ans2[i];
            maxn=max(maxn,query_sum(root[it-1],root[n],0,INF,min(i+1,n)));
        } 
        FOR(i,1,m){
            cout<<max(maxn,premax[num[i].y]+num[i].x)<<" ";
        }
        cout<<"\n";
    }
    return 0;
}