程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CodeForces 482B Interesting Array 線段樹

CodeForces 482B Interesting Array 線段樹

編輯：C++入門知識

CodeForces 482B Interesting Array 線段樹

B. Interesting Array time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

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.

Sample test(s) input

3 1
1 3 3

output

YES
3 3 3

input

3 2
1 3 3
1 3 2

output

NO

題意：給m個區間及區間內每個數&值,問存不存在這樣一個數列滿足。

分析：對於每一個區間[l,r]&值為q，那麼說明這個區間每一個數都得或q。用線段樹維護下區間更新,，注意向下更新是或，向上合並是與。最後查詢下各自的區間看值是否滿足。滿足再輸出對應的單個點的值。

/**
 * @author neko01
 */
//#pragma comment(linker, /STACK:102400000,102400000)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
using namespace std;
typedef long long LL;
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define clr(a) memset(a,0,sizeof a)
#define clr1(a) memset(a,-1,sizeof a)
#define dbg(a) printf(%d
,a)
typedef pair pp;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x7fffffff;
const LL inf=(((LL)1)<<61)+5;
const int N=100005;
struct node{
    int l,r;
    int col;
    int val;
}tree[N*4];
void build(int x,int l,int r)
{
    tree[x].l=l,tree[x].r=r;
    tree[x].col=tree[x].val=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}
inline void push_down(int x)
{
    if(tree[x].col!=0)
    {
        tree[x<<1].col|=tree[x].col;
        tree[x<<1|1].col|=tree[x].col;
        tree[x<<1].val|=tree[x].col;
        tree[x<<1|1].val|=tree[x].col;
        tree[x].col=0;
    }
}
void update(int x,int l,int r,int val)
{
    if(tree[x].l==l&&tree[x].r==r)
    {
        tree[x].val|=val;
        tree[x].col|=val;
        return;
    }
    push_down(x);
    int mid=(tree[x].l+tree[x].r)>>1;
    if(r<=mid) update(x<<1,l,r,val);
    else if(l>mid) update(x<<1|1,l,r,val);
    else
    {
        update(x<<1,l,mid,val);
        update(x<<1|1,mid+1,r,val);
    }
    tree[x].val=tree[x<<1].val&tree[x<<1|1].val;
}
int query(int x,int l,int r)
{
    if(tree[x].l==l&&tree[x].r==r)
        return tree[x].val;
    push_down(x);
    int mid=(tree[x].l+tree[x].r)>>1;
    if(r<=mid) return query(x<<1,l,r);
    else if(l>mid) return query(x<<1|1,l,r);
    else return query(x<<1,l,mid)&query(x<<1|1,mid+1,r);
}
int l[N],r[N],q[N];
int main()
{
    int n,m;
    scanf(%d%d,&n,&m);
    build(1,1,n);
    for(int i=0;i