分析
区间加，区间和，区间最小值，区间整除
跟区间开方的性质差不多，一次一次除下去，区间中的数会越来越接近
当区间中的数接近时，他们减少的数会相等，就转换成了区间减
代码
1 /*****************************
2 User:Mandy.H.Y
3 Language:c++
4 Problem:market
5 *****************************/
6 //
7 #include<bits/stdc++.h>
8 #define lson l,mid,k << 1
9 #define rson mid + 1,r,k << 1 | 1
10 #define Max(x,y) ((x) > (y) ? (x) : (y))
11 #define Min(x,y) ((x) < (y) ? (x) : (y))
12
13 using namespace std;
14
15 const int maxn = 1e5 + 5;
16
17 int n,q;
18 long long sum[maxn << 2];
19 int mi[maxn << 2],ma[maxn << 2],lazy[maxn << 2];
20 int L,R,C,D;
21
22 template<class T>inline void read(T &x){
23 x = 0;bool flag = 0;char ch = getchar();
24 while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
25 while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
26 if(flag) x = -x;
27 }
28
29 template<class T>void putch(const T x){
30 if(x > 9) putch(x / 10);
31 putchar(x % 10 | 48);
32 }
33
34 template<class T>void put(const T x){
35 if(x < 0) putchar('-'),putch(-x);
36 else putch(x);
37 }
38
39 void file(){
40 freopen("market.in","r",stdin);
41 freopen("market.out","w",stdout);
42 }
43
44 void pushup(int k){
45 int ls = k << 1;
46 int rs = k << 1 | 1;
47 sum[k] = sum[ls] + sum[rs];
48 mi[k] = Min(mi[ls],mi[rs]);
49 ma[k] = Max(ma[ls],ma[rs]);
50 }
51
52 void buildtree(int l,int r,int k){
53 if(l == r){
54 read(mi[k]);
55 sum[k] = ma[k] = mi[k];
56 return ;
57 }
58 int mid = (l + r) >> 1;
59 buildtree(lson);
60 buildtree(rson);
61 pushup(k);
62 }
63
64 void readdata(){
65 read(n);read(q);
66 buildtree(1,n,1);
67 }
68
69 void pushdown(int l,int r,int k){
70 if(!lazy[k]) return;
71 int ls = k << 1;
72 int rs = ls | 1;
73 int mid = (l + r) >> 1;
74 sum[ls] += (long long)lazy[k] * (mid - l + 1);
75 sum[rs] += (long long)lazy[k] * (r - mid);
76 mi[ls] += lazy[k];ma[ls] += lazy[k];
77 mi[rs] += lazy[k];ma[rs] += lazy[k];
78 lazy[ls] += lazy[k];
79 lazy[rs] += lazy[k];
80 lazy[k] = 0;
81 }
82
83 void add(int l,int r,int k){
84 if(L <= l && r <= R){
85 sum[k] += (long long)C * (r - l + 1);
86 mi[k] += C;
87 ma[k] += C;
88 lazy[k] += C;
89 return;
90 }
91 pushdown(l,r,k);
92 int mid = (l + r) >> 1;
93 if(L <= mid) add(lson);
94 if(R > mid) add(rson);
95 pushup(k);
96 }
97
98 void div(int l,int r,int k){//如果区间最大值与最小值的下降的值都一样，那么区间下降的值一样
99 if(L <= l && r <= R){
100 int tmp1 = ma[k] - (int)floor((double)ma[k]/(double)D);
101 int tmp2 = mi[k] - (int)floor((double)mi[k]/(double)D);
102 if(tmp1 == tmp2){
103 sum[k] -= (long long)tmp1 * (r - l + 1);
104 mi[k] -= tmp1;
105 ma[k] -= tmp1;
106 lazy[k] -= tmp1;
107 return;
108 }
109 }
110 pushdown(l,r,k);
111 int mid = (l + r) >> 1;
112 if(L <= mid) div(lson);
113 if(R > mid) div(rson);
114 pushup(k);
115 }
116
117 long long get_sum(int l,int r,int k){
118 if(L <= l && r <= R) return sum[k];
119 pushdown(l,r,k);
120 int mid = (l + r) >> 1;
121 long long ans = 0;
122 if(L <= mid) ans += get_sum(lson);
123 if(R > mid) ans += get_sum(rson);
124 pushup(k);
125 return ans;
126 }
127
128 int get_min(int l,int r,int k){
129 if(L <= l && r <= R) return mi[k];
130 pushdown(l,r,k);
131 int mid = (l + r) >> 1;
132 int ans1 = 2e9 + 5;
133 int ans2 = 2e9 + 5;
134 if(L <= mid) ans1 = get_min(lson);
135 if(R > mid) ans2 = get_min(rson);
136 pushup(k);
137 return Min(ans1,ans2);
138 }
139
140 void work(){
141 while(q --){
142 int opt;
143 read(opt);
144 switch(opt){
145 case 1:{
146 read(L);read(R);read(C);
147 L++,R++;//注意本题给出的标号从0开始
148 add(1,n,1);
149 break;
150 }
151 case 2:{
152 read(L);read(R);read(D);
153 L++,R++;
154 div(1,n,1);
155 break;
156 }
157 case 3:{
158 read(L);read(R);L++,R++;
159 int ans = get_min(1,n,1);
160 put(ans);puts("");
161 break;
162 }
163 case 4:{
164 read(L);read(R);
165 L++,R++;
166 long long ans = get_sum(1,n,1);
167 put(ans);puts("");
168 break;
169 }
170 }
171 }
172 }
173
174 int main(){
175 // file();
176 readdata();
177 work();
178 return 0;
179 }
View Code