HDU 4902 Nice boat 2014杭電多校訓練賽第四場F題（線段樹區間更新）
解題報告：輸入一個序列，然後有q次操作，操作有兩種，第一種是把區間 (l,r) 變成x，第二種是把區間 (l,r) 中大於x的數跟 x 做gcd操作。
線段樹區間更新的題目，每個節點保存一個最大和最小值，當該節點的最大值和最小值相等的時候表示這個區間所有的數字都是相同的，可以直接對這個區間進行1或2操作，
進行1操作時，當還沒有到達要操作的區間但已經出現了節點的最大值跟最小值相等的情況時，說明這個區間的值都是相同的，但現在我只要在這個區間的一部分進行1操作，所以
我要先把這個節點的最大的最小值往下壓，直到找到了要操作的區間。
進行2操作時，如果該區間的最大值都小於x，則可以直接退出，如果最大值大於x，則表示這個區間可以進行gcd操作，然後繼續往下，直到找到最大值跟最小值相等的區間才開始
進行gcd操作，進行gcd操作之後不要忘了更新父節點的最大最小值。
復制代碼
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6 #define maxn 100005
7 struct node
8 {
9 int Max,Min,l,r;
10 }tree[4*maxn];
11 void build(int p)
12 {
13 if(tree[p].l == tree[p].r) return ;
14 int mid = (tree[p].l + tree[p].r) / 2;
15 tree[2*p].Max = tree[2*p+1].Max = -1;
16 tree[2*p].Min = tree[2*p+1].Min = 0x7fffffff;
17 tree[2*p].l = tree[p].l;
18 tree[2*p].r = mid;
19 tree[2*p+1].l = mid + 1;
20 tree[2*p+1].r = tree[p].r;
21 build(2*p);
22 build(2*p+1);
23 }
24 void push(int p,int l,int d)
25 {
26 tree[p].Max = max(tree[p].Max,d);
27 tree[p].Min = min(tree[p].Min,d);
28 if(tree[p].l == tree[p].r) return ;
29 int mid = (tree[p].l + tree[p].r) / 2;
30 if(l <= mid) push(2*p,l,d);
31 else push(2*p+1,l,d);
32 }
33 int gcd(int a,int b)
34 {
35 return b == 0? a : gcd(b,a%b);
36 }
37 void oper1(int p,int l,int r,int x)
38 {
39 if(tree[p].l == l && tree[p].r == r)
40 {
41 tree[p].Max = tree[p].Min = x;
42 return ;
43 }
44 int mid = (tree[p].l + tree[p].r) / 2;
45 if(tree[p].Max == tree[p].Min)
46 {
47 oper1(2*p+1,mid+1,tree[p].r,tree[p].Max); //先把當前區間的值往下壓
48 oper1(2*p,tree[p].l,mid,tree[p].Max);
49 }
50 tree[p].Max = max(tree[p].Max,x);
51 tree[p].Min = min(tree[p].Min,x);
52 if(r <= mid)
53 oper1(2*p,l,r,x);
54 else if(l <= mid && r > mid)
55 {
56 oper1(2*p,l,mid,x);
57 oper1(2*p+1,mid+1,r,x);
58 }
59 else oper1(2*p+1,l,r,x);
60 }
61 void oper2(int p,int l,int r,int x)
62 {
63 int mid = (tree[p].l + tree[p].r) / 2;
64 if(tree[p].l == l && tree[p].r == r)
65 {
66 if(tree[p].Max < x) return ; //最大的都不可以進行gcd操作，直接退出
67 if(tree[p].Max == tree[p].Min) //找到了值都相同的區間，可以直接進行gcd操作
68 {
69 if(tree[p].Max > x) tree[p].Max = tree[p].Min = gcd(tree[p].Max,x);
70 return ;
71 }
72 else if(tree[p].Max > x)
73 {
74 oper2(2*p,l,mid,x);
75 oper2(2*p+1,mid+1,r,x);
76 }
77 return ;
78 }
79 if(tree[p].Max == tree[p].Min) //還沒找到操作的區間之前碰到了這個，則也要通過1操作，把這個節點的值往下壓
80 {
81 oper1(2*p,tree[p].l,mid,tree[p].Max);
82 oper1(2*p+1,mid+1,tree[p].r,tree[p].Max);
83 }
84 if(r <= mid)
85 oper2(2*p,l,r,x);
86 else if(l <= mid && r > mid)
87 {
88 oper2(2*p,l,mid,x);
89 oper2(2*p+1,mid+1,r,x);
90 }
91 else oper2(2*p+1,l,r,x);
92 if(tree[p].l != tree[p].r) //記得更新父節點的最大最小值
93 {
94 tree[p].Max = max(tree[2*p].Max,tree[2*p+1].Max);
95 tree[p].Min = min(tree[2*p].Min,tree[2*p+1].Min);
96 }
97 }
98 int query(int p,int l)
99 {
100 int mid = (tree[p].l + tree[p].r) / 2;
101 if(tree[p].Max == tree[p].Min)
102 return tree[p].Max;
103 if(l <= mid) return query(2*p,l);
104 else return query(2*p+1,l);
105 }
106
107 int main()
108 {
109 int T,n;
110 scanf("%d",&T);
111 while(T--)
112 {
113 scanf("%d",&n);
114 tree[1].Max = -1;
115 tree[1].Min = 0x7fffffff;
116 tree[1].l = 1;
117 tree[1].r = n;
118 build(1);
119 int d;
120 for(int i = 1;i <= n;++i)
121 {
122 scanf("%d",&d);
123 push(1,i,d);
124 }
125 int q,t,l,r,x;
126 scanf("%d",&q);
127 while(q--)
128 {
129 scanf("%d%d%d%d",&t,&l,&r,&x);
130 if(t == 1) oper1(1,l,r,x);
131 else oper2(1,l,r,x);
132 }
133 for(int i = 1;i <= n;++i) //輸出有點不同，PE了好幾次，最後也是有空格的
134 printf("%d ",query(1,i));
135 puts("");
136 }
137 return 0;
138 }
