Codeforces 482B 线段树

本文主要是介绍Codeforces 482B 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求是否存在这样的n个数；

m次操作，每次操作就是三个数 l ，r，val

         a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。

也就是意味着区间[L , R] 每个数要执行 | val 操作 

最后判断  a[l] & a[l+1] &......&a[r] 是否= val

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;public class Main {public static void main(String[] args){new CF482B().solve()  ; }
}class CF482B{InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;void solve(){int n = in.nextInt() ;int m = in.nextInt() ;build(1 , 1 , n) ;for(int i = 1 ;  i <= m ; i++){l[i] = in.nextInt() ;r[i] = in.nextInt() ;q[i] = in.nextInt() ;update(l[i] , r[i] , q[i] , 1 , 1, n) ;}boolean can = true ;for(int i = 1 ; i <= m ; i++){if(query(l[i] , r[i] , 1 , 1 , n) != q[i]){can = false ;break ; }}if(can){out.println("YES") ; for(int i = 1 ; i <= n ; i++){if(i > 1) out.print(" ") ;out.print(query(i , i , 1 , 1 , n)) ;}out.println() ;}else out.println("NO")  ;out.flush() ;}final int N = 100008 ;int[] sum = new int[N<<2] ;int[] add = new int[N<<2] ;int[] l = new int[N] ;int[] r = new int[N] ;int[] q = new int[N] ;void build(int t , int l , int r){sum[t] = add[t] = 0 ;if(l == r) return ;int mid = (l + r) >> 1 ;build(t<<1 , l , mid) ;build(t<<1|1 , mid+1 , r) ;up(t) ;}void up(int t){sum[t] = sum[t<<1] & sum[t<<1|1] ;}void down(int t){if(add[t] != 0){sum[t<<1] |= add[t] ;sum[t<<1|1] |= add[t] ;add[t<<1] |= add[t] ;add[t<<1|1] |= add[t] ;add[t] = 0 ;}}void update(int L , int R , int v ,  int t , int l , int r){if(L <= l && r <= R){add[t] |= v ;sum[t] |= v ;return ;}down(t) ;int mid = (l + r) >> 1 ;if(L <= mid) update(L, R, v , t<<1 , l , mid)  ;if(R > mid) update(L , R , v , t<<1|1 , mid+1 , r) ;up(t) ;}int query(int L , int R , int t , int l , int r){if(L <= l && r <= R) return sum[t] ;int res = (1<<30) - 1  ; down(t) ;int mid = (l + r) >> 1 ;if(L <= mid) res &= query(L, R, t<<1 , l , mid) ;if(R > mid) res &= query(L, R, t<<1|1 , mid+1 , r) ;up(t) ;return res ;}}class InputReader {  public BufferedReader reader;  public StringTokenizer tokenizer;  public InputReader(InputStream stream) {  reader = new BufferedReader(new InputStreamReader(stream), 32768);  tokenizer = new StringTokenizer("");  }  private void eat(String s) {  tokenizer = new StringTokenizer(s);  }  public String nextLine() {  try {  return reader.readLine();  } catch (Exception e) {  return null;  }  }  public boolean hasNext() {  while (!tokenizer.hasMoreTokens()) {  String s = nextLine();  if (s == null)  return false;  eat(s);  }  return true;  }  public String next() {  hasNext();  return tokenizer.nextToken();  }  public int nextInt() {  return Integer.parseInt(next());  }  public long nextLong() {  return Long.parseLong(next());  }  public double nextDouble() {  return Double.parseDouble(next());  }  public BigInteger nextBigInteger() {  return new BigInteger(next());  }  }  

   

这篇关于Codeforces 482B 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---