Codeforces Round #757 (Div. 2)

C. Divan and bitwise operations

一天，Divan 研究了一个由 \(n\) 个非负整数构成的序列，\(a_1,a_2,...a_n\) 他选出了这个序列 \(a\) 的所有非空子序列，计算出所有子序列的异或 xor 值，然后把这些子序列的异或值加起来，得到了这个序列的 conziness 值。

\[conziness =\sum(\sum _1 ^{size} a_{k_1} \oplus a_{k_2}...\oplus a_{k_{size}}), size\leq n \]

一个子序列的定义是从原序列中任意删除几个数(零，一，…，所有)，剩下的元素按照原来的顺序写在一起，得到一个新的序列，即原序列的子序列。

Divan 对他的研究感到非常骄傲，但是他现在不小心把序列 \(a\) 给弄丢了，当然 conziness 值也弄丢了！但是，Divan 知道 \(m\) 个子串的同或 or值，并且，原序列的每个元素都至少在这 \(m\) 个子串中出现过一次。

Divan 想让你帮忙找出 \(a\) 序列的 conziness 值，保证存在至少一种方案，如果有多种可能，任意输出一种即可。

由于答案可能特别大，请将最后的答案对 \(10^9 + 7\) 取模。

多测，有 \(t\) 组数据 .

\(1\leq t\leq 10^3,1\leq n,m\leq 2\cdot 10^5,1\leq l\leq r\leq n,0\leq x<2^{30}-1,\sum n\leq 2\cdot 10^5,\sum m\leq 2\cdot 10^5\)

sol1

发现要根据or的值重新构建 \(a\) .

分析 or 的性质，发现，or 中为 \(1\) 的一位中至少有一个 \(1\) ，为 \(0\) 中不能有 \(1\) .

因为保证了存在答案，所以，考虑按区间大小从小往大填，把区间从 \(l\) 到 \(r\) 中没有赋值的都赋值成 \(x\) . 这样一定是有解的，但是这个方法不是很好实现，鉴于是才是 div2 的 c ，考虑一些更好写的方法 .

