模拟赛T1-[愚蠢的戴夫]豌豆射手-题解

题目背景

愚蠢的戴夫和向日葵聊天。

如果向日葵之间产生了代沟，她们就再也不会交流了。

题目描述

一些向日葵站在上排在一列花盆上，她们通过传话的方式互相交流。

话说多了，自然就产生了代沟。一旦有了代沟，两个向日葵就不说话了，话就传不过去。

有$m$个向日葵，$m$个事件。每一个事件都是这样的：

给定一个$k$，排在第$k$的向日葵和排在第$k+1$的向日葵产生了代沟，事件按发生顺序给出。

每一次事件发生后，愚蠢的戴夫想知道有多少个无序数对$(a,b)$，使得排在$a$和排在$b$的向日葵事件发生前可以交流，事件发生后无法交流。

输入格式

第一行两个整数$n,m$，表示向日葵的个数和事件数量。

接下来$m$行，每行一个正整数，描述一个事件。

输出格式

共$m$行，每一个事件发生后，输出题目所求。

样例 #1

样例输入 #1

6 3
3
2
4

样例输出 #1

9
2
2

数据范围

• 对于$10\%$的数据：$n,m\leq 50$

• 对于$20\%$的数据：$n,m\leq 200$

• 对于$40\%$的数据：$n,m\leq 2000$

• 对于$50\%$的数据：$n\leq 10^5\quad m\leq 2000$

• 对于$100\%$的数据：$1\leq m< n\leq 10^5\quad 1\leq k<n$

题解

首先观察样例，我们可以发现每一次“代沟”出现其实是将这条代沟左右两边的向日葵阻断，设左边有向日葵$x$个，右边有向日葵$y$个，即出现无法交流的向日葵对数为$x*y$对。

具体实现我使用了线段树，区间批量修改每个点的当前所在区间的最左点和最右点，总时间复杂度为$O(nlogn)$。

代码实现

#include<iostream>
#include<array>
#include<algorithm>
#include<cmath>
using namespace std;
using gg=int;
struct node{
	gg l,r;
}zero;
array<node,400010> tree,tag;
gg n,m;
void pushdown(const gg &p)
{
	if(tag[p].l)
	{
		tag[p*2]=tag[p*2+1]=tree[p*2]=tree[p*2+1]=tag[p];
		tag[p]=zero;
	}
	return;
}
void build(const gg &l,const gg &r,const gg &p)
{
	if(l==r)
	{
		tree[p].l=1;
		tree[p].r=n;
		return;
	}
	gg mid=(l+r)/2;
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
	return;
}
void update(const gg &l,const gg &r,const gg &nl,const gg &nr,const gg &p,const node &k)
{
	if(nl>=l&&nr<=r)
	{
		tree[p]=tag[p]=k;
		return;
	}
	pushdown(p);
	gg mid=(nl+nr)/2;
	if(mid>=l)
	{
		update(l,r,nl,mid,p*2,k);
	}
	if(mid+1<=r)
	{
		update(l,r,mid+1,nr,p*2+1,k);
	}
	return;
}
node getpoi(const gg &x,const gg &nl,const gg &nr,const gg &p)
{
	if(nl==nr)
	{
		return tree[p];
	}
	pushdown(p);
	gg mid=(nl+nr)/2;
	if(mid>=x) return getpoi(x,nl,mid,p*2);
	else return getpoi(x,mid+1,nr,p*2+1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	gg x;
	cin>>n>>m;
	build(1,n,1);
	while(m--)
	{
		cin>>x;
		node ll=getpoi(x,1,n,1),rr=getpoi(x+1,1,n,1);
		if(ll.l!=rr.l&&ll.r!=rr.r)
		{
			cout<<0<<'\n';
		}
		else
		{
			cout<<(x-ll.l+1)*(rr.r-x)<<'\n';
			update(ll.l,x,1,n,1,{ll.l,x});
			update(x+1,rr.r,1,n,1,{x+1,rr.r});
		}
	}
	return 0;
}

Ps:还有更快的离线做法…似乎是倒着加边然后用带权并查集维护…