莫队 | OceanEye's Blog

@OceanEye7年前

05/2

20:40

BZOJ3236

OceanEye 撰写树状数组莫队无回复

看着这道题觉得很神啊

于是写了个n根号nlogn的就开始跑了

然后就跑过去了……

95s的AC

不过写这份代码好像只花了我十分钟？说明我码力还算不错么qwq[单身狗的怨念]

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;
#define N 100010
#define lb(x) (x&-x)
int Arr[N];
void add(int x,int v)
{
	while(x<=N) { Arr[x]+=v; x+=lb(x); }
}
int query(int pos)
{
	int ret=0;
	while(pos) { ret+=Arr[pos]; pos-=lb(pos); }
	return ret;
}
int Arr2[N];
void ins(int x,int v)
{ while(x<=N) { Arr2[x]+=v; x+=lb(x); } }
int _query(int pos)
{
	int ret=0;
	while(pos) { ret+=Arr2[pos]; pos-=lb(pos); }
	return ret;
}

struct rec
{
	int l,r,id;
	int a,b;
}Q[N*10];

#define SIZ 400
int a[N],n,m,cnt[N];
int l[SIZ],r[SIZ],belong[N],SQR,CNT;
int ans1[N*10],ans2[N*10];

bool comp(const rec &x,const rec &y)
{
	if(belong[x.l]==belong[y.l]) return x.r<y.r;
	return x.l<y.l;
}

void pre()
{
	read(n); read(m);
	SQR=sqrt(n); CNT=(n-1)/SQR+1;
	for(int i=1;i<=CNT;++i) { l[i]=(i-1)*SQR+1; r[i]=i*SQR; }
	r[CNT]=n;
	for(int i=1;i<=CNT;++i)
		for(int j=l[i];j<=r[i];++j) belong[j]=i;
	for(int i=1;i<=n;++i) read(a[i]);
	for(int i=1;i<=m;++i)
	{ read(Q[i].l); read(Q[i].r); read(Q[i].a); read(Q[i].b); Q[i].id=i; }
	sort(Q+1,Q+m+1,comp);
}

