bitset | OceanEye's Blog

@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;

}

BZOJ4810 莫队+bitset

@OceanEye7年前

04/8

18:51

POJ 2777 线段树+bitset

OceanEye 撰写 bitset POJ 基础题线段树无回复

妈呀这题真卡时。
不得不承认这是我第二道用递归线段树AC的题目qwq太感动了
这题差不多是线段树的裸题了，，只需要bitset维护每一条线段上的颜色还有记得维护PushDown标记就好了。
其他都是细节问题，但是不知道为什么我加了读入优化之后就爆炸WA，，
所以只贴一份AC的无读入优化的代码好了qwq

#include <cstdio>
#include <algorithm>
#include <bitset>
#include <iostream>

using namespace std;

const int NIL = 0;
const int maxn = 100050;
const int Root = 1;

struct node 
{
	bitset <32> rec;
	int l,r;
	bool flag;
}T[8*maxn];

int n,t,o,i,j;
bitset <32> ans;

void build(int l,int r,int k)
{
	T[k].rec.set(1);
	T[k].l = l;T[k].r = r;
	if (l==r) return;
	int mid = (l+r) >> 1;
	build(l,mid,k<<1); build(mid+1,r,k<<1|1);
}

void PushUP(int x)
{
	int lc = x<<1 , rc = x<<1|1; T[x].rec.reset();
	for(int i=1;i<=t;i++) if(T[lc].rec.test(i) || T[rc].rec.test(i)) T[x].rec.set(i); if (T[x].rec.count() == 1) T[x].flag = true; } void insert(int l,int r,int c,int x) { if (T[x].l >= l && T[x].r <= r)
	{ T[x].rec.reset(); T[x].rec.set(c); T[x].flag = true; return; }
	if (T[x].l==T[x].r || T[x].r < l || T[x].l > r) return;
	if(T[x].flag)
	{
		T[x<<1].rec.reset(); T[x<<1|1].rec.reset();
		for(int i=1;i<=t;i++)
			if (T[x].rec.test(i)){ T[x<<1].rec.set(i); T[x<<1|1].rec.set(i); }
		T[x<<1].flag = true;T[x<<1|1].flag = true;
		T[x].flag = false;
	}
	insert(l,r,c,x<<1);
	insert(l,r,c,x<<1|1);
	PushUP(x);
}
void query(int l,int r ,int x)
{
	if(T[x].l > r || T[x].r < l) return; 
	if(T[x].l <= l || T[x].r >= r)if (T[x].flag)
	{
		for(int i=1;i<=t;i++) if (T[x].rec.test(i)) ans.set(i); return; } if (T[x].l >= l && T[x].r <= r)
	{
		for(int i=1;i<=t;i++) if (T[x].rec.test(i)) ans.set(i);
		return;
	}
	if (T[x].l==T[x].r) return;
	query(l,r,x<<1);
	query(l,r,x<<1|1);
}
int main()
{
	std::ios::sync_with_stdio(false); cin >> n >> t >> o;
	build(1,n,Root); 
	for(i=1;i<=o;i++) { char cmd = getchar(); while(cmd == '\n' || cmd == ' ') cmd = getchar(); if (cmd == 'C') { int l,r,c; cin >> l >> r >> c ; if (l > r) swap(l,r);
			insert(l,r,c,Root);
		}
		if (cmd == 'P')
		{
			int l,r;
			cin >> l >> r ; if (l > r) swap(l,r);
			ans.reset();
			query(l,r,Root);
			cout << ans.count() << endl;
		}
	}
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <bitset>

#include <iostream>

using namespace std;

const int NIL = 0;

const int maxn = 100050;

const int Root = 1;

struct node

{

bitset <32> rec;

int l,r;

bool flag;

}T[8*maxn];

int n,t,o,i,j;

bitset <32> ans;

void build(int l,int r,int k)

{

T[k].rec.set(1);

T[k].l = l;T[k].r = r;

if (l==r) return;

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

build(l,mid,k<<1); build(mid+1,r,k<<1|1);

}

void PushUP(int x)

{

int lc = x<<1 , rc = x<<1|1; T[x].rec.reset();

for(int i=1;i<=t;i++) if(T[lc].rec.test(i) || T[rc].rec.test(i)) T[x].rec.set(i); if (T[x].rec.count() == 1) T[x].flag = true; } void insert(int l,int r,int c,int x) { if (T[x].l >= l && T[x].r <= r)

{ T[x].rec.reset(); T[x].rec.set(c); T[x].flag = true; return; }

if (T[x].l==T[x].r || T[x].r < l || T[x].l > r) return;

if(T[x].flag)

{

T[x<<1].rec.reset(); T[x<<1|1].rec.reset();

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

if (T[x].rec.test(i)){ T[x<<1].rec.set(i); T[x<<1|1].rec.set(i); }

T[x<<1].flag = true;T[x<<1|1].flag = true;

T[x].flag = false;

}

insert(l,r,c,x<<1);

insert(l,r,c,x<<1|1);

PushUP(x);

}

void query(int l,int r ,int x)

{

if(T[x].l > r || T[x].r < l) return;

if(T[x].l <= l || T[x].r >= r)if (T[x].flag)

{

for(int i=1;i<=t;i++) if (T[x].rec.test(i)) ans.set(i); return; } if (T[x].l >= l && T[x].r <= r)

{

for(int i=1;i<=t;i++) if (T[x].rec.test(i)) ans.set(i);

return;

}

if (T[x].l==T[x].r) return;

query(l,r,x<<1);

query(l,r,x<<1|1);

}

int main()

{

std::ios::sync_with_stdio(false); cin >> n >> t >> o;

build(1,n,Root);

for(i=1;i<=o;i++) { char cmd = getchar(); while(cmd == '\n' || cmd == ' ') cmd = getchar(); if (cmd == 'C') { int l,r,c; cin >> l >> r >> c ; if (l > r) swap(l,r);

insert(l,r,c,Root);

}

if (cmd == 'P')

{

int l,r;

cin >> l >> r ; if (l > r) swap(l,r);

ans.reset();

query(l,r,Root);

cout << ans.count() << endl;

}

return 0;

}

OceanEye's Blog

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

@OceanEye7年前

BZOJ4810 莫队+bitset

BZOJ4810 莫队+bitset

@OceanEye7年前

POJ 2777 线段树+bitset

POJ 2777 线段树+bitset

友情链接

近期文章

标签