Smiling & Weeping
----你是我绕过的山河错落，才找到的人间烟火
Problem Description There is a sequence a of length n. We use ai to denote the i-th element in this sequence. You should do the following three types of operations to this sequence.0 x y t: For every x≤i≤y, we use min(ai,t) to replace the original ai's value.
1 x y: Print the maximum value of ai that x≤i≤y.
2 x y: Print the sum of ai that x≤i≤y.
Input The first line of the input is a single integer T, indicating the number of testcases.
The first line contains two integers n and m denoting the length of the sequence and the number of operations.
The second line contains n separated integers a1,…,an (∀1≤i≤n,0≤ai<231).
Each of the following m lines represents one operation (1≤x≤y≤n,0≤t<231).
It is guaranteed that T=100, ∑n≤1000000, ∑m≤1000000.
Output For every operation of type 1 or 2, print one line containing the answer to the corresponding query.
Sample Input 1 5 5 1 2 3 4 5 1 1 5 2 1 5 0 3 5 3 1 1 5 2 1 5
Sample Output 5 15 3 12 题目链接：Problem - 5306 (hdu.edu.cn) 思路：需要引入一个se次最大值，话不多说 上代码ヾ(@^▽^@)ノ
1 //必须使用C++编译器
2 #include<cstdio>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6 #include<cmath>
7 using namespace std;
8 typedef long long ll;
9 const int maxn = 1000100;
10 #define ls(p) p<<1
11 #define rs(p) p<<1|1
12 int a[maxn] , n , m;
13 int mx[maxn<<2] , cnt[maxn<<2] , se[maxn<<2] , add[maxn<<2];
14 ll sum[maxn<<2];
15 void push_up(int p)
16 {
17 sum[p] = sum[ls(p)] + sum[rs(p)];
18 if(mx[ls(p)] == mx[rs(p)])
19 {
20 se[p] = max(se[ls(p)] , se[rs(p)]);
21 mx[p] = mx[ls(p)];
22 cnt[p] = cnt[ls(p)] + cnt[rs(p)];
23 }
24 else if(mx[ls(p)] > mx[rs(p)])
25 {
26 se[p] = max(se[ls(p)] , mx[rs(p)]);
27 mx[p] = mx[ls(p)];
28 cnt[p] = cnt[ls(p)];
29 }
30 else
31 {
32 se[p] = max(se[rs(p)] , mx[ls(p)]);
33 mx[p] = mx[rs(p)];
34 cnt[p] = cnt[rs(p)];
35 }
36 }
37 void push_down(int p)
38 {
39 if(add[p] == -1) return ; // 区间覆盖
40 int& t = add[p];
41 if(mx[ls(p)] > t && t > se[ls(p)])
42 {
43 sum[ls(p)] -= 1ll*(mx[ls(p)]-t)*cnt[ls(p)];
44 add[ls(p)] = mx[ls(p)] = t;
45 }
46 if(mx[rs(p)] > t && t > se[rs(p)])
47 {
48 sum[rs(p)] -= 1ll*(mx[rs(p)]-t)*cnt[rs(p)];
49 add[rs(p)] = mx[rs(p)] = t;
50 }
51 t = -1;
52 }
53 void build(int p , int pl , int pr)
54 {
55 add[p] = -1;
56 if(pl == pr)
57 {
58 se[p] = -1; cnt[p] = 1;
59 sum[p] = mx[p] = a[pl];
60 return ;
61 }
62 int mid = pl+pr >> 1;
63 build(ls(p) , pl , mid);
64 build(rs(p) , mid+1 , pr);
65 push_up(p);
66 }
67 void update(int L , int R, int p , int pl, int pr , int t)
68 {
69 if(mx[p] <= t) return ;
70 if(L <= pl && pr <= R && se[p] < t)
71 {
72 sum[p] -= 1ll*(mx[p]-t)*cnt[p];
73 mx[p] = add[p] = t;
74 return ;
75 }
76 int mid = pl+pr >> 1;
77 push_down(p);
78 if(L <= mid) update(L , R , ls(p) , pl , mid , t);
79 if(R > mid) update(L , R , rs(p) , mid+1 , pr , t);
80 push_up(p);
81 }
82 int query_max(int L , int R , int p , int pl , int pr)
83 {
84 if(L <= pl && pr <= R) return mx[p];
85 int mid = pl+pr >> 1;
86 int ans = 0;
87 push_down(p);
88 if(L <= mid) ans = max(ans , query_max(L , R , ls(p) , pl , mid));
89 if(R > mid) ans = max(ans , query_max(L , R , rs(p) , mid+1 , pr));
90 return ans;
91 }
92 ll query_sum(int L , int R , int p , int pl , int pr)
93 {
94 if(L <= pl && pr <= R) return sum[p];
95 int mid = pl+pr >> 1;
96 ll ans = 0;
97 push_down(p);
98 if(L <= mid) ans += query_sum(L , R , ls(p) , pl , mid);
99 if(R > mid) ans += query_sum(L , R , rs(p) , mid+1 , pr);
100 return ans;
101 }
102 int main()
103 {
104 int t;
105 scanf("%d",&t);
106 while(t--)
107 {
108 scanf("%d%d",&n,&m);
109 for(int i = 1; i <= n; i++)
110 scanf("%d",&a[i]);
111 build(1,1,n);
112 for(int i = 1;i <= m; i++)
113 {
114 int opt , L , R , k;
115 scanf("%d",&opt);
116 if(opt == 0)
117 {
118 scanf("%d%d%d",&L,&R,&k);
119 if(L > R) swap(L , R);
120 update(L , R , 1 , 1 , n , k);
121 }
122 else if(opt == 1)
123 {
124 scanf("%d%d",&L,&R);
125 if(L > R) swap(L , R);
126 printf("%d\n",query_max(L,R,1,1,n));
127 }
128 else if(opt == 2)
129 {
130 scanf("%d%d",&L,&R);
131 if(L > R) swap(L , R);
132 printf("%lld\n",query_sum(L,R,1,1,n));
133 }
134 }
135 }
136 return 0;
137 }
؏؏☝ᖗ乛◡乛ᖘ☝؏؏下次再见
标签：pr,rs,--,线段,mid,int,ls,mx,模板 From： https://www.cnblogs.com/smiling-weeping-zhr/p/17570890.html