总结：CSP2024-S模拟赛

A. 人事调动

长得非常像一道模拟，但是由于set会去重，map开的大小会达到 $N^2$ ，所以，我们可以使用multiset（其增删改查时间复杂度近似：O(log N)，即总时间复杂度为O(N log N)）。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=100005;

int n,q;
int a[N],b[N];
multiset<int> mp[N];
multiset<int> ans;

int main()
{
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
		
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		mp[b[i]].insert(a[i]);
	}
	
	for(int i=1;i<N;i++)
	{
		if(mp[i].empty())
		{
			continue;
		}
		ans.insert(*(--mp[i].end()));
	}
	
	while(q--)
	{
		int c,d;
		cin>>c>>d;
		
		int id=b[c];
		ans.erase(ans.find(*(--mp[id].end())));
		mp[id].erase(mp[id].find(a[c]));
		if(!mp[id].empty())
		{
			ans.insert(*(--mp[id].end()));
		}
		
		if(!mp[d].empty())
		{
			ans.erase(ans.find(*(--mp[d].end())));
		} 
		mp[d].insert(a[c]);
		ans.insert(*(--mp[d].end()));
		
		b[c]=d;
		
		
		cout<<(*ans.begin())<<"\n";
	}
	
	return 0;
}             
 

---

B. 失意

比较一眼的贪心，以区间左端点从小到大排序，用优先队列从小到大维护右端点，每次队列里有m个元素，就比较一次大小，超过m就把右端点最小的弹出去。每次比较记录此时的最大L和最小R（答案即R-L），最后再循环一边找到符合的m个区间。

注意：要特判答案为0的时候，任意输出m个区间即可

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=1000005;

ll Num,n,m;
struct node
{
	ll l,r,id;
	bool operator <(node a)
	{
		return l<a.l;
	}
} a[N];

priority_queue<ll> pq;
bool f;

ll ans,id1,id2;

int main()
{
    freopen("failure.in","r",stdin);
    freopen("failure.out","w",stdout);
    
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>Num;
	
	cin>>n>>m; 
	for(ll i=1;i<=n;i++)
	{
		ll x,y;
		cin>>x>>y;
		a[i]={x,y,i};
	}
	sort(a+1,a+n+1);
		
	for(ll i=1;i<=n;i++)
	{
		pq.push(-a[i].r);
		while(pq.size()>m)
		{
			pq.pop();
		}
		if(pq.size()==m)
		{
			if(-pq.top()-a[i].l>ans)
			{
				ans=-pq.top()-a[i].l;
				id1=a[i].l,id2=-pq.top();
			}
		}
	}
	
	if(id1==0&&id2==0)
	{
		id1=1e9;
	}
	cout<<ans<<"\n";
	
	for(ll i=1;i<=n;i++)
	{
		if(a[i].l<=id1&&a[i].r>=id2)
		{
			cout<<a[i].id<<" ";
			m--;
		}
		if(!m)
		{
			cout<<"\n";
			return 0;
		}
	} 
	
	return 0;
}    
 

---

C. 位于LIS概率

又是C>>>>>>D，扣C结果在还有3分钟结束的时候想到了正解，错失D大好90pts

70pts的做法就是没有线段树/树状数组优化的正解：求出整个数列的LIS长度mx；对于每个 $i∈{1…n}$ 求出以i结尾与以i开头的LIS长度 $x1$, $x2$ 和数量 $t1$, $t2$ ，如果其 $x1+x2-1=mx$，说明这是一种LIS，i在LIS中的情况数+= $t1\times t2$，最后用快速幂求逆元即可。

用树状数组维护比较短（改成线段树只要改架构就行了）。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=1000005,mod=998244353;

ll n,m;
ll a[N],b[N];

ll ans[N];

struct node
{
	ll x,t; //长度，数量
	
} tr[N],pre[N],suf[N];

node mx;

ll qpow(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1)
		{
			ret=ret*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}