int main()
{
	pre();
	int nodeL=1,nodeR=0;
	for(int i=1;i<=m;++i)
	{
		while(nodeL>Q[i].l)
		{
			nodeL--;
			add(a[nodeL],1);
			if(!cnt[a[nodeL]]) ins(a[nodeL],1);
			cnt[a[nodeL]]++;
		}
		while(nodeR<Q[i].r)
		{
			nodeR++;
			add(a[nodeR],1);
			if(!cnt[a[nodeR]]) ins(a[nodeR],1);
			cnt[a[nodeR]]++;
		}
		while(nodeL<Q[i].l)
		{
			add(a[nodeL],-1);
			cnt[a[nodeL]]--;
			if(!cnt[a[nodeL]]) ins(a[nodeL],-1);
			nodeL++;
		}
		while(nodeR>Q[i].r)
		{
			add(a[nodeR],-1);
			cnt[a[nodeR]]--;
			if(!cnt[a[nodeR]]) ins(a[nodeR],-1);
			nodeR--;
		}
		ans1[Q[i].id]=query(Q[i].b)-query(Q[i].a-1);
		ans2[Q[i].id]=_query(Q[i].b)-_query(Q[i].a-1);
	}
	for(int i=1;i<=m;i++) printf("%d %d\n",ans1[i],ans2[i]);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <cmath>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

#define lb(x) (x&-x)

int Arr[N];

void add(int x,int v)

{

while(x<=N) { Arr[x]+=v; x+=lb(x); }

}

int query(int pos)

{

int ret=0;

while(pos) { ret+=Arr[pos]; pos-=lb(pos); }

return ret;

}

int Arr2[N];

void ins(int x,int v)

{ while(x<=N) { Arr2[x]+=v; x+=lb(x); } }

int _query(int pos)

{

int ret=0;

while(pos) { ret+=Arr2[pos]; pos-=lb(pos); }

return ret;

}

struct rec

{

int l,r,id;

int a,b;

}Q[N*10];

#define SIZ 400

int a[N],n,m,cnt[N];

int l[SIZ],r[SIZ],belong[N],SQR,CNT;

int ans1[N*10],ans2[N*10];

bool comp(const rec &x,const rec &y)

{

if(belong[x.l]==belong[y.l]) return x.r<y.r;

return x.l<y.l;

}

void pre()

{

read(n); read(m);

SQR=sqrt(n); CNT=(n-1)/SQR+1;

for(int i=1;i<=CNT;++i) { l[i]=(i-1)*SQR+1; r[i]=i*SQR; }

r[CNT]=n;

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

for(int j=l[i];j<=r[i];++j) belong[j]=i;

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

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

{ read(Q[i].l); read(Q[i].r); read(Q[i].a); read(Q[i].b); Q[i].id=i; }

sort(Q+1,Q+m+1,comp);

}

int main()

{

pre();

int nodeL=1,nodeR=0;

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

{

while(nodeL>Q[i].l)

{

nodeL--;

add(a[nodeL],1);

if(!cnt[a[nodeL]]) ins(a[nodeL],1);

cnt[a[nodeL]]++;

}

while(nodeR<Q[i].r)

{

nodeR++;

add(a[nodeR],1);

if(!cnt[a[nodeR]]) ins(a[nodeR],1);

cnt[a[nodeR]]++;

}

while(nodeL<Q[i].l)

{

add(a[nodeL],-1);

cnt[a[nodeL]]--;

if(!cnt[a[nodeL]]) ins(a[nodeL],-1);

nodeL++;

}

while(nodeR>Q[i].r)

{

add(a[nodeR],-1);

cnt[a[nodeR]]--;

if(!cnt[a[nodeR]]) ins(a[nodeR],-1);

nodeR--;

}

ans1[Q[i].id]=query(Q[i].b)-query(Q[i].a-1);

ans2[Q[i].id]=_query(Q[i].b)-_query(Q[i].a-1);

}

for(int i=1;i<=m;i++) printf("%d %d\n",ans1[i],ans2[i]);

return 0;

}

BZOJ3236

@OceanEye7年前

04/27

09:59

BZOJ4810 莫队+bitset

OceanEye 撰写 bitset 神技巧莫队无回复

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4810

kry大爷的代码好短……可以看看orz

[bzoj 4810] [Ynoi2017]由乃的玉米田

这题目测只要是根号+压位就能过得去的了……所以不要太在意细节
[然后就被细节骗走了五次wa]
如果我们压了位……
减法就可以直接右移解决 b-c=a
加法的话把它反过来右移解决大概是变成 a+b=c -> b-c=-a

乘法很simple，直接暴力就好了，根号可是比n/64要小的
而且时限30s，跑起来好像还挺稳的？
代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;
#define N 100010
#define SIZ 400
bitset <N> Appear,Rev,____;

int a[N],cnt[N],n,m;
int l[SIZ],r[SIZ],belong[N],SQR,CNT;

struct rec
{
	int l,r,c,type;
	int id;
}pool[N];

bool comp(const rec &x,const rec&y )
{
	if(belong[x.l]==belong[y.l]) return x.r<y.r;
	return x.l<y.l;
}

void pre()
{
	read(n); read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	SQR=sqrt(n); CNT=(n-1)/SQR+1;
	for(int i=1;i<=CNT;i++)
	{ l[i]=(CNT-1)*SQR+1; r[i]=CNT*SQR; }
	r[CNT]=n;
	for(int i=1;i<=n;i++) belong[i]=(i-1)/SQR+1;
	for(int i=1;i<=m;i++) { read(pool[i].type); read(pool[i].l); read(pool[i].r); read(pool[i].c); pool[i].id=i; }
	sort(pool+1,pool+1+m,comp);
}

int ans[N];

void solve(int i)
{
	if(pool[i].type==1)
	{
		____=Appear;
		____>>=pool[i].c;
		____&=Appear;
		if(____.any()) ans[pool[i].id]=1;
		else ans[pool[i].id]=0;
		return;
	}
	if(pool[i].type==2)
	{
		____=Rev;
		____>>=(100000-pool[i].c);
		____&=Appear;
		if(____.any()) ans[pool[i].id]=1;
		else ans[pool[i].id]=0;
		return;
	}
	if(pool[i].type==3)
	{
		for(int j=1;j*j<=pool[i].c;j++) if(cnt[j]&&cnt[pool[i].c/j])
		{
			if(pool[i].c%j==0)
			{
				ans[pool[i].id]=1;
				return;
			}
		}
		ans[pool[i].id]=0;
		return;
	}
}

int main()
{
	pre();
	int nodeR,nodeL;
	nodeR=0;nodeL=1;
	for(int i=1;i<=m;i++)
	{
		while(nodeR<pool[i].r)
		{
			nodeR++;
			cnt[a[nodeR]]++;
			if(cnt[a[nodeR]]==1) Appear[a[nodeR]]=1,Rev[100000-a[nodeR]]=1;
		}
		while(nodeL>pool[i].l)
		{
			nodeL--;
			cnt[a[nodeL]]++;
			if(cnt[a[nodeL]]==1) Appear[a[nodeL]]=1,Rev[100000-a[nodeL]]=1;
		}
		while(nodeL<pool[i].l)
		{
			cnt[a[nodeL]]--;
			if(!cnt[a[nodeL]]) Appear[a[nodeL]]=0,Rev[100000-a[nodeL]]=0;
			nodeL++;
		}
		while(nodeR>pool[i].r)
		{
			cnt[a[nodeR]]--;
			if(!cnt[a[nodeR]]) Appear[a[nodeR]]=0,Rev[100000-a[nodeR]]=0;
			nodeR--;
		}
		solve(i);
	}
	for(int i=1;i<=m;i++) ans[i]?puts("yuno"):puts("yumi");
	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

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <iostream>

#include <bitset>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

#define SIZ 400

bitset <N> Appear,Rev,____;

int a[N],cnt[N],n,m;

int l[SIZ],r[SIZ],belong[N],SQR,CNT;

struct rec

{

int l,r,c,type;

int id;

}pool[N];

bool comp(const rec &x,const rec&y )

{

if(belong[x.l]==belong[y.l]) return x.r<y.r;

return x.l<y.l;

}

void pre()

{

read(n); read(m);

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

SQR=sqrt(n); CNT=(n-1)/SQR+1;

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

{ l[i]=(CNT-1)*SQR+1; r[i]=CNT*SQR; }

r[CNT]=n;

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

for(int i=1;i<=m;i++) { read(pool[i].type); read(pool[i].l); read(pool[i].r); read(pool[i].c); pool[i].id=i; }

sort(pool+1,pool+1+m,comp);

}

int ans[N];

void solve(int i)

{

if(pool[i].type==1)

{

____=Appear;

____>>=pool[i].c;

____&=Appear;

if(____.any()) ans[pool[i].id]=1;

else ans[pool[i].id]=0;

return;

}

if(pool[i].type==2)

{

____=Rev;

____>>=(100000-pool[i].c);

____&=Appear;

if(____.any()) ans[pool[i].id]=1;

else ans[pool[i].id]=0;

return;

}

if(pool[i].type==3)

{

for(int j=1;j*j<=pool[i].c;j++) if(cnt[j]&&cnt[pool[i].c/j])

{

if(pool[i].c%j==0)

{

ans[pool[i].id]=1;

return;

}

ans[pool[i].id]=0;

return;

}

int main()

{

pre();

int nodeR,nodeL;

nodeR=0;nodeL=1;

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

{

while(nodeR<pool[i].r)

{

nodeR++;

cnt[a[nodeR]]++;

if(cnt[a[nodeR]]==1) Appear[a[nodeR]]=1,Rev[100000-a[nodeR]]=1;

}

while(nodeL>pool[i].l)

{

nodeL--;

cnt[a[nodeL]]++;

if(cnt[a[nodeL]]==1) Appear[a[nodeL]]=1,Rev[100000-a[nodeL]]=1;

}

while(nodeL<pool[i].l)

{

cnt[a[nodeL]]--;

if(!cnt[a[nodeL]]) Appear[a[nodeL]]=0,Rev[100000-a[nodeL]]=0;

nodeL++;

}

while(nodeR>pool[i].r)

{

cnt[a[nodeR]]--;

if(!cnt[a[nodeR]]) Appear[a[nodeR]]=0,Rev[100000-a[nodeR]]=0;

nodeR--;

}

solve(i);

}

for(int i=1;i<=m;i++) ans[i]?puts("yuno"):puts("yumi");

return 0;

}

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

BZOJ3236

BZOJ3236

@OceanEye7年前

BZOJ4810 莫队+bitset

BZOJ4810 莫队+bitset

友情链接

近期文章

标签