noip模拟赛 fateice-or

分析:or操作只有在结果的这一位为0的情况下才会强制要求两个数的这一位都为0，其它时候不强求，所以为了最大限度地满足条件，我们先把所有的数的所有位全部变成1，如果p的第i位为0，那么[l,r]的数的第i位都要为0，&一下p就好了.最后检验一下看看是否满足所有条件就可以了。为什么这样做事合法的呢？因为我们之前已经尽可能让它最大限度地满足条件了，某一位更改后可能就不能满足这么多条件了,如果这都不行，那么肯定无解.因为是区间&操作，所以用线段树来优化.

构造题要满足所有的条件，那么就构造出尽可能多地满足条件的，最后检验一下就可以了.

注意：实际操作是|，但是每次进行的操作是&,在合并和修改的时候不要弄混了.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int inf = ( << ) - , maxn = ;

int n, m, l[maxn], r[maxn], p[maxn], v[maxn * ], tag[maxn * ], flag[maxn * ];

bool can = true;

void build(int o, int l, int r)

{

    tag[o] = v[o] = inf;

    if (l == r)

        return;

    int mid = (l + r) >> ;

    build(o * , l, mid);

    build(o *  + , mid + , r);

}

void pushup(int o)

{

    v[o] = v[o * ] | v[o *  + ];

}

void pushdown(int o)

{

    if (flag[o])

    {

        flag[o * ] = flag[o *  + ] = ;

        flag[o] = ;

        tag[o * ] &= tag[o];

        tag[o *  + ] &= tag[o];

        v[o * ] &= tag[o];

        v[o *  + ] &= tag[o];

        tag[o] = inf;

    }

}

void update(int o, int l, int r, int x, int y, int c)

{

    if (x <= l && r <= y)

    {

        tag[o] &= c;

        v[o] &= c;

        flag[o] = ;

        return;

    }

    pushdown(o);

    int mid = (l + r) >> ;

    if (x <= mid)

        update(o * , l, mid, x, y, c);

    if (y > mid)

        update(o *  + , mid + , r, x, y, c);

    pushup(o);

}

int query(int o, int l, int r, int x, int y)

{

    if (x <= l && r <= y)

        return v[o];

    pushdown(o);

    int mid = (l + r) >> , res = ;

    if (x <= mid)

        res |= query(o * , l, mid, x, y);

    if (y > mid)

        res |= query(o *  + , mid + , r, x, y);

    return res;

}

int main()

{

    freopen("or1.in", "r", stdin);

    freopen("or2.txt", "w", stdout);

    scanf("%d%d", &n, &m);

    build(, , n);

    for (int i = ; i <= m; i++)

    {

        scanf("%d%d%d", &l[i], &r[i], &p[i]);

        update(, , n, l[i], r[i], p[i]);

    }

    for (int i = ; i <= m; i++)

        if (query(, , n, l[i], r[i]) != p[i])

        {

            can = ;

            break;

        }

    if (can == false)

        printf("No\n");

    else

    {

        printf("Yes\n");

        for (int i = ; i <= n; i++)

            printf("%d ",query(,,n,i,i));

    }

    return ;

}

巴特西

noip模拟赛 fateice-or

最新文章

热门文章