T1 Game
首先考试想到的直接找大于他最小的数，但按照最大字典序输出就炸了，但前几个数据比较水，得了几分辛苦分
这里我们用线段树维护现行答案：
struct TREE_TABLE {
#define lid (id<<1)
#define rid (id<<1|1)
struct TREE { int numa,numb,ans; } tre[maxn<<2];
inline void update(int id) {
int d=min(tre[lid].numa,tre[rid].numb);
tre[id].ans=tre[lid].ans+tre[rid].ans+d;
tre[id].numa=tre[lid].numa+tre[rid].numa-d;
tre[id].numb=tre[lid].numb+tre[rid].numb-d;
}
inline void insert(int id,int l,int r,int pos,int val1,int val2) {
if(l==r) { tre[id].numa+=val1; tre[id].numb+=val2; return; }
int mid=(l+r)>>1;
if(pos<=mid) insert(lid,l,mid,pos,val1,val2);
else insert(rid,mid+1,r,pos,val1,val2);
update(id);
}
} tres;
应该很好理解。
然后的话，直接从左向右扫一边，看这个点能否在不改变总答案的前提下被匹配，如果可以那就匹配他，否则就找不能匹配他最大的数且不改变总答案的数，容易发现选择匹配数具有单调性，二分即可。
for(re int i=1,l,r,mid,ans;i<=n;i++) {
tres.insert(1,1,maxn,a[i],-1,0);
ans=0,l=a[i]+1,r=*s.rbegin();
while(l<=r) {
mid=(l+r)>>1;
tres.insert(1,1,maxn,mid,0,-1);
if(tres.tre[1].ans+1==res) l=mid+1,ans=mid;
else r=mid-1;
tres.insert(1,1,maxn,mid,0,1);
}
tres.insert(1,1,maxn,ans,0,-1);
if(ans&&tres.tre[1].ans+1==res) { res--; printf("%d ",ans); s.erase(s.find(ans)); }
else {
tres.insert(1,1,maxn,ans,0,1);
ans=0,l=1,r=a[i];
while(l<=r) {
mid=(l+r)>>1;
tres.insert(1,1,maxn,mid,0,-1);
if(res==tres.tre[1].ans) l=mid+1,ans=mid;
else r=mid-1;
tres.insert(1,1,maxn,mid,0,1);
}
tres.insert(1,1,maxn,ans,0,-1);
printf("%d ",ans);
s.erase(s.find(ans));
}
}
T2 Time
考试依然想了个假的正解，数据依然水。。。
采用分治思想，从小到大枚举数字让他们向两边移，采取最优决策就好了，这道题还是比较水的，赶紧过
T3 Cover
很新奇～只有包含和不相交，直接建树
struct DATE { int ls,rs,val; } dat[maxn];
inline bool cmp(DATE a,DATE b) { if(a.ls!=b.ls) return a.ls<b.ls; return a.rs>b.rs; }
signed main(void) {
sort(dat+1,dat+1+m,cmp);
vector<int>q; q.push_back(0);
for(re int i=1;i<=m;i++) {
while(q.back()&&dat[q.back()].rs<dat[i].rs) q.pop_back();
add(q.back(),i);
q.push_back(i);
}
}
暴力跳过
重点不在建树，我们发现DP数组可以维护一个差分结构，为什么还取个“差分表”的名字
而且差分数具有单调性，因为这行代码：
f[i][j]=max(f[i][j],f[i][j-1]+dat[i].val);
这地方着重理解，然后mulitset维护差分表，合并时启发式合并（即以小并大）。