Data Structure

将一个非负整数序列划分为 $\ K$ 段，分别计算出各段中的整数按位或的结果，然后再把这些结果按位与起来得到一个最终结果，把这个最终结果定义为这个序列的一个 $\ K-or-and$ 值。

比如序列为 $\ [1,5,9,2] ,K=2$ ，如果划分为 $\ [1,5],[9,2]$ ,那么 $\ K-or-and$ 值为 $\ (1 \; or \;5) \; and \; (9 \; or \;2) = 1$ 。当然划分可能不止一种，所以 $\ K-or-and$ 值也可能不止一个。

给定一个长度为 $\ N$ 的非负整数序列 $\ A_{1}A_{2}A_{3}...A_{N}$ ，一个整数 $\ K$ 和以下三种操作：

1.给定一个整数 $\ x$ ，把序列中的所有数字按位或上 $\ x$ 。即 $\forall \; i \in [1,N], A_{i}= A_{i} \; or \; x$ 。

2.给定一个整数 $\ x$ ，把序列中的所有数字按位与上 $\ x$ 。即 $\forall \; i \in [1,N], A_{i}= A_{i} \; and \; x$ 。

3.查询当前序列最大的 $\ K-or-and$ 值。

lililalala太菜了，他希望你来帮他解决这个问题。

第一行两个整数 $\ N,K(1 \le K \le N \le 2 \times 10^{5})$ --序列长度和划分的段数。

第二行 $\ N$ 个整数 $\ A_{1}A_{2}A_{3}...A_{N} ( \ 0 \leq \ A_{1}A_{2}A_{3}...A_{N} < 2^{31} )$ 。

第三行一个整数 $\ Q(1 \le Q \le 2 \times 10^{5})$ --操作的数量。

然后 $\ Q$ 行其中第 $\ i$ 行为以下三种格式之一:

$\ 1 \quad x_{i}$ --把序列中的所有数字按位或上 $\ x_{i}(0 \leq x_{i} < 2^{31})$ 。

$\ 2 \quad x_{i}$ --把序列中的所有数字按位与上 $\ x_{i}(0 \leq x_{i} < 2^{31})$ 。

$\ 3$ --查询当前序列最大的 $\ K-or-and$ 值。

#include<bits/stdc++.h> #define N 200010 #define sc(x) scanf("%d",&x) #define scc(x,y) scanf("%d%d",&x,&y) using namespace std; int a[N],v[32],n,m,q,fg,ans; void spy(){ ans=0; for(int i=30;i>=0;i--) if (!(fg>>i&1)){ int tm=ans|(1<<i),cnt=0,x=0; for (int j=1;j<=n;j++){ x|=a[j]; if ((x&tm)==tm) cnt++,x=0; } if (cnt>=m) ans|=(1<<i); } } int main(){ scc(n,m); for (int i=1;i<=n;i++) sc(a[i]); sc(q); spy(); while(q--){ int op,x;sc(op); if (op<3){ op=2-op; sc(x); int tm=fg; for (int i=0;i<=30;i++) if ((x>>i&1)==op) tm|=(1<<i),v[i]=op; if (tm!=fg) fg=tm,spy(); }else{ int tm=ans; for (int i=0;i<=30;i++) if (fg>>i&1) tm|=v[i]<<i; printf("%d\n",tm); } } }

详情