专栏文章

题解：P9986 [Ynoi2079] r2pspc

wwwt100127
P9986题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipf1o1m
此快照首次捕获于
2025/12/03 10:56
3 个月前
此快照最后确认于
2025/12/03 10:56
3 个月前
查看原文

题意

给定序列 aa，qq 组询问给定 L,RL,R，求 popcount(∑i=LR2ai){\rm popcount}(\sum_{i=L}^{R}2^{a_i})。
其中 n≤1×105,q≤1×106n \le 1 \times 10^5,q \le 1 \times 10^6。

思路

First

由 Ynoi 和没有强制在线，猜出是莫队不过分吧……
容易想到莫队，修改的时候暴力的查找大于它的位中是 00 的最小的。
按理说这做法拿不了几分的，但是 9696 分。
本部分的代码如下：
CPP
const int N=1e6+5;
int n,m,t,a[N];
namespace Lisanhua
{
	unordered_map<int,int> Map;
	int A[N],cnt;
	int Get(int x)
	{
		return lower_bound(A+1,A+1+cnt,x)-A;
	}
	int solve()
	{
		int i,x;
		for(i=1;i<=n;i++)
		{
			x=a[i];
			while(Map[x])
			{
				Map[x]=0;
				x++;
			}
			Map[x]=1;
		}
		for(auto t:Map) A[++cnt]=t.fi;
		sort(A+1,A+1+cnt);
		cnt=unique(A+1,A+1+cnt)-A-1;
		for(i=1;i<=n;i++) a[i]=Get(a[i]);
		return cnt;
	}
}

struct Query{int L,R,id;}q[N*10];
bool comp(const Query &a,const Query &b)
{
	if(a.L/t!=b.L/t) return a.L<b.L;
	return (a.L/t)&1? a.R<b.R:a.R>b.R;
}
int ans[N],cnt[N],Answer;
void ADD(int x)
{
	while(cnt[x])
	{
		Answer--;
		cnt[x]--;
		x++;
	}
	Answer++;
	cnt[x]++;
}
void DEL(int x)
{
	while(!cnt[x])
	{
		Answer++;
		cnt[x]++;
		x++;
	}
	Answer--;
	cnt[x]--;
}
void Never_Give_up()
{
	int i,L,R;
	read(n,m); t=sqrt(n);
	for(i=1;i<=n;i++) a[i]=read();
	Lisanhua::solve();
	for(i=1;i<=m;i++) read(q[i].L,q[i].R),q[i].id=i;
	sort(q+1,q+1+m,comp);
	for(i=1,L=1,R=0;i<=m;i++)
	{
		while(L>q[i].L) ADD(a[--L]);
		while(R<q[i].R) ADD(a[++R]);
		while(L<q[i].L) DEL(a[L++]);
		while(R>q[i].R) DEL(a[R--]);
		ans[q[i].id]=Answer;
	}
	for(i=1;i<=m;i++) write(ans[i],'\n');
}

Second

考虑怎么在这个基础上优化。
每次暴力的找 00 实在是太慢了，怎么卡都过不去。考虑在这上面优化。
惊奇的发现：每个位置只有 00 和 11 两种取值。
感觉可以用 bitset 优化（其实这个优化更像是分块）！

Code

由于本题用 bitset 优化没有压位好写，代码用压位。
CPP
#define Count_Number(x) __builtin_popcountll(x)
const int N=1e5+5;
const int M=1e9/32+5;
int n,m,t,a[N],ans[10*N];
struct Query{int L,R,id;}q[10*N];
bool comp(const Query &a,const Query &b)
{
	if(a.L/t!=b.L/t) return a.L<b.L;
	return (a.L/t)&1? a.R<b.R:a.R>b.R;
}
long long cnt[M];
int Answer;
void ADD(int x)
{
	int A=x>>5,B=x&31;
	Answer-=Count_Number(cnt[A]);
	cnt[A]+=1ll<<B;
	while(cnt[A]>>32)
	{
		Answer-=Count_Number(cnt[A+1]);
		cnt[A+1]+=cnt[A]>>32;
		cnt[A]&=(1ll<<32)-1;
		Answer+=Count_Number(cnt[A++]);
	}
	Answer+=Count_Number(cnt[A]);
}
void DEL(int x)
{
	int A=x>>5,B=x&31;
	Answer-=Count_Number(cnt[A]);
	cnt[A]-=1ll<<B;
	while(cnt[A]<0)
	{
		Answer-=Count_Number(cnt[A+1]);
		cnt[A+1]--;
		cnt[A]+=(1ll<<32);
		Answer+=Count_Number(cnt[A++]); 
	}
	Answer+=Count_Number(cnt[A]);
}

void I_Love_her_Forever()
{
	int i,L,R;
	read(n,m); t=sqrt(n);
	for(i=1;i<=n;i++) a[i]=read();
	for(i=1;i<=m;i++) read(q[i].L,q[i].R),q[i].id=i;
	sort(q+1,q+1+m,comp);
	for(i=1,L=1,R=0;i<=m;i++)
	{
		while(L>q[i].L) ADD(a[--L]);
		while(R<q[i].R) ADD(a[++R]);
		while(L<q[i].L) DEL(a[L++]);
		while(R>q[i].R) DEL(a[R--]);
		ans[q[i].id]=Answer;
	}
	for(i=1;i<=m;i++) write(ans[i],'\n');
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...