题解：P9986 [Ynoi2079] r2pspc

给个理论打不过

O(n\sqrt q)

，实测干不过

O(\frac{nq}{w})

，但可能有点意思的做法。

首先值域可以简化成严格

n

之内，方法是把暴力计算

\sum_{i=1}^n 2^{a_i}

时始终没变化的位全删掉。

然后考虑对一个数加

2^{a_i}

究竟在干啥，就是将最低的比

a_i

高的

0

和中间连续的

1

分别变为

1

和

0

。如果我们能快速维护出连续

1

段并支持单点改，或许就能用莫队做出来了。

当只有二进制加法时，每次操作改变的位数是

O(1)

的，因此考虑不删莫队。在莫队右端点拓展的时候，我们可能会合并两段、在某段删除插入一个元素，容易想到直接用并查集维护。由于要删除元素所以改成 leafy 的，也就是代表

n

个二进制位的结点全是叶子，中间结点是辅助维护联通性的。这么做的正确性一在于每次插入或删除的元素都在段的边缘（不用支持分裂段），二是删除元素不会增加并查集势能，所以均摊复杂度还是对的。

不过拓展左端点时就不能在并查集上做修改操作了，否则需要撤销复杂度就不对了。发现如果加入的

2^{a_i}

是严格递减的就很容易维护，因为后面加入

2^{a_i}

涉及的连续

1

段有多长，只跟

a_i

在并查集中所处的段，以及上次加入

2^{a_j}

后

a_j

所在的段如何有关。所以把块中所有

a_i

排序，查询时从大到小扫，处理出块内

\sum 2^{a_i}

从高到低哪些二进制位为

1

，就能只用并查集 Find 算出答案了。

路径压缩+按秩合并就能做到单次查询/修改均摊

O(\alpha(n))

，至于这玩意能否改成

O(1)

，反正直接序列线性并查集是不对的，因为并查集结点数量并非

\frac{n}{w}

。丘老师指出：

我没看懂 /ll

时间

O(n\sqrt q\ \alpha(n)+q)

，空间

O(n+q)

。容易发现题解区只有 bitset 的做法给了代码，所以我喜提最劣解。参考代码：

CPP

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5,MAXM=1e6,SIZE=2e5;

int Read()
{
	int res=0;char c;
	while(!isdigit(c=getchar()));
	while(isdigit(c)) res=res*10+c-'0',c=getchar();
	return res;
}
void Print(int x)
{
	if(x<10) {putchar('0'+x);return;}
	int y=x/10; Print(y),putchar('0'+x-y*10);
}

int n,m,A[MAXN+5],Q[MAXN+5];
int ql[MAXM+5],qr[MAXM+5],ans[MAXM+5];
bool B[MAXN+5];int tim[MAXN+5],T;
int stk[MAXN+5],tp;
int S,Bloc[MAXN+5];

bool cmp(int a,int b) {return A[a]<A[b];}

int Head[MAXN+5],nxt[MAXM+5];
void Insert(int x,int v) {nxt[v]=Head[x],Head[x]=v;}

int fa[SIZE+5],h[SIZE+5],lef[SIZE+5],tot;
int Find(int x) {return fa[x]==x ? x : fa[x]=Find(fa[x]);}
int Union(int a,int b)
{
	a=Find(a),b=Find(b);
	lef[b]=lef[a];
	if(h[a]<h[b]) swap(a,b);
	fa[b]=a,h[a]=max(h[a],h[b]+1);
	return a;
}

int main()
{
	n=Read(),m=Read();
	for(int i=1;i<=n;i++) A[i]=Read(),Q[i]=i;
	sort(Q+1,Q+n+1,cmp);
	for(int i=1,j,cnt=0,rnk=1;i<=n;i=j)
	{
		j=i; while(j<=n && A[Q[j]]==A[Q[i]]) ++j;
		int d=A[Q[j]]-A[Q[i]];
		for(int k=i;k<j;k++) A[Q[k]]=rnk;
		cnt+=j-i;
		rnk+=min(cnt,d),cnt=max(0,cnt-d);
	}
	S=ceil(1.0*n/sqrt(m));
	for(int i=1,L=1,R;L<=n;i++,L=R) {R=min(n+1,L+S); for(int j=L;j<R;j++) Bloc[j]=i;}
	for(int i=1;i<=m;i++)
	{
		ql[i]=Read(),qr[i]=Read();
		if(Bloc[ql[i]]==Bloc[qr[i]])
		{
			++T;
			for(int j=ql[i];j<=qr[i];j++)
			{
				int x=A[j];
				while(tim[x]==T && B[x]) --ans[i],B[x++]=0;
				++ans[i],tim[x]=T,B[x]=1;
			}
		}
		else Insert(qr[i],i);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=Head[i],k;j;j=k) k=nxt[j],Insert(Bloc[ql[j]],j);
		Head[i]=0;
	}
	stk[0]=n+1;
	for(int i=1,L=1,R;L<=n;i++,L=R+1)
	{
		R=min(n,L+S-1);
		if(!Head[i]) continue;
		for(int j=1;j<=S;j++) Q[j]=L+j-1;
		sort(Q+1,Q+S+1,cmp);
		for(int j=1;j<=n+1;j++) fa[j]=j; tot=n+1;
		int pre=0;
		for(int j=Head[i],k;j;pre=j,j=k) k=nxt[j],nxt[j]=pre;
		Head[i]=pre;
		int MoR=R,cnt=0;
		for(int j=Head[i];j;j=nxt[j])
		{
			while(MoR<qr[j])
			{
				int x=A[++MoR];
				if(fa[x]==x)//zero
				{
					if(fa[x-1]!=x-1)
					{
						if(fa[x+1]!=x+1) fa[x]=Union(x+1,x-1);
						else lef[fa[x]=Find(x-1)]=x;
					}
					else if(fa[x+1]!=x+1) fa[x]=Find(x+1);
					else fa[x]=++tot,fa[tot]=tot,h[tot]=1,lef[tot]=x;
				}
				else
				{
					lef[Find(x)]=x-1;
					while(fa[x]!=x) fa[x]=x,--cnt,++x;
					if(fa[x+1]!=x+1) fa[x]=Find(x+1);
					else fa[x]=++tot,fa[tot]=tot,h[tot]=1,lef[tot]=x;
				}
				++cnt;
			}
			tp=0;
			for(int k=S;k;k--)
				if(Q[k]>=ql[j])
				{
					int x=A[Q[k]];
					while(stk[tp]==x) --tp,++x;
					stk[++tp]=x;
				}
			ans[j]=cnt;
			int lst=n;
			for(int k=1;k<=tp;k++)
				if(fa[stk[k]]==stk[k])
				{
					++ans[j];
					if(stk[k-1]==stk[k]+1) continue;
					if(fa[stk[k]+1]==stk[k]+1) {lst=stk[k];continue;}
					int x=Find(stk[k]+1);
					if(Find(stk[k-1]-1)!=x) lst=lef[x];
				}
				else
				{
					int x=Find(stk[k]);
					if(Find(stk[k-1]-1)==x) ans[j]-=lst-stk[k];
					else ans[j]-=lef[x]-stk[k];
					lst=stk[k]-1;
				}
		}
	}
	for(int i=1;i<=m;i++) Print(ans[i]),putchar('\n');
	return 0;
}

题解：P9986 [Ynoi2079] r2pspc

文章操作

相关推荐

评论

题解：P9986 [Ynoi2079] r2pspc