题目链接
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 #define inf 0x7fffffff
5 #define faster ios::sync_with_stdio(0);cin.tie(0)
6
7 inline ll read()
8 {
9 int x=0,f=1;char ch=getchar();
10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
12 return x*f;
13 }
14
15 /********************************************************************/
16
17 const int maxn = 50000+7;
18 int n, m;
19 ll a[maxn], b[maxn];
20 int num, block;
21 ll minn[maxn], belong[maxn];
22 ll sum[maxn];
23
24 void makeblock(){
25 block = sqrt(n);
26 if(n%block) num = n/block+1;
27 else num = n/block;
28 for(int i = 1;i <= n;i++){
29 belong[i] = (i-1)/block + 1;
30 b[i] = a[i];
31 }
32 for(int i = 1;i <= num;i++){
33 ll l = (i-1)*block+1, r = min(i*block, n);
34 for(int j = l;j <= r;j++){
35 b[j] = a[j];
36 }
37 sort(b+l, b+r+1);
38 minn[i] = b[l];
39 sum[i] = 0;
40 for(int j = l;j <= r;j++){
41 if(b[j] == minn[i])
42 sum[i]++;
43 else break;
44 }
45 }
46 return;
47 }
48
49
50 //单点更新
51 void update(int x, int v){
52 a[x] = v;
53 int pos = belong[x];
54 ll l = (pos - 1)*block + 1;
55 ll r = (pos*block, n);
56 for(ll i = l;i <= r;i++)
57 b[i] = a[i];
58 sort(b+l, b+r+1);
59 minn[pos] = b[l];
60 sum[pos] = 0;
61 for(int i = l;i <= r;i++){
62 if(b[i] == minn[pos])
63 sum[pos]++;
64 else break;
65 }
66 return;
67 }
68
69 //区间查询
70 int ask(int l, int r){
71 ll ans = inf;
72 if(belong[l] == belong[r]){
73 for(int i = l;i <= r;i++){
74 ans = min(ans, a[i]);
75 }
76 }
77 else {
78 for(int i = l;i <= belong[l]*block;i++){
79 ans = min(ans, a[i]);
80 }
81 for(int i = belong[r-1]*block+1;i <= r;i++){
82 ans = min(ans, a[i]);
83 }
84 }
85 for(int i = belong[l]+1;i < belong[r];i++){
86 ans = min(ans, minn[i]);
87 }
88 return ans;
89 }
90
91 int ask1(int l, int r, int len){
92 ll ans = 0;
93 if(belong[l] == belong[r]){
94 for(int i = l;i <= r;i++){
95 if(a[i] == len)
96 ans++;
97 }
98 }
99 else {
100 for(int i = l;i <= belong[l]*block;i++){
101 if(a[i] == len)
102 ans++;
103 }
104 for(int i = belong[r-1]*block+1;i <= r;i++){
105 if(a[i] == len)
106 ans++;
107 }
108 }
109 for(int i = belong[l]+1;i < belong[r];i++){
110 if(minn[i] == len){
111 ans += sum[i];
112 }
113 }
114 return ans;
115 }
116
117 int Find(int pos, int len){
118 if(minn[pos] < len)
119 return 0;
120 ll l = (pos - 1)*block+1;
121 ll r = min(pos*block, n);
122 int ans = 0;
123 for(int i = l;i <= r;i++){
124 if(b[i] <= len)
125 ans++;
126 else break;
127 }
128 return ans;
129 }
130
131 int deal(int l, int r, int len){
132 int ans = 0;
133 if(belong[l] == belong[r]){
134 for(int i = l;i <= r;i++){
135 if(a[i] <= len) ans++;
136 }
137 }
138 else{
139 for(int i = l;i <= belong[l]*block;i++){
140 if(a[i] <= len) ans++;
141 }
142 for(int i = belong[r-1]*block+1;i <= r;i++){
143 if(a[i] <= len) ans++;
144 }
145 }
146 for(int i = belong[l]+1;i < belong[r];i++){
147 ans += Find(i, len);
148 }
149 return ans;
150 }
151
152 int main(){
153 n = read(); m = read();
154 for(int i = 1;i <= n;i++){
155 a[i] = read();
156 }
157 makeblock();
158 while(m--){
159 int op, x, y, v;
160 op = read();
161 if(op == 1){
162 x = read(); v = read();
163 update(x, v);
164 }
165 else if(op == 2){
166 x = read(); y = read();
167 int tmp = ask(x, y);
168 int tmp1 = ask1(x, y, tmp);
169 printf("%d %d
", tmp, tmp1);
170 }
171 else if(op == 3){
172 x = read(); y = read(); v = read();
173 int tmp = deal(x, y, v);
174 printf("%d
", tmp);
175 }
176 }
177 return 0;
178 }