HDU4902 线段树

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

n个数，m个操作，

1 L R X  :区间[L,R]的数同时置为X;

2 L R X  :区间[L,R]大于X的数y,置为gcd(X,y)

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 Task().solve();}
}class Task {InputReader in = new InputReader(System.in);PrintWriter out = new PrintWriter(System.out);int[] val ;void build(int l , int r,  int t){val[t] = -1 ;if(l == r){val[t] = in.nextInt() ;return ; }int m = (l + r) >> 1 ;build(l, m, t<<1) ;build(m+1, r, t<<1|1) ;up(t) ;}void up(int t){if(val[t<<1] == val[t<<1|1]){val[t] = val[t<<1] ;}else{val[t] = -1 ;}}void down(int t){if(val[t] != -1){val[t<<1] = val[t<<1|1] = val[t] ;val[t] = -1 ;} }int gcd(int x , int y){return y == 0 ? x : gcd(y , x % y) ;}void update(int type , int L , int R , int x ,  int l , int r , int t){if(type == 1){if(L <= l && r <= R){val[t] = x ;return  ;}}else{if(L <= l && r <= R && val[t] != -1){if(val[t] > x){val[t] = gcd(val[t] , x) ;}return ; }}down(t) ;int m = (l + r) >> 1 ;if(L <= m){update(type, L, R, x, l, m, t<<1) ;}if(R > m){update(type, L, R, x, m+1, r, t<<1|1) ;}up(t) ;}void query(int l , int r , int t){if(l == r){out.print(val[t] + " ") ;return ;}down(t) ;int m = (l + r) >> 1 ;query(l, m, t<<1);query(m+1, r, t<<1|1) ;}void solve() {int t = in.nextInt() ;while(t-- > 0){int n = in.nextInt() ;val = new int[n<<2] ;build(1, n, 1) ;int m = in.nextInt() ;while(m-- > 0){update(in.nextInt() , in.nextInt() , in.nextInt() , in.nextInt() , 1 , n , 1) ; }query(1 , n , 1) ;out.println() ;}out.flush();}
}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());}}

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

---