noip模拟31

2024-02-23 13:31:34

A.Game

发现最高得分可以直接贪心得到答案..
然后我们去满足字典序最大..
一开始想的是从后往前字典序最小就可以，然后同时刚好满足一些值，但是发现手写几个例子就Hack了..
首先我们发现，对于一个前面的数\(A\)，ta所被对应的数\(B\)越大，那么后面能满足的个数一定是不会上升的..
所以二分答案..用线段树同时维护两个值..
线段树维护多个这样的值要学会..

A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll int 
	#define ull unsigend ll
	#define re register ll 
	#define lf double
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memset(x,y,sizeof x)
	inline ll read() {
		ll ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=1e5+50;

ll m,n,ans,cnt,maxn;
ll a[N],b[N];
struct I { ll ta,tb,ts; } tr[N<<7];
multiset<ll> s;
inline void pushup(ll x){
	ll temp=min(tr[x<<1].tb,tr[x<<1|1].ta);
	tr[x].ts=tr[x<<1].ts+tr[x<<1|1].ts+temp;
	tr[x].ta=tr[x<<1].ta+tr[x<<1|1].ta-temp;
	tr[x].tb=tr[x<<1].tb+tr[x<<1|1].tb-temp;
	return ;
}
void update(ll x,ll l,ll r,ll pos,ll ta,ll tb){
	if(l==r){
		tr[x].ta+=ta;
		tr[x].tb+=tb;
		return ;
	}
	ll mid=(l+r)>>1;
	if(pos<=mid) update(x<<1,l,mid,pos,ta,tb);
	else update(x<<1|1,mid+1,r,pos,ta,tb);
	pushup(x);
	return ;
}
inline void Work(ll x){
	update(1,1,maxn,b[x],0,-1);
	ll le=b[x]+1,ri=*s.rbegin(),mid;
	while(le<ri){
		mid=(le+ri+1)>>1;
		update(1,1,maxn,mid,-1,0);
		if(tr[1].ts==ans-1) le=mid;
		else ri=mid-1;
		update(1,1,maxn,mid,1,0);
	}
	update(1,1,maxn,le,-1,0); 
	if(tr[1].ts==ans-1 and le<=ri){
		ans--;
		s.erase(s.find(le));
		printf("%d ",le);
		return ;
	}
	update(1,1,maxn,le,+1,0); 
	le=0,ri=b[x];
	while(le<ri){
		mid=(le+ri+1)>>1;
		update(1,1,maxn,mid,-1,0);
		if(tr[1].ts==ans) le=mid;
		else ri=mid-1;
		update(1,1,maxn,mid,1,0);
	}
	update(1,1,maxn,le,-1,0); s.erase(s.find(le));
	printf("%d ",le);
	return ;
}
	
signed main(){
//	File(0.in,out);
	n=read();
	for(re i=1;i<=n;i++) b[i]=read(),maxn=max(maxn,b[i]);
	for(re i=1;i<=n;i++) a[i]=read(),maxn=max(maxn,a[i]);
	for(re i=1;i<=n;i++){
		update(1,1,maxn,a[i],1,0),update(1,1,maxn,b[i],0,1);
		s.insert(a[i]);
	}
	ans=tr[1].ts;
	for(re i=1;i<=n;i++) Work(i);
	return 0;
}

B.Time

一个显然的性质，中间的数字一定最大..
考场上打的是枚举位置，考虑这个点前面的逆序对个数和后面的逆序对个数..
后来发现：这个数字左右两边的数字也可以交换.
观察得到，对于每一个数字\(x\)，比较\(x\)到最左边和最右边分别经过的比\(x\)大的数字个数，取\(min\)值就是ta要移动的距离..
所以答案就是：
设第i个位置的数与前面构成的逆序对个数为\(s_i\)，和后面构成的正序对个数为\(t_i\)，那么有

\[ans=\Sigma_{i=1}^nmin(s_i,t_i) \]

B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int 
	#define ull unsigend ll
	#define re register ll 
	#define lf double
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memset(x,y,sizeof x)
	inline ll read() {
		ll ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=1e5+50;
ll m,n,cnt,maxw,maxcnt;
ll w[N],f[N],g[N],lsh[N],pre[N],suf[N],maxpos[N];
struct I { ll l,r,sum; } tr[N*20];
void build(ll x,ll l,ll r){
	tr[x].l=l; tr[x].r=r;
	if(l==r) return ;
	ll mid=(tr[x].l+tr[x].r)>>1;
	build(x<<1,l,mid); build(x<<1|1,mid+1,r);
	return ;
}
inline void pushup(ll x){
	tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
	return ;
}
ll query(ll x,ll ql,ll qr){
	if(ql>qr) return 0;
	if(tr[x].l>=ql and tr[x].r<=qr){
		return tr[x].sum;
	}
	ll mid=(tr[x].l+tr[x].r)>>1;
	ll temp=0;
	if(ql<=mid) temp+=query(x<<1,ql,qr);
	if(qr>=mid+1) temp+=query(x<<1|1,ql,qr);
	return temp;
}
void update(ll x,ll pos,ll num){
	if(tr[x].l==tr[x].r){
		tr[x].sum+=num;
		return ;
	}
	ll mid=(tr[x].l+tr[x].r)>>1;
	if(pos<=mid) update(x<<1,pos,num);
	else update(x<<1|1,pos,num);
	pushup(x);
	return ;
}
signed main(){
	n=read();
	for(re i=1;i<=n;i++){
		lsh[i]=w[i]=read();
	}
	sort(lsh+1,lsh+1+n); 
	cnt=unique(lsh+1,lsh+1+n)-lsh-1;
	build(1,1,cnt);
	for(re i=1;i<=n;i++){
		w[i]=lb(lsh+1,lsh+1+cnt,w[i])-lsh;
		f[i]=query(1,w[i]+1,cnt);
		update(1,w[i],1);
	}
	for(re i=1;i<=n;i++){
		update(1,w[i],-1);
	}
	for(re i=n;i>=1;i--){
		g[i]=query(1,w[i]+1,cnt);
		update(1,w[i],1);
	}
	ll ans=0;
//	for(re i=1;i<=n;i++) cout<<f[i]<<" "<<g[i]<<endl;
	for(re i=1;i<=n;i++) {
		ans+=min(f[i],g[i]);
	}
	printf("%lld",ans);
	return 0;
}

C.Cover

发现区间只有包含和不相交，所以可以构成一个树上结构..
设\(f_{i,j}\)表示第\(i\)个点的子树中，节点最多被覆盖\(j\)次..
所以得到转移方程：

\[f_{i,j}=max(f_{i,j}\ ,f_{i,j-1}+w[i]) \]

第一次见到差分表优化Dp..
可以使用\(multiset\)或优先队列维护被覆盖第\(i\)次的最大值..
然后答案累加即可..

C_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int 
	#define ull unsigend ll
	#define re register ll 
	#define lf double
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memset(x,y,sizeof x)
	inline ll read() {
		ll ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=1e6+50;

ll m,n,ts;
ll head[N];
multiset<ll> f[N];
struct I { ll l,r,w; } p[N];
struct II { ll u,v,nxt; } e[N<<4];
inline bool comp(I i,I j){ return i.l==j.l ? i.r>j.r : i.l<j.l ; }
inline void add(ll u,ll v){
	e[++ts].u=u;
	e[ts].v=v;
	e[ts].nxt=head[u];
	head[u]=ts;
}
ll Build(ll x,ll l,ll r,ll st){
	for(ll i=st;i<=m;i++){
		if(p[i].l>=l and p[i].r<=r){
			add(x,i);
			i=Build(i,p[i].l,p[i].r,i+1)-1;
		}
		else return i;
	}
	return m+1;
}
void dfs(ll now){
	ll son=m+5;
	multiset<ll> s;
	for(re i=head[now];i;i=e[i].nxt){
		dfs(e[i].v);
		if(f[e[i].v].size()>f[son].size()) son=e[i].v;
	}
	swap(f[now],f[son]);
	for(re i=head[now];i;i=e[i].nxt){
		if(e[i].v==son) continue;
		while(f[e[i].v].size() and f[e[i].v].size()){
			auto it1=--f[e[i].v].end();
			auto it2=--f[now].end();
			s.insert(*it1+*it2);
			f[e[i].v].erase(it1);
			f[now].erase(it2);
		}
		while(f[now].size()){
			auto it1=--f[now].end();
			s.insert(*it1);
			f[now].erase(it1);
		}
		while(f[e[i].v].size()){
			auto it1=--f[e[i].v].end();
			s.insert(*it1);
			f[e[i].v].erase(it1);
		}
		swap(f[now],s);
	}
	f[now].insert(p[now].w);
	return ;
}
signed main(){
//	freopen("0.in","r",stdin);
	n=read(); m=read();
	for(re i=1;i<=m;i++){
		p[i].l=read();
		p[i].r=read();
		p[i].w=read();
	}
	sort(p+1,p+1+m,comp);
	Build(0,1,n,1);
	dfs(0);
	ll ans=0;
	for(int i=1;i<=m;i++)
	{
		if(f[0].size()){
			auto it=--f[0].end();
			f[0].erase(it);
			ans+=*it;
		}
		printf("%lld ",ans);
	}
	return 0;
}
上一篇：[SDOI2016] 生成魔咒 - 后缀数组,平衡树,STL,时间倒流


下一篇：单向队列，双向队列，优先队列的基本用法