CF 482B Interesting Array

문제

https://codeforces.com/contest/482/problem/B

길이 N의 배열에 l~r 구간에 대해 모든 값들을 & 한 결과값들이 m개 주어져 있을 때, 이 모든 조건을 만족하는 배열을 구하는 문제이다.

 

풀이

bitwise 연산이 들어간 문제의 대다수는 각 비트를 따로 생각해주면 풀리는 경우가 많다.

이 문제도 n번째 칸의 i번째 비트가 켜져 있는지, 꺼져 있는지 각각 구해주자.

 

만약 l~r 까지의 & 값이 켜져 있다는 말은, l~r 의 i번째 비트는 모두 다 켜져 있다는 뜻이다.

따라서 먼저 모든 m을 보며 l~r의 i번째 비트를 켜준다.

그 후에 켜져 있지 않은 비트는 무조건 꺼져 있다고 생각해도 답에 영향을 미치지 않는다.

마지막으로 꺼져 있는 비트에 대해서 검사를 하며, l~r의 모든 비트가 켜져 있다면 불가능함을 알 수 있다.

 

이러한 과정을 거치기 위해서는 구간에 대해서 비트들을 켜고, 구간의 비트의 수를 세주는 자료구조가 필요하다.

제일 생각하기 쉬운것은 세그먼트 트리이고, 펜윅트리에 약간의 정의를 변형시키면 구간에 대해 더해주는 연산을 구현할 수 있다.

 

하지만, 이것은 누적합 배열 하나로도 충분히 해결 가능하다.

그 이유는 업데이트 연산과 쿼리 연산이 서로 도중에 일어나는 것이 아니라, 업데이트를 모두 해준 후 개수를 세주면 되기 때문이다.

업데이트는 arr[l]++; arr[r-1]--; 을 통해 누적합을 갱신해주고, 중복으로 더해진 값들을 1로 만들어준 후에 다시 누적합을 계산해주면, 모든 연산을 $O(1)$ 만에 처리할 수 있다.

 

시간 복잡도 : $O(30*(N+M))$ $(O((N+M)logMAXNUM)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

struct Query { int l, r, q; };

int n, m;
int arr[31][MAXN+10];
Query query[MAXN+10];

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++) scanf("%d%d%d", &query[i].l, &query[i].r, &query[i].q);

    for(i=1; i<=m; i++)
    {
        for(j=0; j<30; j++)
        {
            if(query[i].q&(1<<j))
            {
                arr[j][query[i].l]++;
                arr[j][query[i].r+1]--;
            }
        }
    }

    for(i=0; i<30; i++) for(j=1; j<=n; j++) arr[i][j]+=arr[i][j-1];
    for(i=0; i<30; i++) for(j=1; j<=n; j++) if(arr[i][j]) arr[i][j]=1;
    for(i=0; i<30; i++) for(j=1; j<=n; j++) arr[i][j]+=arr[i][j-1];

    for(i=1; i<=m; i++)
    {
        for(j=0; j<30; j++)
        {
            if(query[i].q&(1<<j)) continue;
            int one=arr[j][query[i].r]-arr[j][query[i].l-1];
            if(one==query[i].r-query[i].l+1)
            {
                printf("NO");
                return 0;
            }
        }
    }

    printf("YES\n");
    for(i=1; i<=n; i++)
    {
        int now=0;
        for(j=0; j<30; j++) if(arr[j][i]-arr[j][i-1]) now+=(1<<j);
        printf("%d ", now);
    }
    return 0;
}