15011418730 LV 7 @ 2025-8-24 22:38:08

自动搬运

来自洛谷，原作者为

	FutaRimeWoawaSete Dear the fking destiny!

搬运于2025-08-24 22:38:08，当前版本为作者最后更新于2023-01-31 19:23:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

sol of P8337

线性空间，线性查询你也卡常是吧？

然后还有更毒瘤的带空间版本，我不懂了。Ynoi 不是为了卡常而卡常。虽然也习惯了，毕竟破防演练。

~~最离谱的是要了三份代码对拍前两份都 UB 了。~~

一年前就实现过了，然后寄了。

我们先考虑转化问题，发现查询的要求子区间 $[x,y]$ 条件等价于 $[x,y]$ 中的数组成集合 $S$ ，满足 $span(S) = S$ 且 $0 \in S$ 。

考虑反证法。假设存在 $span(S) \not = S$ 且任意的 $i \bigoplus j \in S$ 。原问题限制下除非空集则 $S$ 中必然含 $0$ 。若 $span(S) \not = S$ 考虑一个子集 $T$ 的按位异或和 $V$ ，我们可以递归地将其分拆成两个数按位异或的形式，例如 $(x_1,x_2,x_3,x_4)$ ，我们可以递归地将 $x_1 \bigoplus x_2,x_3 \bigoplus x_4$ 这两个数在 $S$ 内，然后就可以推导出来 $x_1 \bigoplus x_2 \bigoplus x_3 \bigoplus x_4$ 在 $S$ 内。

然后就简单了：合法的 $[x,y]$ 满足其中的颜色数为 $2 ^ k$ 。固定右端点 $r$ ，枚举所有合法长度，对于每种长度合法左端点 $l$ 形成了一个区间 $[l_1,l_2]$ ，用一个三元组描述就是 $(l_1,l_2,r)$ ，这样的三元组至多 $O(n \log n)$ 个。

我们采用可扫描线的线性基即可维护固定 $r$ 时长为一定量的线性基范围，注意特判最近的 $0$ 的位置。

然后对于每种长度，随着 $r$ 的递增， $(l_1,l_2)$ 单调不下降，这个可以直接前缀和维护的，我把具体方法写代码里了，自己看吧。

时间复杂度 $O(n \log n)$ ，强制在线空间复杂度 $O(n \log n)$ 。

然后卡常：

基础的卡常，卡卡循环展开，指令集，还有一些 cache；
排线性基的 tim 序时别写 $O(\log n \log \log n)$ 的；
查询时根据区间长从小长度区间问到大长度区间。

实现时我还特判了全 $0$ ，即集合颜色数为 $1$ 的区间这种情况。

其实这道题正常写不卡常的，卡空间倒是，我也卡不过 256MB 和 1.37s。这道题也是卡着跑的，建议不要直接学实现，仅供参考。

