Warning 有一部分的图炸了，是因为笔者还没上传图片

10.09 模拟赛 (SG-NOI 2019) 解题报告

[toc]

Task 1: Pilot

Description

有 $n$ 座山峰，第 $i$ 座的高度为 $H_i$ 。

有 $m$ 架飞机，第 $j$ 架飞机的最大飞行高度为 $Y_j$ 。

一架最大飞行高度为 $Y$ 飞机能从第 $s$ 座山峰出发飞到第 $e$ 座山峰（$s\le e$），当且仅当对于所有的 $s \le i \le e$，都有 $Y\ge H_i$ 。

现在要对每一架飞机求出这架飞机有多少种不同的飞行路线（飞机一定是向右飞，也就是起点的编号一定小于等于终点的编号），两条飞行路线不同当且仅当它们的起点和终点不完全相同。

Constraints

对于 $100\%$ 的数据，$1\le n,m,H_i,Y_j \le 10^6$

Sample

Solution

Subtask1~4

随便写，暴力即可。

预计得分：40pts

Subtask5

性质分

观察到 $H_i \le 10^6$，而 $Y_i=10^6$，所以这一架飞机可以飞过所有的山，答案为 $n*(n+1)/2$

预计得分：5pts

Subtask6~7

这两个点的共性是：$H_i$ 都是严格递增的。

所以一架飞机能够飞的最大区间一定是一个前缀，而且前缀的长度是随着最大飞行高度的增加单调不降的。

所以可以给飞机的最大飞行高度排序。

预计得分：23pts

正解

受到 Subtask6~7 的启发，我们可以给飞机按照最大飞行高度进行排序，由此衍生出两种思路：

从大到小考虑

提供一个直观的理解方式：

这些绿色的条条是山，而飞机的飞行高度可以视为一个逐渐下降的水面，随着水面的下降，一些山会露出水面从而隔断一些大区间，使其变为两个小区间。

于是我们就可以维护当前有哪些区间，当一个山露出水面时，我们就对应地把这个区间分裂。

可以使用 set 维护当前有哪些区间，但是由于这种做法常数较大的原因，不能通过本题。

从小到大考虑

这是上面那种方法的逆过程，考虑水面逐渐上升的过程，一些山会被水盖住，从而使得几个小区间合并成一个大区间，我们可以用并查集维护这个过程。这种做法可以通过本题。

Code

下面那一堆被注释掉的是用了 set 的超时做法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,nQ;

struct query{
	int y,id;
}q[N];

bool cmpq(query u,query v){
	return u.y<v.y;
}

struct node{
	int v,p;
}a[N];

bool cmpn(node x,node y){
	if(x.v==y.v)return x.p<y.p;
	return x.v<y.v;
}

int id[N];ll sz[N];
ll ANS=0;

int root(int x){return id[x]==x?id[x]:id[x]=root(id[x]);}

void unite(int u,int v){
	u=root(u),v=root(v);
	if(u==v)return;
	if(sz[u]>sz[v])swap(u,v);
	ANS-=sz[u]*(sz[u]+1)/2;
	ANS-=sz[v]*(sz[v]+1)/2;
	id[u]=v;
	sz[v]+=sz[u];
	ANS+=sz[v]*(sz[v]+1)/2;
}

void add(int pos){
	if(!id[pos]){
		id[pos]=pos;
		sz[pos]=1;
		ANS+=1;
	}
	if(pos>1){
		if(id[pos-1]){
			int u=root(pos-1),v=root(pos);
			unite(u,v); 
		}
	}
	if(pos<n){
		if(id[pos+1]){
			int u=root(pos),v=root(pos+1);
			unite(u,v);
		}
	}
}

ll ans[N];

int main(){
	
	scanf("%d %d",&n,&nQ);
	
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].v);
		a[i].p=i;
	}
	
	sort(a+1,a+1+n,cmpn);
	
	for(int i=1;i<=nQ;i++){
		scanf("%d",&q[i].y);
		q[i].id=i;
	}
	
	sort(q+1,q+nQ+1,cmpq);
	
	int p=1;
	for(int i=1;i<=nQ;i++){
		while(p<=n&&a[p].v<=q[i].y){
			add(a[p].p);
			p++;
		}
		ans[q[i].id]=ANS;
	}
	
	for(int i=1;i<=nQ;i++){
		printf("%lld\n",ans[i]);
	}
	
	return 0;
}

