牛客挑战赛54E题解

首先，考虑给定一个非负整数序列，如何求子集可重异或第k小的值。

考虑建出线性基，从高位到低位依次确定子集可重异或第k小的值。设在线性基里面的元素有s个，外面的元素有t个，我们可以发现，不论这t个元素如何选（2^t种方案），它们通过线性基中元素选与不选异或得到的2^s个方案是完全相同的(是线性基能表示的数的个数）。（如，线性基内元素{1，2}，线性基外元素{1，3}，线性基外元素任何一种选取方案，通过线性基内的不同选取后得到的集合都是{0,1,2,3}）

那么从高到低考虑每一位，设这位以下还有x个位在线性基上有值，我们这一位选1就相当于选择的数排名增大(2^x * 2^t),看当前k与该值的大小是否选，然后往下做即可。

现在的问题是要找到序列最短的区间（将b离散化），满足其中子集可重异或第k小值<=给定值。

显然可以发现左端点从小到大枚举，最小可行右端点单调不降。

此时会有一个问题，右端点增大是插入操作可以实现，但是左端点增大是需要删除。

这里有很多方法，出题人将删除操作转化掉，利用线性基大小只有log，且两个线性基能在log^2内合并的性质，用栈维护，大致做法：

设当前考察区间[l,r],维护一个栈s1,栈中每个元素是一个线性基，分别表示[l, rlas]从右到左依次插入得到的后缀线性基和，即某个线性基表示j~las元素（j属于l~rlas）构成的线性基。再维护[rlas+1,r]的当前线性基bas。查询[l,r]，将s1栈顶线性基与bas线性基合并后查询第k大；修改：

1）r增大，将新增元素插入线性基bas即可

2）l增大，分两种情况，若l <= rlas,则将s1栈顶元素弹出即可,若l > rlas（即s1栈已空），重构整个栈：新开一个空的线性基，从r到l依次插入元素得到后缀线性基和并压入s1栈，接着将bas清空,变量rlas记为r

显然重构总次数为n,重构总复杂度nlogn,而瓶颈在于查询时合并线性基（log^2每次），总复杂度nlog^2

事实上，出题人认为线性基难以删除，但观摩了下kczno1巨佬的代码，发现线性基是有办法删除元素的（删除最早插入元素）

考虑插入一个元素x失败的情况，等价于此时线性基有一个最小子集S, S能通过异或表示出x。注意到线性基中元素线性无关，故S也为线性无关，且因为S是最小能表示出x的子集，S踢掉一个元素后加入x，S能表示的东西是不会变的。而显然我们扔掉最早的元素一定最优，因此对线性基每个元素维护插入时间，插入失败时，找到该元素的表示集S,把S中插入时间最早元素删除换成x，并把时间记为当前即可。

之后删除l位置时，若线性基存在时间等于l的，那么就一定得删掉了。

具体实现时，可以酱紫写：

 void ins(ll x, int y)
    {
        ++tot;
        for(int i = 62; i >= 0; i--)
        {
            if((1LL << i) & x)
            {
                if(!val[i])
                {
                    val[i] = x;
                    tim[i] = y;
                    ++cnt;
                    break;
                }
                if(y > tim[i])
                {
                    swap(tim[i], y);
                    swap(val[i], x);
                }
                x ^= val[i];
            }
        }
    }

相当于当前这位元素处于x的表示集中且早于x，直接把线性基上这位值与x互换并更新时间，继续插入操作，显然能实现踢掉最早的那个的效果。

这个做法的复杂度是nlog,比出题人不知道高到哪里去了（XD）

整道题代码：

//#define LOCAL
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v,x) for(auto v:x)
#define all(x) (x).begin(), (x).end()
#define VI vector<int>
#define VLL vector<ll>
#define pll pair<ll, ll>
#define double long double
//#define int long long
using namespace std;
const int N = 1e6 + 100;
const int inf = 1e9;
//const ll inf = 1e18
const ll mod = 998244353;//1e9 + 7

#ifdef LOCAL
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
	cerr << " " << to_string(H);
	debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


int n, len, num;
pll a[N];
string K;
ll ss;

bool fff = 0;

struct base{
	ll val[63];
	int tim[63];
	int tot, cnt;
	void init()
	{
		memset(val, 0, sizeof val);
		memset(tim, 0, sizeof tim);
		tot = cnt = 0;
	}
	void ins(ll x, int y)
	{
		++tot;
		for(int i = 62; i >= 0; i--)
		{
			if((1LL << i) & x)
			{
				if(!val[i])
				{
					val[i] = x;
					tim[i] = y;
					++cnt;
					break;
				}
				if(y > tim[i])
				{
					swap(tim[i], y);
					swap(val[i], x);
				}
				x ^= val[i];
			}
		}
	}
	void clear(int y)
	{
		--tot;
		for(int i = 62; i >= 0; i--)
		{
			if(tim[i] == y && val[i])
			{
				tim[i] = val[i] = 0;
				--cnt;
			}
		}
	}
	bool chk()
	{
		ll nw = 0, tmp = tot - cnt, cur = cnt;
		if(tot <= len)
			return 0;
		for(int i = 62; i >= 0; i--)
		{
			if(val[i])
			{
				if(K[cur + tmp - 1] == '1')
					nw = max(nw, nw ^ val[i]);
				else
					nw = min(nw, nw ^ val[i]);
				--cur;
			}
		}
		return nw <= ss;
	}
}bas1;



void sol()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i].fi >> a[i].sc;
	}
	sort(a + 1, a + n + 1, [](pll x, pll y)
	{
		return x.sc < y.sc;
	});
	cin >> K;
	len = K.length() - 1;
	reverse(all(K));
	cin >> ss;
	bas1.init();
	ll ans = 1e18;
	for(int lp = 1, rp = 0; lp <= n; lp++)
	{
		if(lp > 1)bas1.clear(lp - 1);
		while(rp < n && !bas1.chk())
		{
			++rp;
			bas1.ins(a[rp].fi, rp);
		}
		if(bas1.chk())
			ans = min(ans, a[rp].sc - a[lp].sc);
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
//	int tt;
//	cin >> tt;
//	while(tt--)
		sol();
}
/*
10
16 272
8 60
1 392
24 352
16 188
1 130
8 161
24 121
24 117
24 156
*/