「BZOJ2821」作诗(Poetize)

2014年7月19日8,2183

Description

神犇SJY虐完HEOI之后给傻×LYD出了一题：
SHY是T国的公主，平时的一大爱好是作诗。
由于时间紧迫，SHY作完诗之后还要虐OI，于是SHY找来一篇长度为N的文章，阅读M次，每次只阅读其中连续的一段[l,r]，从这一段中选出一些汉字构成诗。因为SHY喜欢对偶，所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。于是SHY请LYD安排选法。
LYD这种傻×当然不会了，于是向你请教……
问题简述：N个数，M组询问，每次问[l,r]中有多少个数出现正偶数次。

Input

输入第一行三个整数n、c以及m。表示文章字数、汉字的种类数、要选择M次。
第二行有n个整数，每个数Ai在[1, c]间，代表一个编码为Ai的汉字。
接下来m行每行两个整数l和r，设上一个询问的答案为ans(第一个询问时ans=0)，令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交换L和R，则本次询问为[L,R]。

Output

输出共m行，每行一个整数，第i个数表示SHY第i次能选出的汉字的最多种类数。

Sample Input

5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5

Sample Output

2
0
0
0
1

HINT

对于100%的数据，1<=n,c,m<=10^5

题解

分块大法好

类似区间众数的做法，预处理F[i][j]表示第i块到第j块的答案

一个询问l-r，那么中间大块x-y的答案已经得到了

只要考虑l-x和y-r对答案的影响，对于这至多2√n个数，对于每个数统计它在x-y出现次数t1，以及l-r出现次数t2，根据t1，t2的奇偶性考虑其对答案的影响

每块大小√（n/logn），复杂度n√n logn

顺便附关于块大小分析

设分块大小为x，分块数n/x，预处理n/x*n

m与n同级，视为n个询问，每次询问二分x次n*x*logn（除非相同的数字很多，否则logn会很小）

n*（x*logn+n/x）
分块大小应该是sqrt(n/logn)

#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];
int lastans;
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()
{
    n=read();c=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    block=sqrt((double)n/log((double)n)*log(2));
    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();
        int x=(l+lastans)%n+1,y=(r+lastans)%n+1;
        if(x>y)swap(x,y);
        lastans=que(x,y);
        printf("%d\n",lastans);
    }
    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

138

139

#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];

int lastans;

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()

{

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

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

block=sqrt((double)n/log((double)n)*log(2));

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();

int x=(l+lastans)%n+1,y=(r+lastans)%n+1;

if(x>y)swap(x,y);

lastans=que(x,y);

printf("%d\n",lastans);

}

return 0;

}

« 「BZOJ2724」[Violet 6] 蒲公英「BZOJ2141」排队 »

cyy489

大神，请问此题中inline有什么作用？

Anonymous

快一点……

神犇，块的大小应该是 sqrt(n / logn) 吧。
请教一下如何分析这个块的最优大小

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

「BZOJ2821」作诗(Poetize)

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论