/*

set<int> st;
ll ANS=0;

ll ans[N];

void add(int pos){
	st.insert(pos);
	set<int>::iterator it=st.find(pos);
	set<int>::iterator it1,it2;
	it--;it1=it;
	it++,it++;it2=it;
	int len=(*it2)-(*it1)-1;
	ANS-=1ll*len*(len+1)/2;
	len=(*it2)-pos-1;
	ANS+=1ll*len*(len+1)/2;
	len=pos-(*it1)-1;
	ANS+=1ll*len*(len+1)/2;
}

int main(){
	
	scanf("%d %d",&n,&nQ);
	
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].v);
		a[i].p=i;
	}
	
	sort(a+1,a+1+n,cmpn);
	
	for(int i=1;i<=nQ;i++){
		scanf("%d",&q[i].y);
		q[i].id=i;
	}
	
	sort(q+1,q+nQ+1,cmpq);
	
	int p=1;
	
	st.insert(0),st.insert(n+1);
	ANS=1ll*n*(n+1)/2;
	
	for(int i=1;i<=nQ;i++){
		while(p<=n&&a[p].v>q[i].y){
			add(a[p].p);
			p++;
		}
		ans[q[i].id]=ANS;
	}
	
	for(int i=1;i<=nQ;i++)printf("%lld\n",ans[i]);
	
	return 0;
}
*/

Task 2: Lasers

Description

有 $L$ 个激光器等距摆放在墙上，有 $R$ 条轨道，第 $i$ 条轨道上有 $x_i$ 个可以滑动的墙体，其中第 $j$ 个墙体的宽度为 $w_{i,j}$，一个宽度为 $d$ 的墙体恰好可以挡住 $d$ 个连续的激光器（不管怎么滑动，总是会挡住 $d$ 个），同一条轨道上的墙体可以在不改变相对顺序的情况下随意摆放，并且任意两个墙体（同轨道的）不会重合（也就是说不会同时挡住同一个激光器）。

问有多少个激光器无论如何都会被至少一个墙体挡住。

Constraints

对于 $100\%$ 的数据，$1\le R \le 5 * 10^5,1\le L \le 10^9,1\le \sum c_i \le 5*10^5$ ,$\text{对于每一行 }1\le \sum w_{i,j} \le L$

Sample

Solution

Subtask1

只有一行，并且这一行只有一面墙体。手模一下找找规律：

图中夹在红线之间的区域是无论如何都会被盖住的。也就是说，最终会被盖住的区间是以墙体在最右边是左端点的位置和墙体在最左边时的右端点的位置所夹的区间。

Subtask2

有很多行，但是每一行都只有一面墙体。我们顺着上一个子任务的思路走：

每一行都有一个区间，而一个激光器所在的位置，如果被至少一个区间包含，那么意味着这个激光器无论如何一定会被至少一个墙体挡住。所以全局的答案区间就是每一行的区间的并集。

Subtask 3

考虑一个特定的位置和一条轨道，如何判断是否存在一种墙体的排布方式使得这个位置的激光器不会被挡住？

我们希望把墙体尽量堆在这个位置的两侧，于是这些墙体会形成一个前缀的和后缀的连续段，我们对这个轨道上的墙体的宽度求一个前缀和，然后就可以在前缀和数组上二分出那些墙体堆在了前面，进而判断后缀的墙体段是否会覆盖这个位置。

而一个位置如果在所有一条轨道上没被挡住的话，那么这个位置就无论如何都不会被挡住。

于是我们可以枚举每一个位置，然后对应地判断这个位置是否无论如何都会被挡住。

正解

考虑如何快速的计算出一个轨道上哪些位置无论如何都会被挡住。

我们能正向考虑吗？此时，我们需要计算出每一种的墙体的摆放方式中，被墙体挡住的位置的集合，然后我们需要把这些集合取一个交集。总之挺难处理的。

我们可以从反面考虑：先计算出由那些无论如何也不会被墙体挡住的位置的集合，然后取一个补集就是我们想要的。

考虑怎么算上面说的那个集合：对于所有的墙体的摆放方式，我们只考虑那些把墙体全部堆在最左边或者最右边的方式。我们可以证明，对于所有的方式，我们对中间没有墙体遮挡的位置的集合求并集，就是无论如何也不会被墙体挡住的位置的集合。

四句话核心思路（摘自代码注释）：