void calc(node &x,node y) //合并
{
	if(x.x==y.x)
	{
		x.t=(x.t+y.t)%mod;
	}
	else if(x.x<y.x)
	{
		x=y;
	}
}

void update(ll x,node y)
{
	while(x<=m)
	{
		calc(tr[x],y);
		x+=x&(-x);
	}
}

node query(ll x)
{
	node ret={0,0};
	while(x)
	{
		calc(ret,tr[x]);
		x-=x&(-x);
	}
	
	return ret;
}

int main()
{
    freopen("lis.in","r",stdin);
    freopen("lis.out","w",stdout);
    
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	
	sort(b+1,b+n+1);
	m=unique(b+1,b+n+1)-b-1;
	
	for(ll i=1;i<=n;i++)
	{
		a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	}
	
	for(ll i=1;i<=n;i++)
	{
		pre[i]=query(a[i]-1);
		pre[i].x++;
		calc(pre[i],{1,1});
		update(a[i],pre[i]);
		
		calc(mx,pre[i]);
	}
	
	memset(tr,0,sizeof tr);
	
	for(ll i=n;i;i--)
	{
		a[i]=m-a[i]+1;
		suf[i]=query(a[i]-1);
		suf[i].x++;
		calc(suf[i],{1,1});
		update(a[i],suf[i]);
	}
	
	for(ll i=1;i<=n;i++)
	{
		if(pre[i].x+suf[i].x-1==mx.x)
		{
			ans[i]=pre[i].t*suf[i].t%mod;
		}
	}
	
	ll tt=qpow(mx.t,mod-2);
	for(ll i=1;i<=n;i++)
	{
		cout<<ans[i]*tt%mod<<" ";
	}
	
	cout<<"\n";

	return 0;
}

---

D. 排队

暴力有90早知道不扣C了

补题之后感觉不是很复杂，不知道做法有没有假掉。

首先由题目我们明确了一些排序规则：

• 子节点在父节点前面
• 编号小的的子节点在编号大的子节点前面

因此，我们可以用dfs给每一个节点排序，并用优先队列维护空房间顺序。

对于操作1（来人）：弹出x次优先级最高房间，输出最后一个编号

对于操作2（走人）：我们发现对于被移动的人x，他只会影响他的祖先，倍增，直到到空房间，输出其上跳步数即可。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=1e5+5;

int n,t;

vector<int> e[N];
int par[N][25];

int id[N];
int tot;
	
bool vis[N];

void dfs(int x,int f)
{
	par[x][0]=f;
	vector<int> son;
	son.clear();
	
	for(auto y:e[x])
	{
		if(y==f)
		{
			continue;	
		}
		son.push_back(y);
	}
	
	sort(son.begin(),son.end());
	for(auto y:son)
	{
		dfs(y,x);
	}
		
	id[x]=++tot;
}

struct node
{
	int v;
	bool operator < (const node &x) const
	{
		return id[v]>id[x.v];
	}
};

priority_queue<node>q;


int main()
{
    freopen("queue.in","r",stdin);
    freopen("queue.out","w",stdout);
    
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>t;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	
	dfs(1,0);
	
	for(int i=1;i<=20;i++)
	{
		for(int j=1;j<=n;j++)
		{
			par[j][i]=par[par[j][i-1]][i-1];
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		q.push((node){i});
	}
	
	while(t--)
	{
		int op,x;
		cin>>op>>x;
		
		if(op==1)
		{
			int v=0;
			for(int i=1;i<=x;i++)
			{
				v=q.top().v;
				q.pop();
				vis[v]=1;
			}
			cout<<v<<"\n";
			
		}
		else
		{
			int cnt=0;
			for(int i=20;i>=0;i--)
			{
				if(vis[par[x][i]])
				{
					x=par[x][i];
					cnt+=(1<<i);
				}
			}
			
			vis[x]=0;
			q.push((node){x});
		
			cout<<cnt<<"\n";
		}
	}
	
	return 0;
}

---

END…