/*
设 (l,r,R') 是贡献元组，(L,R) 是查询区间 
r >= L & l < L & R' <= R ;L <= l & r <= R。
维护 r 里面第一个大于等于 L 的区间，维护 l 里面最后一个 < L 的区间，维护 R' <= R 的最后一个区间 
(l,R')
维护 l 里面第一个 >= L 的区间，维护 R' <= R 的最后一个区间 
前缀和内维护的东西
第一类：\sum r；L 维护的系数；+1 的系数
第二类：直接区间和。
*/
const int Len = 6e5 + 5 , M = 1e6 + 5 , LOG = 30 , V = 20;
int lsh[Len],ct,a[Len],n,q,m;vector<int> rk;
inline bool cmp(int x,int y){return x > y;}
struct Linearbasis
{
	int a[LOG + 5],tim[LOG + 5]; 
	Linearbasis(){memset(a , 0 , sizeof a);memset(tim , 0 , sizeof tim);}
	inline void getSt(int x,int y)
	{
		int i = 0 , j = 0 , Sz = (int)rk.size() , tt = 0;
		vector<int> ns;ns.reserve(Sz + (!x));
		while(i < Sz && j < 1)
		{
			if(rk[i] == x && !tt) 
			{
				tt ++;
				i ++;
				continue;
			}
			if(rk[i] > y) ns.push_back(rk[i ++]);
			else ns.push_back(y) , j ++;
		}
		while(i < Sz) 
		{
			if(rk[i] == x && !tt) 
			{
				tt ++;
				i ++;
				continue;
			}
			ns.push_back(rk[i ++]);
		}
		while(j < 1) ns.push_back(y) , j ++;
		swap(ns , rk);
	}
	inline void ins(int x,int tm)
	{
		const int idd = tm;
		for(int i = LOG - 1 ; i >= 0 ; i -= 3)
		{
			if((x >> i) & 1) 
			{
				if(tim[i] < tm) swap(x , a[i]) , swap(tim[i] , tm);
				if(!tm){ct ++;break;}
				x ^= a[i];
			}
			int I = i - 1;
			if(I < 0) break;
			if((x >> I) & 1) 
			{
				if(tim[I] < tm) swap(x , a[I]) , swap(tim[I] , tm);
				if(!tm){ct ++;break;}
				x ^= a[I];
			}
			I = i - 2;
			if(I < 0) break;
			if((x >> I) & 1) 
			{
				if(tim[I] < tm) swap(x , a[I]) , swap(tim[I] , tm);
				if(!tm){ct ++;break;}
				x ^= a[I];
			}
		}
		if(tm != idd) getSt(tm , idd);
	}
}Bs;
int cc[V][Len],nm[V],idx[V];
ll sr[V][Len];
int so[V][Len],sL[V][Len];
int len[V];
ll ss[V][Len];
int sufr[V][Len],prel[V][Len],sufl[V][Len],preR[V][Len],zsm[Len];
int col[V][Len],nmm[V],idxx[V];
inline void get(const int le)
{
	while(nm[le] > (1 << le)) 
	{
		cc[le][a[idx[le]]] --;
		if(!cc[le][a[idx[le] ++]]) nm[le] --;
	}
}
inline void gtt(const int le)
{
	int tt = 0;
	while(nmm[le] >= (1 << le)) 
	{
		tt ++;
		col[le][a[idxx[le]]] --;
		if(!col[le][a[idxx[le] ++]]) nmm[le] --;
	}
	if(tt) nmm[le] ++ , idxx[le] -- , col[le][a[idxx[le]]] ++;
}
inline void add(int le,int x){if(!cc[le][x] ++) nm[le] ++;}
inline void adx(int le,int x){if(!col[le][x] ++) nmm[le] ++;}
int lstl[V],lstr[V],lstR[V],lstid[V];
int cmd[Len];int nmmm;
inline void Work()
{
	int lst0 = -1 , lsto0 = -1;for(int j = 0 ; j < V ; ++ j) idx[j] = idxx[j] = 1 , nm[j] = nmm[j] = 0;
	for(int i = 1 ; i <= n ; ++ i)
	{
		if(!cmd[a[i]] ++) nmmm ++;
		if(!lsh[a[i]]) lst0 = i;
		else lsto0 = i;
		for(int j = 0 ; j < V ; ++ j) 
		{
			add(j , a[i]) , adx(j , a[i]);
			get(j) , gtt(j);
		}
		Bs.ins(lsh[a[i]] , i);
		int l,r,L,R,ul,ur;
		if(lst0 != -1)
		{
			const int LIM = min(V , (int)rk.size());
			for(int j = 1 ; j <= LIM && (1 << j) <= nmmm ; ++ j) 
			{
				if(nm[j] >= (1 << j)) 
				{
					l = idx[j] , r = idxx[j];
					if(j >= (int)rk.size()) L = 1 , R = rk[j - 1];
					else L = rk[j] + 1 , R = rk[j - 1];
					R = min(lst0 , R);if(L > R) continue;
					ul = max(l , L) , ur = min(r , R);if(ul > ur) continue;
					len[j] ++;const int now = len[j];
					sr[j][now] = sr[j][now - 1] , sL[j][now] = sL[j][now - 1] , so[j][now] = so[j][now - 1];
					sr[j][now] += ur , sL[j][now] -- , so[j][now] ++;
					ss[j][now] = ss[j][now - 1] + (ur - ul + 1);
					for(int k = lstr[j] + 1 ; k <= ur ; ++ k) sufr[j][k] = now;
					if(lstl[j] != ul)
					{
						for(int k = lstl[j] + 1 ; k <= ul ; ++ k) prel[j][k] = lstid[j];
					}
					for(int k = lstl[j] + 1 ; k <= ul ; ++ k) sufl[j][k] = len[j];
					for(int k = lstR[j] ; k < i ; ++ k) preR[j][k] = lstid[j];
					lstl[j] = ul , lstr[j] = ur , lstR[j] = i , lstid[j] = len[j];
				} 
			}
		}
		if(!lsh[a[i]]) 
		{
			ul = lsto0 + 1 , ur = i;int j = 0;
			len[j] ++;const int now = len[j];
			sr[j][now] = sr[j][now - 1] , sL[j][now] = sL[j][now - 1] , so[j][now] = so[j][now - 1];
			sr[j][now] += ur , sL[j][now] += -1 , so[j][now] ++;
			ss[j][now] = ss[j][now - 1] + (ur - ul + 1);
			for(int k = lstr[j] + 1 ; k <= ur ; k += 3) 
			{
				sufr[j][k] = now;
				if(k + 1 <= ur) sufr[j][k + 1] = now;
				if(k + 2 <= ur) sufr[j][k + 2] = now;
			}
			if(lstl[j] != ul)
			{
				for(int k = lstl[j] + 1 ; k <= ul ; k += 3) 
				{
					prel[j][k] = lstid[j];
					if(k + 1 <= ul) prel[j][k + 1] = lstid[j];
					if(k + 2 <= ul) prel[j][k + 2] = lstid[j];
				}
			}
			for(int k = lstl[j] + 1 ; k <= ul ; k += 3) 
			{
				sufl[j][k] = len[j];
				if(k + 1 <= ul) sufl[j][k + 1] = len[j];
				if(k + 2 <= ul) sufl[j][k + 2] = len[j];
			}
			for(int k = lstR[j] ; k < i ; k += 3) 
			{
				preR[j][k] = lstid[j];
				if(k + 1 < i) preR[j][k + 1] = lstid[j];
				if(k + 2 < i) preR[j][k + 2] = lstid[j];
			}
			lstl[j] = ul , lstr[j] = ur , lstR[j] = i , lstid[j] = len[j];
		}
		if(i == n) 
		{
			for(int j = min(V , (int)rk.size()) ; j >= 0 ; -- j) 
			{
				if(nm[j] >= (1 << j)) 
				{
					for(int k = lstl[j] + 1 ; k <= n ; ++ k) prel[j][k] = lstid[j];
					for(int k = lstR[j] ; k <= n ; ++ k) preR[j][k] = lstid[j];
				}
			}
		}
	}
}
inline ll Q(int l,int r)
{
	l ++ , r ++;
	ll ret = 0;int L,R;const int LEN = r - l + 1;
	for(int i = 0 ; i < V && (1 << i) <= LEN ; i += 3) 
	{
		L = sufr[i][l] - 1 , R = min(prel[i][l] , preR[i][r]);
		if(~L && R && L < R) ret += (sr[i][R] - sr[i][L]) + (1ll * (sL[i][R] - sL[i][L])) * l + (so[i][R] - so[i][L]);		
		L = sufl[i][l] - 1 , R = preR[i][r];
		if(~L && R && L < R) ret += ss[i][R] - ss[i][L];
		const int I1 = i + 1 , I2 = i + 2;
		if(I1 < V && (1 << (I1)) <= LEN)
		{
			L = sufr[I1][l] - 1 , R = min(prel[I1][l] , preR[I1][r]);	
			if(~L && R && L < R) ret += (sr[I1][R] - sr[I1][L]) + (1ll * (sL[I1][R] - sL[I1][L])) * l + (so[I1][R] - so[I1][L]);		
			L = sufl[I1][l] - 1 , R = preR[I1][r];
			if(~L && R && L < R) ret += ss[I1][R] - ss[I1][L];
		}
		if(I2 < V && (1 << (I2)) <= LEN)
		{
			L = sufr[I2][l] - 1 , R = min(prel[I2][l] , preR[I2][r]);
			if(~L && R && L < R) ret += (sr[I2][R] - sr[I2][L]) + (1ll * (sL[I2][R] - sL[I2][L])) * l + (so[I2][R] - so[I2][L]);		
			L = sufl[I2][l] - 1 , R = preR[I2][r];
			if(~L && R && L < R) ret += ss[I2][R] - ss[I2][L];
		}
	} 
	return ret;
}
int ctt;
inline void init(int N,int Q,vector<int> A)
{
	n = N , m = Q;
	for(int i = 1 ; i <= n ; i ++) lsh[i] = a[i] = A[i - 1];
	sort(lsh + 1 , lsh + 1 + n);
	ctt = unique(lsh + 1 , lsh + 1 + n) - lsh - 1;int l = 1 , r = ctt , as = 0;
	for(int i = 1 ; i <= n ; i ++) 
	{
		l = 1 , r = ctt , as = 0;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(lsh[mid] >= a[i]) as = mid , r = mid - 1;
			else l = mid + 1;
		}
		a[i] = as;
	}
	Work();
}

ID

7658

时间

2000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

线性空间，线性查询你也卡常是吧？

线性空间，线性查询你也卡常是吧？

线性空间，线性查询你也卡常是吧？

[Ynoi2004] rsxc

信息

1 条题解

自动搬运

以下是正文

线性空间，线性查询你也卡常是吧？

线性空间，线性查询你也卡常是吧？

线性空间，线性查询你也卡常是吧？

[Ynoi2004] rsxc

信息

还没有账户？

登录