如果Jan先手，那么可以放入一个对Petra来说价值$inf$的物品，就变成了Petra先手。
对于Petra来说，拿物品的顺序是固定的，按这个顺序排序。
那么如果把Petra的选择看成$($，Jan的选择看成$)$，一个合法的方案对应了一个合法括号序列。
因此贪心选取$lfloorfrac{n}{2} floor$个价值最大的右括号，同时保证不破坏括号序列合法性即可，线段树维护。
时间复杂度$O(nlog n)$。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1010,M=2050;
int T,n,i,k,x,ansa,ansb,vs[M],vb[M],tag[M];char U[9];
struct P{int a,b;}a[N];
inline bool cmp(const P&a,const P&b){return a.a==b.a?a.b<b.b:a.a>b.a;}
inline void add1(int x,int p){vs[x]+=p,tag[x]+=p;}
inline void pb(int x){if(tag[x])add1(x<<1,tag[x]),add1(x<<1|1,tag[x]),tag[x]=0;}
inline int merge(int x,int y){return a[x].b>a[y].b?x:y;}
inline void up(int x){
vs[x]=min(vs[x<<1],vs[x<<1|1]);
vb[x]=merge(vb[x<<1],vb[x<<1|1]);
}
void build(int x,int a,int b){
tag[x]=0;
if(a==b){vs[x]=vb[x]=a;return;}
int mid=(a+b)>>1;
build(x<<1,a,mid),build(x<<1|1,mid+1,b),up(x);
}
void add(int x,int a,int b,int c){
if(c<=a){add1(x,-2);return;}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)add(x<<1,a,mid,c);
add(x<<1|1,mid+1,b,c);
up(x);
}
void change(int x,int a,int b,int c){
if(a==b){vb[x]=0;return;}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)change(x<<1,a,mid,c);else change(x<<1|1,mid+1,b,c);
up(x);
}
int askmax(int x,int a,int b,int c){
if(c<=a)return vb[x];
pb(x);
int mid=(a+b)>>1,t=0;
if(c<=mid)t=askmax(x<<1,a,mid,c);
t=merge(t,askmax(x<<1|1,mid+1,b,c));
up(x);
return t;
}
int right(int x,int a,int b){
if(vs[x]>1)return 0;
if(a==b)return a;
pb(x);
int mid=(a+b)>>1,t=right(x<<1|1,mid+1,b);
if(!t)t=right(x<<1,a,mid);
up(x);
return t;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%s",&n,U);
for(i=1;i<=n;i++)scanf("%d%d",&a[i].a,&a[i].b),ansa+=a[i].a;
if(U[0]=='J'){
n++;
a[n].a=1010;
a[n].b=0;
}
sort(a+1,a+n+1,cmp);
build(1,1,n);
for(i=n/2;i;i--){
k=right(1,1,n);
x=askmax(1,1,n,k+1);
ansa-=a[x].a;
ansb+=a[x].b;
change(1,1,n,x);
add(1,1,n,x);
}
printf("%d %d
",ansa,ansb);
ansa=ansb=0;
}
return 0;
}