[每日一题] NC50439 tokitsukaze and Soldier

题解：

考虑对s从小到大进行排序。如果当前选择了s[i]那么所有满足的j都是可以选择的。我们只需要取满足条件的前s[i]大就好了。
问题在于如果取前s[i]大，这个可以用一个权值线段树来维护。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
const int mod=1e9+7;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
ll qpow(ll a,ll b){ll ans=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)ans=ans*a%mod;a=a*a%mod;}return ans;}
ll gcd(ll a,ll b){return b>0?gcd(b,a%b):a;}
int n,m,T;
int a[maxn];
int b[maxn];
map<int,int>M; 
vi v;
struct node{
    ll sum,num;
    node operator+(const node& b)const{
        return node{sum+b.sum,num+b.num};
    }
}tr[maxn];
#define lson rt<<1
#define rson rt<<1|1
void update(int C,int pos,int l,int r,int rt){
    if(pos<l||pos>r) return;
    if(l==r){
        tr[rt].num+=C;
        tr[rt].sum+=1ll*C*v[pos-1];
        return ;
    }
    int mid=l+r>>1;
    update(C,pos,l,mid,lson);
    update(C,pos,mid+1,r,rson);
    tr[rt]=tr[lson]+tr[rson];
}
ll query(int k,int l,int r,int rt){
    if(l==r||k==0){
        return 1ll*k*v[l-1];
    }
    if(tr[rt].num<=k){
        return tr[rt].sum;
    }
    int mid=l+r>>1;
    if(tr[rson].num>=k) return query(k,mid+1,r,rson);
    else return tr[rson].sum+query(k-tr[rson].num,l,mid,lson);
}
int getid(int x){
    return lower_bound(all(v),x)-v.begin()+1;
}
pii c[maxn];
int main(){
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        c[i]={b[i],a[i]};
        v.pb(a[i]);
    }
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    int N=v.size();
    sort(c+1,c+1+n); 
    for(int i=1;i<=n;i++){
        update(1,getid(a[i]),1,N,1); 
    }
    for(int i=1;i<=n;i++){
        pii tmp=c[i];
        ans=max(ans,query(tmp.fi,1,N,1));
        update(-1,getid(tmp.se),1,N,1);        
    }
    cout<<ans<<"\n";

//    cin>>n>>m;

    return 0;
}
/*
5
1 2
1 2
1 3
1 4
1 4

*/