noip模拟31 solutions
我就觉得这些考试题是越考越难，我是也越考越完蛋，已经完完全全的接近爆零了
只有20pts，说真的这还是我第一次挂掉30pts，本来我还有50pts嘞
所以这次考试我直接炸裂，改题的时候也不是非常的顺利，一直不知道该咋办
但是我得到了一个经验，线段树真的是个好东西，得好好的利用
T1 game
这个题真的快要气死我了，我在考场上一秒切掉最优解
一个小时没想出来字典序，真是无奈。。。。。
最后看题解的时候发现这个直接线段树维护就好了
维护啥呢？维护这个区间内所有的a，b一共可以造成的贡献是多少
每次二分这个不影响贡献的边界值，可能不太好理解
就是你发现在两个序列中，只要b大于a就好了，所以我们在权值线段树中在相应的位置的相应的序列中插入1
这样我们每次pushup的时候就可以维护出每个区间的贡献
我们按顺序便利a数组，首先删掉当前的a，去线段树中寻找不影响总贡献的最大值
这个肯定是单调的，因为你区间内的数越多，获得贡献的可能性越大
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=1e5+5;
int n,a[N],b[N];
struct XDS{
#define ls x<<1
#define rs x<<1|1
int sum[N*4],dw[N*4],up[N*4];
void pushup(int x){
int tmp=min(dw[ls],up[rs]);
sum[x]=sum[ls]+sum[rs]+tmp;
dw[x]=dw[ls]+dw[rs]-tmp;
up[x]=up[ls]+up[rs]-tmp;
return ;
}
void ins(int x,int l,int r,int pos,int v1,int v2){
//cout<<x<<" "<<l<<" "<<r<<" "<<pos<<endl;
if(l==r){
dw[x]+=v1;
up[x]+=v2;
return ;
}
int mid=l+r>>1;
if(pos<=mid)ins(ls,l,mid,pos,v1,v2);
else ins(rs,mid+1,r,pos,v1,v2);
pushup(x);return ;
}
#undef ls
#undef rs
}xds;
int mx,sum;
multiset<int> st;
signed main(){
scanf("%d",&n);
for(re i=1;i<=n;i++)scanf("%d",&a[i]),mx=max(mx,a[i]);
for(re i=1;i<=n;i++)scanf("%d",&b[i]),mx=max(mx,b[i]);
//cout<<mx<<endl;
for(re i=1;i<=n;i++)xds.ins(1,1,mx,a[i],1,0);
for(re i=1;i<=n;i++)xds.ins(1,1,mx,b[i],0,1),st.insert(b[i]);
int sum=xds.sum[1];
for(re i=1;i<=n;i++){
//cout<<i<<endl;
xds.ins(1,1,mx,a[i],-1,0);
int l=a[i]+1,r=*st.rbegin(),mid;
//cout<<l<<" "<<r<<" ";
while(l<r){
//cout<<l<<" "<<r<<endl;
mid=l+r+1>>1;
xds.ins(1,1,mx,mid,0,-1);
if(1+xds.sum[1]==sum)l=mid;
else r=mid-1;
xds.ins(1,1,mx,mid,0,1);
}
//cout<<i<<" sb"<<" ";
xds.ins(1,1,mx,l,0,-1);
if(l<=r&&1+xds.sum[1]==sum){
printf("%d ",l);
sum--;
st.erase(st.find(l));
}
else{
xds.ins(1,1,mx,l,0,1);
l=1;r=a[i];
while(l<r){
//cout<<l<<" "<<r<<endl;
mid=l+r+1>>1;
xds.ins(1,1,mx,mid,0,-1);
if(xds.sum[1]==sum)l=mid;
else r=mid-1;
xds.ins(1,1,mx,mid,0,1);
}
xds.ins(1,1,mx,l,0,-1);
printf("%d ",l);
st.erase(st.find(l));
}
//cout<<endl;
}
}
T2 time
这个考场上其实就差一步就好了，逆序对没用对
所以这个题就爆掉了30pts
那这个题的正解也是线段树（其实我是看着std的双端队列不爽才写线段树的）
最小值一定在两端，所以每次只需要将这个最小值向左右两边移动就好了
你发现这个最小值的移动并不会对比他大的值造成任何影响
我们只需要用线段树维护左边的最小值以及距离，右边一样
因为这里会出现相同的数字，所以左右两边要分别维护
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int n,a[N],ans;
struct XDS{
#define ls x<<1
#define rs x<<1|1
int lmn[N*4],lrk[N*4],rmn[N*4],rrk[N*4];
int siz[N*4];
void pushup(int x){
if(a[lmn[ls]]<=a[lmn[rs]]){
lmn[x]=lmn[ls];
lrk[x]=lrk[ls];
}
else{
lmn[x]=lmn[rs];
lrk[x]=lrk[rs]+siz[ls];
}
if(a[rmn[rs]]<=a[rmn[ls]]){
rmn[x]=rmn[rs];
rrk[x]=rrk[rs];
}
else{
rmn[x]=rmn[ls];
rrk[x]=rrk[ls]+siz[rs];
}
siz[x]=siz[ls]+siz[rs];
return ;
}
void build(int x,int l,int r){
if(l==r){
lmn[x]=rmn[x]=l;
lrk[x]=rrk[x]=1;
siz[x]=1;
return ;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(x);return ;
}
void del(int x,int l,int r,int pos){
//cout<<x<<" "<<l<<" "<<r<<" "<<pos<<endl;
if(l==r){
lmn[x]=rmn[x]=0;
lrk[x]=rrk[x]=inf;
siz[x]=0;
return ;
}
int mid=l+r>>1;
if(pos<=mid)del(ls,l,mid,pos);
else del(rs,mid+1,r,pos);
pushup(x);return ;
}
#undef ls
#undef rs
}xds;
signed main(){
scanf("%d",&n);
a[0]=inf;
for(re i=1;i<=n;i++)
scanf("%d",&a[i]);
xds.build(1,1,n);
for(re i=1;i<=n;i++){
//cout<<i<<" "<<xds.lmn[1]<<" "<<xds.rmn[1]<<endl;
if(xds.lrk[1]<=xds.rrk[1]){
ans+=xds.lrk[1]-1;
xds.del(1,1,n,xds.lmn[1]);
}
else{
ans+=xds.rrk[1]-1;
xds.del(1,1,n,xds.rmn[1]);
}
//cout<<"sB"<<endl;
}
printf("%d",ans);
}
T3 cover
这个最简单了，看到包含和不相交，一眼就是树形dp
可是我不会打，考完了直接一个\(\mathcal{O(n^2)}\)的暴力转移拿到45
这个差分的确是个好东西;
直接把每一个权值插入到对应的节点的multiset中
我们每次让轻链合并到重链，因为一颗树上的轻链包含的节点总个数就是n
所以合并的总复杂度是\(\mathcal{O(nlogn)}\)
这个差分其实就是对一个函数进行做差，
我们将这个二维的转移数组，每个节点当作一个函数，那么他的差分一定是单调不增的
为啥，因为最大的放在前面一定最优
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
const int N=3e5+5;
int n,m;
struct node{
int l,r;
ll a;
node(){}
bool operator < (node x)const{
if(l!=x.l)return l<x.l;
return r>x.r;
}
}sca[N];
int to[N],nxt[N],head[N],rp;
int du[N];
void add_edg(int x,int y){
to[++rp]=y;
nxt[rp]=head[x];
head[x]=rp;
}
int sta[N],tot;
bool check(int x,int y){
return sca[x].l<=sca[y].l&&sca[y].r<=sca[x].r;
}
multiset<ll> f[N];
void merge(multiset<ll> &x,multiset<ll> &y){
if(x.size()<y.size())swap(x,y);
vector<ll> tmp;tmp.clear();
multiset<ll>::iterator it=y.begin();
while(it!=y.end()){
//cout<<"sb"<<endl;
tmp.push_back(*it+*x.begin());
x.erase(x.begin());
it=next(it);
}
for(re i=0;i<tmp.size();i++)x.insert(tmp[i]);
}
void dfs(int x){
for(re i=head[x];i;i=nxt[i]){
int y=to[i];dfs(y);
merge(f[x],f[y]);
//cout<<x<<" "<<y<<" "<<"ok"<<endl;
}
if(x==m+1)return ;
f[x].insert(-sca[x].a);
}
signed main(){
scanf("%d%d",&n,&m);
for(re i=1;i<=m;i++)scanf("%d%d%lld",&sca[i].l,&sca[i].r,&sca[i].a);
sort(sca+1,sca+m+1);
sta[tot=1]=m+1;
for(re i=1;i<=m;i++){
while(tot>1&&!check(sta[tot],i)){
add_edg(sta[tot-1],sta[tot]);
du[sta[tot]]++;tot--;
}
sta[++tot]=i;
}
tot--;
while(tot){
add_edg(sta[tot],sta[tot+1]);
du[sta[tot+1]]++;tot--;
}
dfs(m+1);
//cout<<"sb"<<endl;
ll ans=0;
//cout<<"sb"<<" "<<(*f[m+1].begin())<<endl;
for(re i=1;i<=m;i++){
//cout<<i<<" ";
if(f[m+1].size()){
ans+=-(*f[m+1].begin());
f[m+1].erase(f[m+1].begin());
}
printf("%lld ",ans);
}
}