「czy系列赛」czy的后宫3

2014年7月19日10,1584

czy的后宫3

「题目描述」

上次czy在机房妥善安排了他的后宫之后，他发现可以将他的妹子分为c种，他经常会考虑这样一个问题：在[l,r]的妹子中间，能挑选出多少不同类型的妹子呢？

注意：由于czy非常丧尸，所以他要求在所挑选的妹子类型在[l,r]中出现次数为正偶数，你懂得。

问题简述:n个数，m次询问，每次问[l,r]区间有多少个数恰好出现正偶数次

「输入格式」

第一行3个整数，表示n,c,m

第二行n个数，每个数Ai在[1,c]之间，表示一个Ai类型的妹子

接下来m行，每行两个整数l,r，表示询问[l,r]这个区间的答案

「输出格式」

有m行，表示第i次询问的答案

「样例输入」

5 5 3

1 1 2 2 3

1 5

3 4

2 3

「样例输出」

「数据范围」

共有10组测试数据

1-4组n,m=500，2000，5000，10000，c=1000

5-7组n,m=20000，30000，40000，c=10000

8-10组n,m=50000，80000，100000，c=100000

数据保证随机生成

「题解」

本题改编自bzoj作诗，但是不强制在线

算法1：n^2暴力

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define inf 0x7fffffff
#define ll long long
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,c;
int a[100005],tmp[100005];
int que(int x,int y)
{
	int ans=0;
	for(int i=x;i<=y;i++)
	{
	    tmp[a[i]]++;
	    if(tmp[a[i]]%2==0)ans++;
	    else if(tmp[a[i]]!=1)ans--;
	}
	for(int i=x;i<=y;i++)
	    tmp[a[i]]=0;
	return ans;
}
int main()
{
    //freopen("harem.in","r",stdin);
    //freopen("harem.out","w",stdout);
	n=read();c=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++)
    {
    	int x=read(),y=read();
    	printf("%d\n",que(x,y));
    }
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<cmath>

#define inf 0x7fffffff

#define ll long long

using namespace std;

inline ll read()

{

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

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

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

return x*f;

}

int n,m,c;

int a[100005],tmp[100005];

int que(int x,int y)

{

int ans=0;

for(int i=x;i<=y;i++)

{

tmp[a[i]]++;

if(tmp[a[i]]%2==0)ans++;

else if(tmp[a[i]]!=1)ans--;

}

for(int i=x;i<=y;i++)

tmp[a[i]]=0;

return ans;

}

int main()

{

//freopen("harem.in","r",stdin);

//freopen("harem.out","w",stdout);

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

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

for(int i=1;i<=m;i++)

{

int x=read(),y=read();

printf("%d\n",que(x,y));

}

return 0;

}

