B. Interesting Array（线段树）

系统管理员 2021-11-02 08:46 172阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
题目链接：[http://codeforces.com/problemset/problem/482/B][http_codeforces.com_problemset_problem_482_B]  
We’ll call an array of n non-negative integers a\[1\], a\[2\], …, a\[n\] interesting, if it meets m constraints. The i-th of the m constraints consists of three integers li, ri, qi (1 ≤ li ≤ ri ≤ n) meaning that value should be equal to qi.

Your task is to find any interesting array of n elements or state that such array doesn’t exist.

Expression x&y means the bitwise AND of numbers x and y. In programming languages C++, Java and Python this operation is represented as “&”, in Pascal — as “and”.  
Input

The first line contains two integers n, m (1 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of elements in the array and the number of limits.

Each of the next m lines contains three integers li, ri, qi (1 ≤ li ≤ ri ≤ n, 0 ≤ qi < 230) describing the i-th limit.  
Output

If the interesting array exists, in the first line print “YES” (without the quotes) and in the second line print n integers a\[1\], a\[2\], …, a\[n\] (0 ≤ a\[i\] < 230) decribing the interesting array. If there are multiple answers, print any of them.

If the interesting array doesn’t exist, print “NO” (without the quotes) in the single line.  
Examples  
Input  
Copy

3 1  
1 3 3

Output  
Copy

YES  
3 3 3

Input  
Copy

3 2  
1 3 3  
1 3 2

Output  
Copy

分析：  
涨姿势的一个题。还是菜鸡人生呀。　  
对于给出的一个区间如　1 ５ ３　那么１到５这５个元素的二进制一定是＆３等于３的（通俗讲就是这５个元素的二进制的第１和第２位都是为１的，因为３的二进制第一第二位是为１的）。  
同理，对于给出的每个　l ｒｑ　的操作，都有这样的性质。  
那么，我们可以知道val\[1\] 是在区间1到2 和区间1-3 ……里面的。所以val\[1\]的值一定要满足这些区间的性质。  
同理，我们可以得到其他的值。通过更新可以得到区间的&值。  
参考博客：[https://blog.csdn.net/Seven\_Jun/article/details/51910425][https_blog.csdn.net_Seven_Jun_article_details_51910425]  
[https://blog.csdn.net/qq\_31759205/article/details/52454005][https_blog.csdn.net_qq_31759205_article_details_52454005]

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    typedef pair<int,int> PII;
    struct Node
    {
        int l;int r;int x;
    }node[100010];
    
    int n,m;
    int val[5000101];
    int num_val[2000101],top;
    
    void Push_down(int id)
    {
        val[id] = val[id << 1] & val[id << 1 | 1]; return ;
    }
    
    void Update(int id,int L,int R,int l,int r,int v)
    {
       if(l <= L && r >= R)
       {
           val[id] |= v; return ;
       }
       int mid = (L + R) >> 1;
       if(l <= mid) Update(id << 1,L,mid,l,r,v);
       if(r > mid) Update(id << 1 | 1,mid + 1,R,l,r,v);
    }
    void seek(int id,int L,int R,int x)
    {
        x |= val[id];
        if(L == R)
        {
            val[id] = x; num_val[L] = val[id];
            return ;
        }
        int mid = (L + R) >> 1;
        seek(id << 1,L,mid,x);
        seek(id << 1 | 1,mid + 1,R,x);
        Push_down(id);
    }
    
    int Query(int id,int L,int R,int l,int r)
    {
        if(l <= L && r >= R) return val[id];
        int mid = (L + R) >> 1;
        int A = -1,B = -1;
        if(l <= mid) A = Query(id << 1,L,mid,l,r);
        if(r > mid) B = Query(id << 1 | 1,mid + 1,R,l,r);
        if(A == -1) return B;
        if(B == -1) return A;
        return A & B;
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= m;i ++)
        {
            scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].x);
            Update(1,1,n,node[i].l,node[i].r,node[i].x);
        }
        seek(1,1,n,0);
        for(int i = 1; i <= m; i ++)
        {
            int ans = Query(1,1,n,node[i].l,node[i].r);
            if(ans == node[i].x) continue;
            printf("NO\n"); return 0;
        }
        printf("YES\n");
        for(int i = 1; i<= n;i ++)
            printf("%d ",num_val[i]);
        printf("\n");
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/
[http_codeforces.com_problemset_problem_482_B]: http://codeforces.com/problemset/problem/482/B
[https_blog.csdn.net_Seven_Jun_article_details_51910425]: https://blog.csdn.net/Seven_Jun/article/details/51910425
[https_blog.csdn.net_qq_31759205_article_details_52454005]: https://blog.csdn.net/qq_31759205/article/details/52454005