[bzoj 4939][Ynoi 2016]掉进兔子洞

传送门

Description

一个长为 n 的序列 a。

有 m 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。

注意这里删掉指的是一个一个删，不是把等于这个值的数直接删完，

比如三个区间是 [1,2,2,3,3,3,3] , [1,2,2,3,3,3,3] 与 [1,1,2,3,3]，就一起扔掉了 1 个 1，1 个 2，2 个 3。

Solution

弱化版是luoguP3674，这里放上它的题解戳我

要找相同的元素就是集合求交集，莫队+bitset即可

可是这道题是要算上重复的元素的，很简单，离散化的时候给每个数留下相应的空位就行了

即每个数的离散值等于小于它的数个数+1.

几个例子：

我们把序列3 3 5 5 6 7 7，离散化成1 1 3 3 5 6 6，而不是1 1 2 2 3 4 4

那么，我们在加入数的时候，把它加到“它的离散值+它出现的次数-1”这个位置上

那么求交就是now.count()

还有一个问题，维护\(100000*100000\)的bitset！虽然看上去不太可能，但其实上我们分成3次莫队就行了

Code

#include<bits/stdc++.h>

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

#define MN 100005

int n,m,a[MN],T,nums[MN];

std::bitset<MN> now;

std::bitset<MN> quer[33343];

struct ques{

    int l,r,id,pl;

    bool operator <(const ques&o)const{return (pl^o.pl)?(pl<o.pl):((pl&1)?r<o.r:r>o.r);}

}q[MN+33343];

int num[MN],len[MN];

inline void solve(int L,int R)

{

	if(L>R) return;

	register int tt=0,i;

	for(i=1;i<=R-L+1;++i)

    {

    	quer[i].set();

    	q[++tt].l=read(),q[tt].r=read();q[tt].pl=(q[tt].l-1)/T+1;q[tt].id=i;len[i] =q[tt].r-q[tt].l+1;

    	q[++tt].l=read(),q[tt].r=read();q[tt].pl=(q[tt].l-1)/T+1;q[tt].id=i;len[i]+=q[tt].r-q[tt].l+1;

    	q[++tt].l=read(),q[tt].r=read();q[tt].pl=(q[tt].l-1)/T+1;q[tt].id=i;len[i]+=q[tt].r-q[tt].l+1;

    }

	std::sort(q+1,q+tt+1);

    register int l=1,r=0;now.reset();

    memset(num,0,sizeof num);

	for(i=1;i<=tt;++i)

    {

        for(;r<q[i].r;++r) num[a[r+1]]++,now[a[r+1]+num[a[r+1]]-1]=1;

        for(;l>q[i].l;--l) num[a[l-1]]++,now[a[l-1]+num[a[l-1]]-1]=1;

        for(;r>q[i].r;--r) now[a[r]+num[a[r]]-1]=0,--num[a[r]];

        for(;l<q[i].l;++l) now[a[l]+num[a[l]]-1]=0,--num[a[l]];

        quer[q[i].id]&=now;

    }

    for(i=1;i<=R-L+1;++i) printf("%d\n",len[i]-3*quer[i].count());

}

int main()

{

    n=read();m=read();

    register int i;T=ceil(sqrt((double)n));

    for(i=1;i<=n;++i) nums[i]=a[i]=read();

    std::sort(nums+1,nums+n+1);

    for(i=1;i<=n;++i) a[i]=std::lower_bound(nums+1,nums+n+1,a[i])-nums;

    int N1=m/3+1,N2=2*N1;

    solve(1,min(N1,m));solve(min(N1,m)+1,min(N2,m));solve(min(N2,m)+1,m);

    return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

[bzoj 4939][Ynoi 2016]掉进兔子洞

传送门

Description

Solution

Code

最新文章

热门文章