【BZOJ4942】[Noi2017]整数

题目描述去uoj

题解：如果只有加法，那么直接暴力即可。。。（因为1的数量最多nlogn个）

先考虑加法，比较显然的做法就是将A二进制分解成log位，然后依次更新这log位，如果最高位依然有进位，那么找到最高位后面的第一个0，将中间的所有1变成0，那个0变成1。这个显然要用到线段树，但是复杂度是nlog2n的，肯定过不去。

于是我在考场上yy了一下，这log位是连续的，我们每次都要花费log的时间去修改一个岂不是很浪费？我们可以先在线段树上找到这段区间，然后在线段树上dfs下去，这样，时间复杂度就变成O(logn+那段区间在线段树上的大小)。因为一颗正常的线段树的大小就是4*n的，而这里的那段区间的大小是log的，所以我猜测复杂度应该是log*常数的。但是不会证，考完试旁边的大佬都十分怀疑我的复杂度，搞得我也非常怀疑，但是。。但是AC了。

正解貌似是O(nlog2n/32)的线段树+压位？听说考场上这么写的全被卡常了，体会到了wys的险恶用心~

回来重码了一发，交到uoj上TLE了，交到BZ上AC了（因为是均摊复杂度嘛~）。

欢迎大佬告诉我这个算法的真正复杂度~

#include <cstdio>

#include <cstring>

#include <iostream>

#define lson x<<1

#define rson x<<1|1

using namespace std;

const int N=30000040;

int n,A,B,nxt,f,len;

int s[N+1<<2],p[50];

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

{

	if(!s[x])	s[lson]=s[rson]=0;

	if(s[x]==r-l+1)

	{

		int mid=l+r>>1;

		s[lson]=mid-l+1,s[rson]=r-mid;

	}

}

void pushup(int x)

{

	s[x]=s[lson]+s[rson];

}

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

{

	if(l==r)

	{

		s[x]+=p[l-B];

		while(s[x]>1)	p[l-B+1]++,s[x]-=2;

		while(s[x]<0)	p[l-B+1]--,s[x]+=2;

		return ;

	}

	pushdown(l,r,x);

	int mid=l+r>>1;

	dfs(l,mid,lson),dfs(mid+1,r,rson);

	pushup(x);

}

void updata(int l,int r,int x,int a,int b)

{

	if(a<=l&&r<=b)

	{

		dfs(l,r,x);

		return ;

	}

	pushdown(l,r,x);

	int mid=l+r>>1;

	if(a<=mid)	updata(l,mid,lson,a,b);

	if(b>mid)	updata(mid+1,r,rson,a,b);

	pushup(x);

}

void modify(int l,int r,int x,int a,int b,int c)

{

	if(a>b)	return ;

	if(a<=l&&r<=b)

	{

		s[x]=(r-l+1)*c;

		return ;

	}

	pushdown(l,r,x);

	int mid=l+r>>1;

	if(a<=mid)	modify(l,mid,lson,a,b,c);

	if(b>mid)	modify(mid+1,r,rson,a,b,c);

	pushup(x);

}

void nxt0(int l,int r,int x,int a)

{

	if(r<a||nxt<=l||s[x]==r-l+1)	return ;

	if(l==r)

	{

		nxt=l;

		return ;

	}

	int mid=l+r>>1;

	pushdown(l,r,x);

	nxt0(l,mid,lson,a),nxt0(mid+1,r,rson,a);

}

void nxt1(int l,int r,int x,int a)

{

	if(r<a||nxt<=l||!s[x])	return ;

	if(l==r)

	{

		nxt=l;

		return ;

	}

	int mid=l+r>>1;

	pushdown(l,r,x);

	nxt1(l,mid,lson,a),nxt1(mid+1,r,rson,a);

}

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

{

	if(l==r)	return s[x];

	pushdown(l,r,x);

	int mid=l+r>>1;

	if(a<=mid)	return query(l,mid,lson,a);

	return query(mid+1,r,rson,a);

}

int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd(),rd(),rd(),rd();

	int i;

	for(i=1;i<=n;i++)

	{

		if(rd()==1)

		{

			A=rd(),B=rd(),f=1,len=0;

			if(!A)	continue;

			if(A<0)	f=-1,A=-A;

			while(A)	p[len++]=(A&1)*f,A>>=1;

			p[len++]=0,p[len]=0,updata(0,N,1,B,B+len-1);

			if(p[len]>0)

			{

				nxt=1<<30,nxt0(0,N,1,B+len);

				modify(0,N,1,B+len,nxt-1,0),modify(0,N,1,nxt,nxt,1);

			}

			if(p[len]<0)

			{

				nxt=1<<30,nxt1(0,N,1,B+len);

				modify(0,N,1,B+len,nxt-1,1),modify(0,N,1,nxt,nxt,0);

			}

		}

		else	A=rd(),printf("%d\n",query(0,N,1,A));

	}

	return 0;

}

//10 3 1 2 1 100 0 1 2333 0 1 -233 0 2 5 2 7 2 15 1 5 15 2 15 1 -1 12 2 15

巴特西

【BZOJ4942】[Noi2017]整数线段树+DFS（卡过）

【BZOJ4942】[Noi2017]整数

最新文章

热门文章

巴特西

【BZOJ4942】[Noi2017]整数 线段树+DFS（卡过）

【BZOJ4942】[Noi2017]整数

最新文章

热门文章

【BZOJ4942】[Noi2017]整数线段树+DFS（卡过）