bzoj 4942: [Noi2017]整数

Description

Solution

加法减法可以分开考虑,如果只有加法的话,直接暴力进位复杂度是对的

询问的时候就是把两个二进制数做差,判断第 \(k\) 位的取值

实际上我们只需要判断 \(1\) 到 \(k-1\) 位是否需要借位就知道了做差后的值

那么就需要判断两个二进制数的某个后缀的大小,我们二分出第一个不相同的位置,然后判断一下这一位的大小关系即可

可以用 \(zkw\) 线段树维护一下第一个不同的位置,类似于线段树上二分

#include<bits/stdc++.h>

using namespace std;

template<class T>void gi(T &x){

	int f;char c;

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

	for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;

}

const int N=35000050,inf=1e9,M=1<<25;

int n,op,x,y,T;char s1[N],s2[N],d[N*2];

inline void add(){

	gi(x);gi(y);

	int l=inf,r=0;

	char *a=(x>0?s1:s2);x=abs(x);

	for(int i=0;i<=30;i++){

		if(x>>i&1){

			int t=y+i;

			while(++a[t]>=2)a[t++]=0;

			l=min(l,y+i);r=max(r,t);

		}

	}

	for(int i=l;i<=r;i++)d[i+M]=s1[i]^s2[i];

	for(l=(l+M)>>1,r=(r+M)>>1;l;l>>=1,r>>=1)

		for(int i=l;i<=r;i++)d[i]=d[i<<1]|d[i<<1|1];

}

inline int query(int x){

	for(int i=x+M;i;i>>=1){

		if(i&1&d[i^1]){

			for(i^=1;i<M;(i<<=1)|=d[i|1]);

			return i-M;

		}

	}

	return -1;

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  gi(n);gi(T);gi(T);gi(T);

  while(n--){

	  gi(op);

	  if(op==1)add();

	  else{

		  gi(x);y=query(x);

		  if(y==-1 || s1[y]>=s2[y])printf("%d\n",s1[x]^s2[x]);

		  else printf("%d\n",s1[x]==s2[x]);

	  }

  }

  return 0;

}

巴特西

bzoj 4942: [Noi2017]整数

Description

Solution

最新文章

热门文章