题解 CF482B 【Interesting Array】

### Hint 看到题解区都是$O(n log_2^2 n )$的线段树算法，其实本题是有$O(n log_2 n)$写法的并且不用线段树。 ### 正文 #### 题意 > 给出若干个要求，$l_i ， r_i ， q_i$表示$a[l_i] \& a[l_i + 1]\& ... \& a[r_i] = q_i$ > > 如果存在数组$a$则输出一行$YES$然后输出一种合法的数组. 否则，输出一行$NO$. > > 对于100%的数据 $\leq n\leq 10^5 , q_i \leq 2^{30}$ #### 解析 可以把每个二进制为拉出来，对每一个位分别处理 如果一个区间$l,r$ 区间 $ and $ 值为1，那么 说明这个区间必须全部是$1$ 所以我们直接对这个区间赋值为$1$即可。 然后对每个询问做一遍check，判断是否合法，即看看是$0$位置上的$l,r$是不是都是$1$，一旦都是1，那么就前后矛盾，输出$NO$. 上述维护可以使用差分前缀和维护。复杂度是$O(n \ log_2 \ n)$ #### 程序 ```cpp # include<bits/stdc++.h> # define int long long using namespace std; const int N=1e5+10; int n,Q,c[31][N],ans[31][N]; struct rec{ int l,r,d; }q[N]; void update(int l,int r,int d) { for (int i=30;i>=0;i--) if (d&(1ll<<i)) c[i][l]++,c[i][r+1]--; } void init() { for (int i=0;i<=30;i++) for (int j=1;j<=n;j++) c[i][j]=c[i][j-1]+c[i][j]; for (int i=0;i<=30;i++) for (int j=1;j<=n;j++) c[i][j]=(c[i][j]>0); memcpy(ans,c,sizeof(c)); for (int i=0;i<=30;i++) for (int j=1;j<=n;j++) c[i][j]=c[i][j-1]+c[i][j]; } bool check(int l,int r,int d) { for (int i=30;i>=0;i--) if ((!(d&(1ll<<i)))&&(c[i][r]-c[i][l-1]==r-l+1)) return false; return true; } signed main() { scanf("%lld%lld",&n,&Q); for (int i=1;i<=Q;i++) { scanf("%lld%lld%lld",&q[i].l,&q[i].r,&q[i].d); update(q[i].l,q[i].r,q[i].d); } init(); for (int i=1;i<=Q;i++) if (!check(q[i].l,q[i].r,q[i].d)) { puts("NO"); return 0; } puts("YES"); for (int i=1;i<=n;i++) { int ret=0; for (int j=0;j<=30;j++) if (ans[j][i]) ret+=(1<<j); printf("%lld ",ret); } return 0; } ```