考虑将区间 \([l,r]\) 按照 \(r\) 从小到大，\(l\) 从大到小的顺序排序 . 考虑枚举位数，从 \(1\) 到 \(n\) . 用一个 set 维护包含 \(l\) 的限制条件，其中 \((r,x)\) 从小到大排序，考虑，对于当前 \(i\) ，首先要弹出 \(s\) 中 \(r 的元素，然后找到 \(s\) 中第一个元素，令 \(a_i=x\) . 否则，令 \(a_i=0\) . 然后在 \(s\) 插入 \(l=i\) 的 \((r,x)\) .

因此，就可以得到一个合法的 \(a_i\) .

接下来，用 \(cnt(i,k,0/1)\) 表示，到了第 \(i\) 位，二进制第 \(k\) 位为 \(0/1\) 的序列的个数 . 稍微 \(dp\) 一下即可 .

时间复杂度 : \(O(n\log v+m\log m)\)

空间复杂度 : \(O(n\log v)\)

#include
using namespace std;
const int mod=1e9+7;
int t;
int n,m;
vector >v[200010];
int b[200010];
set >s;
int cnt[200010][32][2];
inline void upd(int&x,int y){x=(x+y)%mod;}
void solve(){
	cin>>n>>m;
	for(int i=0;i>l>>r>>x;
		l--;r--;
		v[l].push_back(make_pair(r,x));
	}
	for(int i=0;ifirstsecond;
		else b[i]=0;
	}
	for(int i=0;i<=n;i++)memset(cnt[i],0,sizeof(cnt[i]));
	for(int i=0;i>t;
	while(t--){
		solve();
	}
	return 0;
}
/*inline? ll or int? size? min max?*/

sol2

考虑求出了 \(b_i\) 数组，其中 \(b_i\) 中第 \(j\) 位为 \(1\) 的有 \(k\) 个 .

考虑子序列中 xor 起来最终第 \(j\) 位为 \(1\) 的子序列数量 .

当 \(k=0\) 时，必然为 \(0\) .

否则，考虑前把一个第 \(j\) 位为 \(1\) 的数换到末尾，这样不影响结果 . 前 \(n-1\) 个数随便选 ，一共是 \(2^{n-1}\) 个子序列 . 如果前面 xor 为 \(0\) ，那么，最后一个选 ; 否则，最后一个不选 . 都只有一种选择，所以，一共是 \(2^{n-1}\) 个选法 .

所以，只需要对 \(b_i\) 的 or 乘上 \(2^{n-1}\) .

但是 \(b_i\) 的 or ，必然是 \(x\) 的 or . 一定不存在 \(b_i\) 中某一位为 \(1\) 而 \(x\) 中不为 \(1\) .

那么，答案即是 \(x\) 的 or 乘上 \(2^{n-1}\) .

时间复杂度 : \(O(n+m)\)

空间复杂度 : \(O(1)\)

#include
using namespace std;
const int mod=1e9+7;
int t;
int n,m;
inline void upd(int&x,int y){x=(x+y)%mod;}
inline int ksm(int x,int k){
	if(k==0)return 1;
	int res=ksm(x,k>>1);
	res=1ll*res*res%mod;
	if(k&1)res=1ll*res*x%mod;
	return res;
}
void solve(){
	cin>>n>>m;
	int ans=0;
	for(int i=0;i>l>>r>>x;
		ans|=x;
	}
	ans%=mod;
	cout<<1ll*ans*ksm(2,n-1)%mod<>t;
	while(t--){
		solve();
	}
	return 0;
}
/*inline? ll or int? size? min max?*/

D2. Divan and Kostomuksha (hard version)

给定一个序列 \(a\) ，定义其权值为：

\[\sum_{i=1}^n\gcd(a_1,a_2,...,a_i) \]

现在你可以重排 \(a\) ，求这个权值的最大值。

\(1\leq n\leq 10^5,1\leq a_i\leq 2\cdot 10^7\)

用 \(dp(i)\) 表示，从前往后 \(\gcd\) 为 \(i\) 时的最大和 . 用 \(cnt(i)\) 表示 \(a_i\) 中包含 \(i\) 的数的个数 .

转移时枚举 \(i\) 中的所有质因数 \(k\) 进行转移，

最后 \(dp(1)\) 即为答案 .

但是，如果做到用最少的复杂度得到 \(j\) 呢 ？

考虑对 \(2\times 10^7\) 的数都维护一个 \(nxt(i)\) 表示 \(i\) 的最小质数 . 此时，只需要循环求一下 \(i/nxt(i)\) 的 \(nxt(i)\) ，知道 \(i=1\) 时就可以得到所有质数.

求 \(nxt(i)\) 需要的时间为 \(O(v\log v)\) 的，但是听说这个时间复杂度是 \(O(\log v\log v)\) 的.

时间复杂度 : \(O(v\log v\log v)\)

空间复杂度 : \(O(v)\)

#include
using namespace std;
int n;
int a[100010];
bool vis[20000010];
int cnt[20000010];
long long dp[20000010];
bool pri[20000010];
int nxt[20000010];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=0;i>a[i];
	for(int i=0;i20000000)continue;
		for(int j=i*i;j<=20000000;j+=i){
			pri[j]=false;
			if(!nxt[j])nxt[j]=i;
		}
	}
	for(int i=1;i<=20000000;i++)if(vis[i])dp[i]=1ll*i*cnt[i];
	long long ans=0;
	for(int i=20000000;i>=1;i--)if(vis[i]){
		ans=max(ans,dp[i]);
		int tmp=i;
		while(nxt[tmp]!=0){
			int x=i/nxt[tmp];
			dp[x]=max(dp[x],dp[i]+1ll*x*(cnt[x]-cnt[i]));
			tmp=tmp/nxt[tmp];
		}
	}
	cout<

#include
using namespace std;
const int inf=1e9;
int n,cnt=0;
class node{public:int ls,rs,mn,mx,tag;}ts[50000010];
inline new_node(int mn,int mx){
	++cnt;
	ts[cnt].ls=ts[cnt].rs=0;
	ts[cnt].mn=mn;
	ts[cnt].mx=mx;
	ts[cnt].tag=0;
	return cnt;
}
inline void pd(int x){
	if(ts[x].tag==0)return;
	if(ts[x].ls){
		ts[ts[x].ls].mn+=ts[x].tag;
		ts[ts[x].ls].mx+=ts[x].tag;
		ts[ts[x].ls].tag+=ts[x].tag;
	}
	if(ts[x].rs){
		ts[ts[x].rs].mn+=ts[x].tag;
		ts[ts[x].rs].mx+=ts[x].tag;
		ts[ts[x].rs].tag+=ts[x].tag;
	}
	ts[x].tag=0;
}
void upd1(int x,int l,int r,int k){
	if(ts[x].mn>k)return;
	if(ts[x].mx>1;
	if(!ts[x].ls){
		int tmp=new_node(l,mid);
		ts[x].ls=tmp;
		ts[tmp].mn+=ts[x].mn-l;
		ts[tmp].mx+=ts[x].mx-r;
	}
	if(!ts[x].rs){
		int tmp=new_node(mid+1,r);
		ts[x].rs=tmp;
		ts[tmp].mn+=ts[x].mn-l;
		ts[tmp].mx+=ts[x].mx-r;
	}
	if(ts[ts[x].ls].mnk){
		pd(x);
		ts[x].mn--;
		ts[x].mx--;
		ts[x].tag--;
		return;
	}
	if(l==r)return;
	pd(x);
	int mid=(l+r)>>1;
	if(!ts[x].ls){
		int tmp=new_node(l,mid);
		ts[x].ls=tmp;
		ts[tmp].mn+=ts[x].mn-l;
		ts[tmp].mx+=ts[x].mx-r;
	}
	if(!ts[x].rs){
		int tmp=new_node(mid+1,r);
		ts[x].rs=tmp;
		ts[tmp].mn+=ts[x].mn-l;
		ts[tmp].mx+=ts[x].mx-r;
	}
	if(ts[ts[x].rs].mx>k)upd2(ts[x].rs,mid+1,r,k);
	if(ts[ts[x].ls].mx>k)upd2(ts[x].ls,l,mid,k);
	ts[x].mn=ts[ts[x].ls].mn;
	ts[x].mx=ts[ts[x].rs].mx;
}
int qry(int x,int l,int r,int k){
	if((!ts[x].ls)&&(!ts[x].rs))return k+ts[x].mn-l;
	pd(x);
	int mid=(l+r)>>1;
	if(k<=mid){
		if(!ts[x].ls)return k+ts[x].mn-l;
		else return qry(ts[x].ls,l,mid,k);
	}
	else{
		if(!ts[x].rs)return k+ts[x].mx-r;
		else return qry(ts[x].rs,mid+1,r,k);
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int rt=new_node(0,inf);
	cin>>n;
	int ans=0;
	for(int i=0;i>t;
		upd1(rt,0,inf,t);
		upd2(rt,0,inf,t);
		int k;cin>>k;
		for(int j=0;j>x;
			x=(x+ans)%(inf+1);
			ans=qry(rt,0,inf,x);
			cout<