首页 > 代码库 > Codeforces Round #275 (Div. 2) D

Codeforces Round #275 (Div. 2) D

2024-09-02 05:19:03   224人阅读

题意 ： 一个数组 给出m个限制条件 l r z 代表从l 一直 & 到 r 为 z  问能否构造出这种数组 如果可以 构造出来

因为 n m 都是1e5 而l r 可能输入进去就超时了 所以刚写完线段树课件的我想了很久想出来了线段树解法 ... 

想法是这样的 每次输入 update 结束后 全部query一遍 看看是否和期望一样

一开始的想法是 存下每个数组的&值 一开始是1<<31 - 1 然后每次进行update 都求出这个区间在树上区间没有被更新到的点的& 三者一& 继续向下

但是感觉时间复杂度很玄学 写完直接wa掉了 

后来想出了 | 的解法

思想 ： 

利用tree存放每个区间的&的值 一开始是0 

如果我们对一个区间有一个期望 : l - r = z 那么一定满足一个东西 : l - r 的数字在二进制上全都包含z

所以每次 我们都对这个区间进行一个 | 上 z 的运算 至少要让 l - r 的数字拥有z

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<queue>
using namespace std;
#define L long long
struct node{
    int l , r ;
    int z ;
}tr[100000 * 5];
int mark[100000 * 5] ;
int n , m ;
node in[100500] ;

int maxx ;

void crea(int ro , int l ,int r ) {
    tr[ro].l = l ;
    tr[ro].r = r ;
    tr[ro].z = 0 ;
    if(l == r)return ;
    int mid = (l + r) / 2 ;
    crea(ro*2 , l , mid ) ;
    crea(ro*2+1, mid + 1 , r) ;
}
void pushdown(int ro) {
    if(mark[ro] == 0) {
        return ;
    }
    if(tr[ro].l == tr[ro].r) return ;
    mark[ro*2] |= mark[ro] ;
    mark[ro*2+1] |= mark[ro] ;
    tr[ro*2].z |= mark[ro] ;
    tr[ro*2+1].z |= mark[ro] ;
    mark[ro] = 0 ;
    return ;
}

int query(int ro , int l , int r ){
    pushdown(ro) ;
    if(l <= tr[ro].l && r >= tr[ro].r) {
        return tr[ro].z ;
    }
    int mid = (tr[ro].l + tr[ro].r) / 2 ;
    if(r <= mid) {
        return query(ro*2 , l , r ) ;
    }
    else if(l >= mid + 1 ) {
        return query(ro*2+1 , l , r ) ;
    }
    else {
        return query(ro*2 , l , r ) & query(ro*2+1 , l , r ) ;
    }
}

void upda(int ro , int l , int r , int z) {
    pushdown(ro) ;
    if(l <= tr[ro].l && r >= tr[ro].r) {
        tr[ro].z |= z ;
        mark[ro] = z ;
        return ;
    }
    if(tr[ro].l == tr[ro].r) return ;
    int mid = (tr[ro].l + tr[ro].r) / 2 ;
    if(r <= mid){
        upda(ro*2 , l , r , z) ;
    }
    else if(l >= mid + 1) {
        upda(ro*2+1 , l , r , z) ;
    }
    else {
        upda(ro*2 , l , mid , z) ;
        upda(ro*2+1 , mid + 1 , r , z) ;
    }
    tr[ro].z = tr[ro*2].z & tr[ro*2+1].z ;
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        maxx = (1 << 31)- 1 ;
        for(int i = 0 ; i <= n * 5 - 5 ; i ++ ) {
            mark[i] = 0 ;
        }
        crea(1,1,n) ;
        for(int i = 1; i <= m ; i ++ ){
            scanf("%d%d%d" , &in[i].l, &in[i].r , &in[i].z) ;
            upda(1 , in[i].l , in[i].r , in[i].z) ;
        }
        bool ok = true ;
        for(int i = 1; i <= m ; i ++ ){
            int z = query(1 , in[i].l , in[i].r ) ;
            if(z != in[i].z) {
                ok = false ;
                break ;
            }
        }
        if(ok) {
            printf("YES\n") ;
            for(int i = 1; i <= n ; i ++ ){
                printf("%d",query(1,i,i)) ;
                if(i == n)printf("\n");
                else printf(" ") ;
            }
        }
        else {
            printf("NO\n") ;
        }
    }
}

　　

Codeforces Round #275 (Div. 2) D


联系
我们