八月月赛原题——对应

注：学了st表或线段树再做

不要被题面所迷惑！其实很简单的！

观察数据范围，我们可以得到一个很棒的结论: 1e5是个很适合套log的范围，小半个int是个很适合直接套log(撑死算33次)的范围，分析完；

主要两大问题：

（1） 快速计算$g(x)$这个函数的蛋生蛋合并。

（2） 快速求最小值。

先看第一个：我们分函数$f(x)$有四种情况，分别用四个符号表示：

（1） $X$, 对应 $(1,0)$, 即对数二进制取反；

（2） $O$，对应 $(0,1)$, 啥都不做；

（3） $1$ ，对应 $(1,1)$, 二进制全转1；

（4） $0$ ，对应 $(0,0)$, 变 零 ！

我们发现，$X$和$O$具有结合律，$1$和$0$具有覆盖性。 于是乎你可以仿照$LCA$的求法建st表(实质为不带修的线段树，但我懒得敲线段树了——做树剖做出了生理不适)；

第二个，没法直接遍历，但对于仅需考虑的$X$和$O$可以用01trie卡平衡树的思想去构造！维护下上下界即可。

$code:$

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1145; 

char st[N][2][30];//1->0 0->1 3->O 4->X
int n,a,b,p;
char ans[2];
long long anss,l,r,uu,vv;
bool fl,fr,ky,num;

char js(char a,char b)// b 覆盖 a
{
	if(b=='1') return '1';
	else if(b=='0') return '0';
    else if(b=='!')
    {
    	if(a=='1') return '0';
    	else if(a=='0') return '1';
    	else if(a=='!') return 'x';
    	else return '!';
	}
	else return a;
}
	
void get(int u,int v)
{
	ans[0]='x',ans[1]='x';
	int temp=v-u+1,k=0;
	while(temp)
	{
		if(temp&1)
		{
			ans[0]=js(ans[0],st[u][0][k]);
			ans[1]=js(ans[1],st[u][1][k]);
			u+=(1<<k);
		}
		temp>>=1;
		k++;
	}
	return;
}
	
int main()
{
	scanf("%d %d",&n,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&a,&b);
		if(a)
		{
			if(b) st[i][0][0]=st[i][1][0]='1';//1 1
			else  st[i][0][0]='!',st[i][1][0]='x';//1 0
		}
		else
		{
			if(b) st[i][0][0]='x',st[i][1][0]='!';//0 1
			else st[i][0][0]=st[i][1][0]='0';//0 0
		}
	}
	for(int i=1;i<=28;i++)
	    for(int j=1;j<=n;j++)
	        if(j+(1<<i)-1 <=n )
	        {
	        	st[j][0][i]=js( st[j][0][i-1], st[j+(1<<(i-1))][0][i-1] );
				st[j][1][i]=js( st[j][1][i-1], st[j+(1<<(i-1))][1][i-1] );
			}
/*	for(int i=0;i<=4;i++)
	{
		for(int j=1;j<=n;j++)
		    printf("%c ",st[j][0][i]);
		cout<<endl;
	}
	for(int i=0;i<=4;i++)
	{
		for(int j=1;j<=n;j++)
		    printf("%c ",st[j][1][i]);
		cout<<endl;
	}*/
	while(p--)
	{
		anss=0;
		scanf("%lld %lld %lld %lld",&uu,&vv,&l,&r);
		get(uu,vv);
		if(ans[0]=='1'||ans[0]=='0')
		{
			for(int i=29;i>=0;i--)
				if(ans[i&1]=='1') anss+=(1<<i);
		}
		else {
			fl=fr=1;
			for(int i=29;i>=0;i--)
			{
				if(!fl&&!fr) anss+=(1<<i);
				else
				{	
				    num=1;
				    if(ans[i&1]=='!') ky=0;
				    else ky=1;
				    
				    if(fl && ((l>>i)&1) && !ky) num=0,ky=1;
				    else if(fr && !((r>>i)&1) && ky) num=0,ky=0;
				    
				    if(fl && ((l>>i)&1)!=ky) fl=0;
				    else if(fr && ((r>>i)&1)!=ky) fr=0;
				    
				    if(num) anss+=(1<<i);
				}
				
			}
		}
	//	cout<<ans[0]<<" "<<ans[1]<<endl;
		printf("%lld\n",anss);
	}
	return 0;
}

ps:这题当时补提时由我首A，劳魏第二……但他退役了，谨以此题解纪念他。

pps:你们学到并查集和区间dp了？我得督促一下八年级的了。

ppps:电脑有大病，每次都显示凌晨发布，这又不是小说！