算法2：分块，同作诗

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define inf 0x7fffffff
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,c,m,block,cnt;
int L[1505],R[1505],f[1505][1505];
int a[100005],belong[100005],tmp[100005],first[100005],last[100005];
bool mark[100005];
struct data{int p,v;}b[100005];
inline bool operator<(data a,data b)
{
    return (a.v<b.v)||(a.v==b.v&&a.p<b.p);
}
void pre()
{
    int tot;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=L[i];j<=n;j++)tmp[a[j]]=0;
        tot=0;
        for(int j=L[i];j<=n;j++)
        {
            if(!(tmp[a[j]]&1)&&tmp[a[j]])tot--;
            tmp[a[j]]++;
            if(!(tmp[a[j]]&1))tot++;
            f[i][belong[j]]=tot;
        }
    }
    for(int i=1;i<=n;i++)
        b[i].p=i,b[i].v=a[i];
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
    {
        if(!first[b[i].v])first[b[i].v]=i;
        last[b[i].v]=i;
    }
}
int findup(int x,int v)
{
    int l=first[v],r=last[v];
    int tmp=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(x<b[mid].p)r=mid-1;
        else {l=mid+1;tmp=mid;}
    }
    return tmp;
}
int finddown(int x,int v)
{
    int l=first[v],r=last[v];
    int tmp=inf;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(x>b[mid].p)l=mid+1;
        else {tmp=mid;r=mid-1;}
    }
    return tmp;
}
int find(int x,int y,int v)
{
    return max(findup(y,v)-finddown(x,v)+1,0);
}
int que(int x,int y)
{
    int ans=0,t1,t2,a1,bx=belong[x],by=belong[y];
    if(bx==by||bx+1==by)
    {
        for(int i=x;i<=y;i++)
        {
            a1=a[i];if(mark[a1])continue;
            int t=find(x,y,a1);
            if(!(t&1)){mark[a1]=1;ans++;}
        }
        for(int i=x;i<=y;i++)mark[a[i]]=0;
    }
    else
    {
        int l=L[bx+1],r=R[by-1];
        ans=f[bx+1][by-1];
        for(int i=x;i<l;i++)
        {
            a1=a[i];if(mark[a1])continue;
            t1=find(x,y,a1),t2=find(l,r,a1);
            if(!(t1&1))
                {if((t2&1)||!t2)ans++;}
            else if(!(t2&1)&&t2)ans--;
            mark[a1]=1;
        }
        for(int i=r+1;i<=y;i++)
        {
            a1=a[i];if(mark[a1])continue;
            t1=find(x,y,a1),t2=find(l,r,a1);
            if(!(t1&1))
                {if((t2&1)||!t2)ans++;}
            else if(!(t2&1)&&t2)ans--;
            mark[a1]=1;
        }
        for(int i=x;i<l;i++)mark[a[i]]=0;
        for(int i=r+1;i<=y;i++)mark[a[i]]=0;
    }
    return ans;
}
int main()
{
	//freopen("harem.in","r",stdin);
	//freopen("harem.out","w",stdout);
    n=read();c=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    block=(int)sqrt((double)n/log((double)n)*log(2.0));
    if(n%block)cnt=n/block+1;
    else cnt=n/block;
    for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;
    for(int i=1;i<=cnt;i++)
        L[i]=(i-1)*block+1,R[i]=i*block;
    R[cnt]=n;
    pre();
    for(int i=1;i<=m;i++)
    {
        int l=read(),r=read();
        printf("%d\n",que(l,r));
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<cmath>

#define inf 0x7fffffff

using namespace std;

inline int read()

{

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

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

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

return x*f;

}

int n,c,m,block,cnt;

int L[1505],R[1505],f[1505][1505];

int a[100005],belong[100005],tmp[100005],first[100005],last[100005];

bool mark[100005];

struct data{int p,v;}b[100005];

inline bool operator<(data a,data b)

{

return (a.v<b.v)||(a.v==b.v&&a.p<b.p);

}

void pre()

{

int tot;

for(int i=1;i<=cnt;i++)

{

for(int j=L[i];j<=n;j++)tmp[a[j]]=0;

tot=0;

for(int j=L[i];j<=n;j++)

{

if(!(tmp[a[j]]&1)&&tmp[a[j]])tot--;

tmp[a[j]]++;

if(!(tmp[a[j]]&1))tot++;

f[i][belong[j]]=tot;

}

for(int i=1;i<=n;i++)

b[i].p=i,b[i].v=a[i];

sort(b+1,b+n+1);

for(int i=1;i<=n;i++)

{

if(!first[b[i].v])first[b[i].v]=i;

last[b[i].v]=i;

}

int findup(int x,int v)

{

int l=first[v],r=last[v];

int tmp=0;

while(l<=r)

{

int mid=(l+r)>>1;

if(x<b[mid].p)r=mid-1;

else {l=mid+1;tmp=mid;}

}

return tmp;

}

int finddown(int x,int v)

{

int l=first[v],r=last[v];

int tmp=inf;

while(l<=r)

{

int mid=(l+r)>>1;

if(x>b[mid].p)l=mid+1;

else {tmp=mid;r=mid-1;}

}

return tmp;

}

int find(int x,int y,int v)

{

return max(findup(y,v)-finddown(x,v)+1,0);

}

int que(int x,int y)

{

int ans=0,t1,t2,a1,bx=belong[x],by=belong[y];

if(bx==by||bx+1==by)

{

for(int i=x;i<=y;i++)

{

a1=a[i];if(mark[a1])continue;

int t=find(x,y,a1);

if(!(t&1)){mark[a1]=1;ans++;}

}

for(int i=x;i<=y;i++)mark[a[i]]=0;

}

else

{

int l=L[bx+1],r=R[by-1];

ans=f[bx+1][by-1];

for(int i=x;i<l;i++)

{

a1=a[i];if(mark[a1])continue;

t1=find(x,y,a1),t2=find(l,r,a1);

if(!(t1&1))

{if((t2&1)||!t2)ans++;}

else if(!(t2&1)&&t2)ans--;

mark[a1]=1;

}

for(int i=r+1;i<=y;i++)

{

a1=a[i];if(mark[a1])continue;

t1=find(x,y,a1),t2=find(l,r,a1);

if(!(t1&1))

{if((t2&1)||!t2)ans++;}

else if(!(t2&1)&&t2)ans--;

mark[a1]=1;

}

for(int i=x;i<l;i++)mark[a[i]]=0;

for(int i=r+1;i<=y;i++)mark[a[i]]=0;

}

return ans;

}

int main()

{

//freopen("harem.in","r",stdin);

//freopen("harem.out","w",stdout);

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

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

block=(int)sqrt((double)n/log((double)n)*log(2.0));

if(n%block)cnt=n/block+1;

else cnt=n/block;

for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;

for(int i=1;i<=cnt;i++)

L[i]=(i-1)*block+1,R[i]=i*block;

R[cnt]=n;

pre();

for(int i=1;i<=m;i++)

{

int l=read(),r=read();

printf("%d\n",que(l,r));

}

return 0;

}

算法3：离线+树状数组

按照所有询问的左端点排序

一开始建树状数组，记录1-x的答案

now=1，从左往右扫

如果now<q[i].l，考虑删除a[now]对于答案的影响，若a[now]值为v

显然v1-v2即now到下一个v出现的位置，答案+1，

v2-v3答案-1，以此类推，用树状数组依次维护

now=q[i].l时记录下q[i].ana，即在树状数组中查询q[i].l-q[i].r的答案

询问每次是logn的，但是now指针向右移动时，花费的时间为a[now]在now之后中出现次数x*logn

但是由于数据是完全随机的，我们可以认为某一个数字出现次数是比较少的

算法4：同上

对于算法3，可以构造数据，某个数字出现次数很多使得其复杂度为n^2logn

所以我们可以采取一些办法使得算法变得“靠谱”

以√n为界，出现次数大于√n的数字不超过√n个

出现次数小于√n的可能有n个

每次查询q[i].l-q[i].r的时候，答案由两部分构成

1.出现次数小于√n的我们依然维护这些数对答案贡献的树状数组，直接在树状数组中查询 logn

2.出现次数大于√n的数，每一个数维护树状数组，我们可以得出q[i].l-q[i].r每一个数出现的次数，是偶数就将答案+1 √nlogn

总询问复杂度nlogn+n√nlogn

考虑删去一个数，它出现次数小于√n，则直接在答案树状数组上操作√nlogn

否则就在以这个数为次数建立的树状数组上操作logn

俩种操作最多都是n次，总复杂度nlogn+n√nlogn

复杂度和分块差不多

算法5：莫队算法

这个没学过的话自行百度，会的话应该分分钟水过的吧，复杂度n√n，常数小

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
inline ll read()
{
	ll 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*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,c,m,block;
int a[100005],belong[100005];
int tmp[100005];
struct data{int l,r,ans,id;}q[100005];
inline bool operator<(data a,data b)
{
	return (belong[a.l]<belong[b.l])||(belong[a.l]==belong[b.l]&&a.r<b.r);
}
inline bool cmp(data a,data b)
{
	return a.id<b.id;
}
void solve()
{
	int l=0,r=0;
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		while(r<q[i].r)
		{
			r++;
	 	    tmp[a[r]]++;
	        if(tmp[a[r]]%2==0)ans++;
	        if(tmp[a[r]]%2==1&&tmp[a[r]]!=1)ans--;
	 	}
	 	while(l>q[i].l)
	 	{
	 		l--;
	 		tmp[a[l]]++;
	        if(tmp[a[l]]%2==0)ans++;
	        if(tmp[a[l]]%2==1&&tmp[a[l]]!=1)ans--;
	 	}
		while(l<q[i].l)
		{
			tmp[a[l]]--;
			if(tmp[a[l]]%2==0&&tmp[a[l]]!=0)ans++;
			if(tmp[a[l]]%2==1)ans--;
			l++;
		}
	 	while(r>q[i].r)
	 	{
	        tmp[a[r]]--;
			if(tmp[a[r]]%2==0&&tmp[a[r]]!=0)ans++;
			if(tmp[a[r]]%2==1)ans--;
			r--;
	 	}
	 	q[i].ans=ans;
	}
}
int main()
{
	//freopen("harem.in","r",stdin);
	//freopen("harem.out","w",stdout);
	n=read();c=read();m=read();
	block=(int)sqrt((double)n);
	for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=m;i++)
	    q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+m+1);
	solve();
	sort(q+1,q+m+1,cmp);
	for(int i=1;i<=m;i++)
	    printf("%d\n",q[i].ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

inline ll read()

{

ll 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*10+ch-'0';ch=getchar();}

return x*f;

}

int n,c,m,block;

int a[100005],belong[100005];

int tmp[100005];

struct data{int l,r,ans,id;}q[100005];

inline bool operator<(data a,data b)

{

return (belong[a.l]<belong[b.l])||(belong[a.l]==belong[b.l]&&a.r<b.r);

}

inline bool cmp(data a,data b)

{

return a.id<b.id;

}

void solve()

{

int l=0,r=0;

int ans=0;

for(int i=1;i<=m;i++)

{

while(r<q[i].r)

{

r++;

tmp[a[r]]++;

if(tmp[a[r]]%2==0)ans++;

if(tmp[a[r]]%2==1&&tmp[a[r]]!=1)ans--;

}

while(l>q[i].l)

{

l--;

tmp[a[l]]++;

if(tmp[a[l]]%2==0)ans++;

if(tmp[a[l]]%2==1&&tmp[a[l]]!=1)ans--;

}

while(l<q[i].l)

{

tmp[a[l]]--;

if(tmp[a[l]]%2==0&&tmp[a[l]]!=0)ans++;

if(tmp[a[l]]%2==1)ans--;

l++;

}

while(r>q[i].r)

{

tmp[a[r]]--;

if(tmp[a[r]]%2==0&&tmp[a[r]]!=0)ans++;

if(tmp[a[r]]%2==1)ans--;

r--;

}

q[i].ans=ans;

}

int main()

{

//freopen("harem.in","r",stdin);

//freopen("harem.out","w",stdout);

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

block=(int)sqrt((double)n);

for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;

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

for(int i=1;i<=m;i++)

q[i].l=read(),q[i].r=read(),q[i].id=i;

sort(q+1,q+m+1);

solve();

sort(q+1,q+m+1,cmp);

for(int i=1;i<=m;i++)

printf("%d\n",q[i].ans);

return 0;

}

« 「BZOJ3688」「FJ2014集训」折线统计「BZOJ3626」[LNOI2014] LCA »

沙狼阿折

分块的思想是什么啊

cyy489

请问大神莫队算法和分块有什么区别？我一直以为是一样的。。。

Believe

czy系列赛是什么？？

hzwer.com _ Home | http://hzwer.com

「czy系列赛」czy的后宫3

分类目录

热门文章

Myfriends

近期评论