「NOI2017」整数

有一些比较简单的\(\log^2n\)做法

比如暴力在动态开点线段树上维护每个位置为\(0\)还是\(1\)，我们发现涉及到某一位加上\(1\)或者减去\(1\)实际上对其他位的影响只有区间覆盖，通过线段树上二分可以得到区间覆盖的位置，然后暴力区间覆盖即可。

反正我这种菜鸡大常数写法只得到了68分..

考虑利用势能，注意到如果同时改变加法和减法，势能很容易被\(b\)搞掉

如果分开维护加法和减法，把位置上的\(1\)的个数当做势能，可以发现，暴力修改是均摊\(O(n\log a)\)的

直接暴力维护两个数组\(plu\)和\(dec\)

考虑单点求值，因为保证了\(x\ge 0\)

所以我们发现只需要两个条件就可以确定第\(k\)位的值，即

\(ans_1=[plu_k=dec_k]\)
\(ans_2=[plu[k-1,1]\ge[dec[k-1,1]]]\)，这里是倒着进行字符串比较的意思

第\(k\)位的答案即为\(ans_1 \ xor \ ans_2\)，这里讨论一下就可以得到了

考虑找到\(\le p\)位置的两个数组第一个不同的位置，然后比较大小

一个暴力的想法是，把每个不同的位置塞到set里面去，然后每次在set里面二分找一下位置，也是\(\log^2n\)的

考虑到每次修改的一个长为\(\log a\)连续的区间(这里实际上饶了一个大圈子)

所以把区间每\(\log a\)分一块，块也是有势能的，然后set里面一次赛一个块就可以了

复杂度就一个\(\log\)了

Code:

#include <cstdio>

#include <cctype>

#include <set>

#include <algorithm>

#define ll long long

using std::min;

const int SIZE=1<<21;

char ibuf[SIZE],*iS,*iT;

//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)

#define gc() getchar()

template <class T>

void read(T &x)

{

	int f=0;x=0;char c=gc();

	while(!isdigit(c)) f|=c=='-',c=gc();

	while(isdigit(c)) x=x*10+c-'0',c=gc();

	if(f) x=-x;

}

const int N=1e6+10;

int n,t1,t2,t3;

int plu[N*30],dec[N*30],bel[N*30];

int edt[N],vis[N];

std::set <int> s;

std::set <int>::iterator it;

int qry(int p)

{

    while(p%32!=0&&plu[p]==dec[p]) --p;

    if(plu[p]!=dec[p])

    {

        if(plu[p]>dec[p]) return 1;

        else return 0;

    }

    p=bel[p];

    it=s.upper_bound(p);

    if(s.empty()||it==s.begin()) return 1;

    --it;

    p=(*it)*32;

    while(plu[p]==dec[p]) --p;

    if(plu[p]>dec[p]) return 1;

    else return 0;

}

int main()

{

	read(n),read(t1),read(t2),read(t3);

	int m=n*30+31,T=(m-1)/32+1;

	for(int L,R=0,i=1;i<=T;i++)

	{

		L=R+1,R=i*32;

		for(int j=L;j<=R;j++) bel[j]=i;

	}

	for(int op,a,b,k,i=1;i<=n;i++)

	{

		read(op);

		if(op==1)

		{

			edt[0]=0;

			read(a),read(b);

			if(a>0)

			{

				for(int p,j=1;j<=30;j++)

					if(a>>j-1&1)

					{

						p=j+b;

						if(vis[bel[p]]!=i)

							edt[++edt[0]]=bel[p],vis[bel[p]]=i;

						while(plu[p])

						{

							plu[p++]=0;

							if(vis[bel[p]]!=i)

								edt[++edt[0]]=bel[p],vis[bel[p]]=i;

						}

						plu[p]=1;

					}

			}

			else

			{

				a=-a;

				for(int p,j=1;j<=30;j++)

					if(a>>j-1&1)

					{

						p=j+b;

						if(vis[bel[p]]!=i)

							edt[++edt[0]]=bel[p],vis[bel[p]]=i;

						while(dec[p])

						{

							dec[p++]=0;

							if(vis[dec[p]]!=i)

								edt[++edt[0]]=bel[p],vis[bel[p]]=i;

						}

						dec[p]=1;

					}

			}

			for(int j=1;j<=edt[0];j++)

			{

				int L=(edt[j]-1)*32+1,R=edt[j]*32,flag=1;

				for(int l=L;l<=R;l++)

					if(plu[l]!=dec[l])

					{

						flag=0;

						break;

					}

				if(flag)

				{

					if(s.find(edt[j])!=s.end()) s.erase(edt[j]);

				}

				else

					s.insert(edt[j]);

			}

		}

		else

		{

			read(k);

			int p=k++;

			int ans=0;

			if(plu[k]==dec[k]) ans=1;

			printf("%d\n",ans^qry(p));

		}

	}

	return 0;

}

2019.5.31

巴特西

「NOI2017」整数解题报告

「NOI2017」整数

最新文章

热门文章

巴特西

「NOI2017」整数 解题报告

「NOI2017」整数

最新文章

热门文章

「NOI2017」整数解题报告