NOI2017 整数

题意：

让你实现两个操作：

1 $a$ $b$：将$x$加上整数$a \cdot 2 ^ b$，其中 $a$为一个整数，$b$为一个非负整数
2 $k$：询问 $x$在用二进制表示时，位权为$2 ^ k$的位的值（即这一位上的$1$代表$2 ^ k$）

一百万次操作，$ |a| \leq 10^9,b,k\leq30n$。

题解：

线段树+压位，30位一位，没了

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define fo(i,l,r) for(int i=l;i<=r;i++)

#define of(i,l,r) for(int i=l;i>=r;i--)

#define fe(i,u) for(int i=head[u];i;i=e[i].next)

using namespace std;

typedef long long ll;

inline void open(const char *s)

{

	#ifndef ONLINE_JUDGE

	char str[20];

	sprintf(str,"in%s.txt",s);

	freopen(str,"r",stdin);

//	sprintf(str,"out%s.txt",s);

//	freopen(str,"w",stdout);

	#endif

}

inline int rd()

{

	static int x,f;

	x=0;f=1;

	char ch=getchar();

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

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

	return f>0?x:-x;

}

const int N=1000010,n=N-2,B=30,S=(1<<B)-1;

int m,rt;

namespace Seg{

#define lson tr[o].ls,l,mid

#define rson tr[o].rs,mid+1,r

#define qlson lson,L,min(mid,R)

#define qrson rson,max(mid+1,L),R

struct tree{

	int ls,rs,val0,val1,tag;//1 or 0 and

	tree(){ls=rs=val0=val1=0;tag=-1;}

}tr[N<<1];int cnt=0;

void build(int &o,int l,int r)

{

	o=++cnt;

	if(l==r)return;

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

	build(lson);

	build(rson);

}

inline void pushup(int o)

{

	tr[o].val1=tr[tr[o].ls].val1|tr[tr[o].rs].val1;

	tr[o].val0=tr[tr[o].ls].val0&tr[tr[o].rs].val0;

}

inline void pushdown(int o)

{

	if(!~tr[o].tag)return;

	int ls=tr[o].ls,rs=tr[o].rs;

	tr[ls].val0=tr[ls].val1=tr[ls].tag=tr[o].tag;

	tr[rs].val0=tr[rs].val1=tr[rs].tag=tr[o].tag;

	tr[o].tag=-1;

}

int find1(int o,int l,int r,int x)

{

	if(tr[o].val0==S)return -1;

	if(l==r)return l;

	pushdown(o);

	int mid=(l+r)>>1,res=-1;

	if(x<=mid)res=find1(lson,x);

	if(~res)return res;

	return find1(rson,x);

}

int find0(int o,int l,int r,int x)

{

	if(!tr[o].val1)return -1;

	if(l==r)return l;

	pushdown(o);

	int mid=(l+r)>>1,res=-1;

	if(x<=mid)res=find0(lson,x);

	if(~res)return res;

	return find0(rson,x);

}

void updata(int o,int l,int r,int x,int d)

{

	if(l==r)return tr[o].val0+=d,tr[o].val1+=d,void();

	pushdown(o);

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

	if(x<=mid)updata(lson,x,d);

	else updata(rson,x,d);

	pushup(o);

}

void paint(int o,int l,int r,int L,int R,int d)

{

	if(l==L&&r==R)return tr[o].tag=tr[o].val0=tr[o].val1=d,void();

	pushdown(o);

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

	if(L<=mid)paint(qlson,d);

	if(R>mid)paint(qrson,d);

	pushup(o);

}

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

{

	if(l==r)return tr[o].val0;

	pushdown(o);

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

	if(x<=mid)return query(lson,x);

	return query(rson,x);

}

}

inline void inc(int p,int x)

{

	static int res,y;

//	printf("%d %d\n",p,x);

	res=Seg::query(rt,0,n,p);

	if(res+x<=S)return Seg::updata(rt,0,n,p,x);

	Seg::updata(rt,0,n,p,x-S-1);

	y=Seg::find1(rt,0,n,p+1);

//	printf("%d\n",y);

	if(y>p+1)Seg::paint(rt,0,n,p+1,y-1,0);

	Seg::updata(rt,0,n,y,1);

}

inline void dec(int p,int x)

{

	static int res,y;

//	printf("%d %d\n",p,x);

	res=Seg::query(rt,0,n,p);

	if(res-x>=0)return Seg::updata(rt,0,n,p,-x);

	Seg::updata(rt,0,n,p,S-x+1);

	y=Seg::find0(rt,0,n,p+1);

//	printf("%d\n",y);

	if(y>p+1)Seg::paint(rt,0,n,p+1,y-1,S);

	Seg::updata(rt,0,n,y,-1);

}

inline void gao1()

{

	static int x,y,p;

	x=rd();y=rd();p=y/B;

	if(x>0){

		inc(p,(x<<(y-p*B))&S);

		inc(p+1,x>>(B-y+p*B));

	}

	else{

		x=-x;

		dec(p,(x<<(y-p*B))&S);

		dec(p+1,x>>(B-y+p*B));

	}

}

inline void gao2()

{

	static int x,p,res;

	x=rd();p=x/B;

	res=Seg::query(rt,0,n,p);

	if(res&(1<<(x-p*B)))puts("1");

	else puts("0");

}

int main()

{

	m=rd();rd();rd();rd();

	Seg::build(rt,0,n);

	while(m--){

		int ty=rd();

		if(ty==1)gao1();

		else gao2();

	}

	return 0;

}

巴特西

NOI2017整数

NOI2017 整数

题意：

题解：

最新文章

热门文章