这里的 [lll,rrr] 表示的是可以不被盖住的区间 所有的 [lll,rrr] 求并集，就是这一行不会被盖住的区间 再求补集，就是这一行总是会被盖住的区间 再对所有的这些区间求并集，就是全局的总是会被盖住的区间

---

当然，$\rm \color{red}{H}\color{black}uangyuxiang$ 大佬和 $\rm \color{red}{r}\color{black}{everSilly}$ 大佬觉得这种处理方式太麻烦了，于是他们使用了珂朵莉树，这里就不说这种方法了。（毕竟珂朵莉树是奇技淫巧，用多了脑子会坏掉的）

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
int L,R;
int cnt[N];
vector<int> wall[N];

namespace subtask1{
	void solve(){
		int x=wall[1][0];
		printf("%d\n",max(0,2*x-L));
	}
}

namespace subtask2{
	bool check(){
		for(int i=1;i<=R;i++)
			if(cnt[i]>1)return false;
		return true;
	}
	void solve(){
		int ll=L+1,rr=0;
		for(int i=1;i<=R;i++){
			int lll=L-wall[i][0]+1;
			int rrr=wall[i][0];
			
//			if(ll==-1)ll=lll;
//			if(rr==-1)rr=rrr;
			ll=min(ll,lll);
			rr=max(rr,rrr);
		}
		printf("%d\n",max(0,rr-ll+1));
	}
}

namespace subtask3{
	
	struct interval{
		ll l,r;
	}itv[N],itv2[N*2];
	
	bool cmp(interval x,interval y){
		if(x.l==y.l)return x.r<y.r;
		return x.l<y.l;
	}
	
	int nI=0,nII=0;
	ll sum[N];
	void solve(){
		for(int i=1;i<=R;i++)
			for(int j=1;j<=cnt[i];j++)sum[i]+=wall[i][j-1];
			
		ll ss=0;
		
		for(int i=1;i<=R;i++){
//			cout<<"i: "<<i<<endl;
//			int ll=L+1,rr=0;
			ss=0;nI=0;
			for(int j=1;j<=cnt[i]+1;j++){
				ll lll=ss+1;
				ll rrr=L-(sum[i]-ss);
//				cout<<lll<<" "<<rrr<<endl; 
				if(lll<=rrr)itv[++nI]=(interval){lll,rrr};
				/*
				这里的 [lll,rrr] 表示的是可以不被盖住的区间
				所有的 [lll,rrr] 求并集，就是这一行不会被盖住的区间
				再求补集，就是这一行总是会被盖住的区间
				在对所有的这些区间求并集，就是全局的总是会被盖住的区间 
				*/
//				ll=min(ll,lll);
//				rr=max(rr,rrr);
				if(j==cnt[i]+1)break;
				ss+=wall[i][j-1];
			}
			if(nI==0){
				itv2[++nII]=(interval){1,L};
				continue;
			}
			sort(itv+1,itv+1+nI,cmp);
			ll lst=1;
			for(int j=1;j<=nI;j++){
				if(lst<=itv[j].l-1)itv2[++nII]=(interval){lst,itv[j].l-1};
				lst=itv[j].r+1;
			}
		}
		
//		for(int i=1;i<=nII;i++)cout<<itv2[i].l<<" "<<itv2[i].r<<endl;
		
		if(nII==0){
			printf("0\n");
			return;
		}
		sort(itv2+1,itv2+1+nII,cmp);
		ll ans=0;
		ll llll=itv2[1].l,rrrr=itv2[1].r;
		for(int i=2;i<=nII;i++){
			if(itv2[i].l>rrrr){
				ans+=rrrr-llll+1;
				rrrr=itv2[i].r,llll=itv2[i].l;
			}else rrrr=max(rrrr,itv2[i].r);
		} 
		ans+=rrrr-llll+1;
		
//		for(int i=1;i<=nI;i++)cout<<itv[i].l<<" "<<itv[i].r<<endl;
		
		printf("%lld\n",ans);
	}
}

int main(){
	
	scanf("%d %d",&L,&R);
	
	for(int i=1;i<=R;i++){
		scanf("%d",&cnt[i]);
		int x;
		for(int j=1;j<=cnt[i];j++){
			scanf("%d",&x);
			wall[i].push_back(x);
		}
	}
	
	if(R==1&&cnt[1]==1)
		subtask1::solve();
	else if(subtask2::check())
		subtask2::solve();
	else
		subtask3::solve();
	
	return 0;
}