C61 可持久化线段树+递推 P3963 [TJOI2013] 奖学金

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=200005;
#define mid (l+r)/2
int n,c,f,ans=-1;
struct node{
    int a,b; //成绩,奖学金
    bool operator<(node &t){return a<t.a;}
}w[N];
int b[N],f1[N],f2[N];
int root[N],tot; //根节点,开点个数
int ls[N*25],rs[N*25],sum[N*25];
//f1[i]:1~i中前k小的奖金之和
//f2[i]:i~c中前k小的奖金之和
//sum:区间数的个数的前缀和

void change(int &u,int v,int l,int r,int x){ //点修
  u=++tot;
  ls[u]=ls[v];rs[u]=rs[v];sum[u]=sum[v]+1;
  if(l==r) return;
  if(x<=mid)change(ls[u],ls[v],l,mid,x);
  else change(rs[u],rs[v],mid+1,r,x);
}
int query(int u,int v,int l,int r,int k){ //点查
  if(l==r) return l;
  int s=sum[ls[u]]-sum[ls[v]];
  if(k<=s) return query(ls[u],ls[v],l,mid,k);
  else return query(rs[u],rs[v],mid+1,r,k-s);
}
int main(){
  scanf("%d%d%d",&n,&c,&f);
  for(int i=1;i<=c;i++)scanf("%d%d",&w[i].a,&w[i].b);
  for(int i=1;i<=c;i++)b[i]=w[i].b;
  sort(b+1,b+1+c);
  int bn=unique(b+1,b+1+c)-b-1; //奖金b离散化
  sort(w+1,w+1+c);       //按成绩a排序
  for(int i=1;i<=c;i++){ //持久树:版本i对应成绩下标
    int p=lower_bound(b+1,b+1+bn,w[i].b)-b;
    change(root[i],root[i-1],1,bn,p);
  }
  
  int k=(n-1)/2; //半数
  for(int i=1;i<=k;i++) 
    f1[i]=f1[i-1]+w[i].b;  //前缀和
  for(int i=k+1;i<=c;i++){ //替换第k小
    int p=query(root[i-1],root[0],1,bn,k);
    f1[i]=f1[i-1]+min(0,w[i].b-b[p]);
  }
  for(int i=c;i>=c-k+1;i--)
    f2[i]=f2[i+1]+w[i].b;  //后缀和
  for(int i=c-k;i>=1;i--){ //替换第k小
    int p=query(root[c],root[i],1,bn,k);
    f2[i]=f2[i+1]+min(0,w[i].b-b[p]);
  }
  for(int i=k+1;i<=c-k;i++) //枚举中位数的位置
    if(w[i].b+f1[i-1]+f2[i+1]<=f) ans=w[i].a;
  printf("%d\n",ans);
}

//大根堆 nlogn
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

const int N=200005;
int n,c,f,ans=-1;
int sa[N],sb[N];
struct node{
  int a,b;
  bool operator<(node &t){return a<t.a;}
}w[N];
priority_queue<int>q;

int main(){
  scanf("%d%d%d",&n,&c,&f);
  for(int i=1;i<=c;i++)scanf("%d%d",&w[i].a,&w[i].b);
  sort(w+1,w+c+1);
  for(int i=1;i<=n/2;i++)
    q.push(w[i].b),sa[i]=sa[i-1]+w[i].b;
  for(int i=n/2+1;i<=c;i++)
    if(w[i].b<q.top())sa[i]=sa[i-1]-q.top()
            +w[i].b,q.pop(),q.push(w[i].b);
  else sa[i]=sa[i-1];
  
  while(q.size()) q.pop();
  for(int i=c;i>=c-n/2+1;i--)
    q.push(w[i].b),sb[i]=sb[i+1]+w[i].b;
  for(int i=c-n/2;i>=1;i--)
    if(w[i].b<q.top())sb[i]=sb[i+1]-q.top()
            +w[i].b,q.pop(),q.push(w[i].b);
  else sb[i]=sb[i+1];
  
  for(int i=n/2+1;i<=c-n/2;i++)
    if(sa[i-1]+sb[i+1]+w[i].b<=f)ans=w[i].a;
  printf("%d\n",ans);
}