自动搬运

查看原文

来自洛谷，原作者为

	xxxxxzy 111

搬运于2025-08-24 22:53:40，当前版本为作者最后更新于2024-01-02 18:11:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[Ynoi2079] r2pspc题解

题目传送门

（看能不能来个首发，求求管理员给个过吧）

看到题目，不要求强制在线，想到莫队算法。

数据范围比较大，但是发现其实很多数值并没有用到，所以要先进行离散化。

只需要把可能出现的数位丢进去离散化就可以了。

然后对于莫队的 $add$ 和 $del$，给一种超时 $96$ 分的写法：

void add(int x){
	int p=a[x];
	while(c[p]) c[p]=0,tmp--,p++;
	tmp++,c[p]=1;
}
void del(int x){
	int p=a[x];
	while(!c[p]) c[p]=1,tmp++,p++;
	tmp--,c[p]=0;
}

这样时间复杂度好像是 $O(nm)$，会超时 (但是数据好像比较水并且根本卡不满所以有 $96$ 分)。

考虑优化这个过程，可以用高效的加法对上面的 $c$ 数组进行压位，时间复杂度就可以通过此题。(但是复杂度好像是 $\dfrac{nm}{64}$，但是所有点都能在 0.5s 以内跑过），成功抢到最优解。

给出代码：

#include<bits/stdc++.h>
#define int long long
#define siz2 60
using namespace std;
int power[100];
int n,m,a[400005],ans[1000005],cnt=1,pos[400005],siz,len,tmp,b[5000005],l2[400005],r2[400005],pos2[400005],len2;
namespace ae86{
    const int bufl=1<<18;
    char buf[bufl],*s=buf,*t=buf;
    inline int fetch(){
        if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
        return*s++;
    }
    inline int read(){
        int a=0,c=fetch();
        while(!isdigit(c)) c=fetch();
        while(isdigit(c))a=a*10+c-48,c=fetch();
        return a;
    }
}
using ae86::read;
struct node{
	int l,r,d,id;
}tt[1000005];
bool cmp(node a,node b){
	if(pos[a.l]!=pos[b.l]) return a.l<b.l;
	if(pos[a.l]%2==1) return a.r<b.r;
	return a.r>b.r;
}
bool c[3000005];
unsigned int g[3000005];
inline void add(int x){
	int pos=pos2[x],l=l2[pos2[x]],r=r2[pos2[x]];
	tmp-=__builtin_popcountll(g[pos]);
	g[pos]+=power[x-l];
	if(g[pos]>=power[siz2]){
		g[pos]-=power[siz2];
		int q=pos+1;
		while(g[q]==power[siz2]-1) g[q]=0,q++,tmp-=siz2;
		tmp-=__builtin_popcountll(g[q]);
		g[q]++;
		tmp+=__builtin_popcountll(g[q]);
	}
	tmp+=__builtin_popcountll(g[pos]);
}
inline void del(int x){
	int pos=pos2[x],l=l2[pos2[x]],r=r2[pos2[x]];
	tmp-=__builtin_popcountll(g[pos]);
	if(g[pos]<power[x-l]){
		g[pos]+=power[siz2]-power[x-l];
		int q=pos+1;
		while(g[q]==0) g[q]=power[siz2]-1,q++,tmp+=siz2;
		tmp-=__builtin_popcountll(g[q]);
		g[q]--;
		tmp+=__builtin_popcountll(g[q]);
	}else g[pos]-=power[x-l];
	tmp+=__builtin_popcountll(g[pos]);
}
unordered_map<int,int> un;
inline void write(int x){
	if(x<=9) return putchar(x+'0'),void();
	write(x/10); putchar(x%10+'0');
}
signed main(){
	n=read(),m=read();
	power[0]=1;
	for(int i=1;i<=60;i++) power[i]=power[i-1]<<1ll;
	for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
	len2=n/siz2+(n%siz2==0?0:1);
	for(int i=1;i<=len2;i++){//对ull分块
		l2[i]=(i-1)*siz2+1,r2[i]=min(i*siz2,n);
		for(int j=l2[i];j<=r2[i];j++) pos2[j]=i; 
	}
	for(int i=1;i<=n;++i){//离散化，存下每一个可能出现的数位
		int v=a[i];
		while(un[v]){
			un[v]=0;
			++v;
		}
		un[v]=1;
	}
	int tot=0;
	for(auto p:un) b[++tot]=p.first;
	sort(b+1,b+1+tot);
	for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
	siz=sqrt(n);
	len=n/siz+(n%siz==0?0:1);
	for(int i=1;i<=len;i++){
		for(int j=(i-1)*siz+1;j<=min(i*siz,n);j++) pos[j]=i;
	}
	for(int i=1;i<=m;i++) tt[i].l=read(),tt[i].r=read(),tt[i].id=i;
//	if(n<=2000||m<=2000) clac();
	sort(tt+1,tt+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){//莫队
		while(tt[i].l<l) add(a[--l]);
		while(tt[i].r>r) add(a[++r]);
		while(tt[i].l>l) del(a[l++]);
		while(tt[i].r<r) del(a[r--]);
		ans[tt[i].id]=tmp;
	}
	for(int i=1;i<=m;i++) write(ans[i]),putchar('\n');
}

做麻了直接刷屏了。。。。