#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (100005)
#define MAXQ (100005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
static unsigned char str[2255522], *p=str;
const int MX = 131072;
struct SEG {
pii d[MX*2]; ll ds[MX*2];
void upd(int x, int r) {
for(d[x+MX] = {r, x}, x += MX, ds[x] = r, x /= 2; x; x /= 2) {
d[x] = max(d[x*2], d[x*2+1]); ds[x] = ds[x*2] + ds[x*2+1];
}
}
pii getmax(int s, int e) {
pii r = {0, 0}; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
if(s&1) upmax(r, d[s++]); if(~e&1) upmax(r, d[e--]);
} return r;
}
ll getsum(int s, int e) {
ll r = 0; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
if(s&1) r += ds[s++]; if(~e&1) r += ds[e--];
} return r;
}
};
SEG seg;
vector<pii> V;
int N, Q, K;
int main() {
fread(str, 1, 2255522, stdin);
rf(N) rf(Q) rf(K)
for(int i = 1, c; i <= N; i++) { rf(c) seg.upd(i, c); }
for(int type, s, e; Q--;) {
rf(type) rf(s) rf(e)
if(1 == type) seg.upd(s, e);
else if(2 == type) {
if(1 == K) continue;
for(pii r;;) {
r = seg.getmax(s, e);
if(!r.first) break;
V.pb(r); seg.upd(r.second, 0);
}
for(pii v : V) seg.upd(v.second, v.first/K);
clv(V);
}
else printf("%lld\n", seg.getsum(s, e));
}
return 0;
}
Compilation message
sterilizing.c:1:18: fatal error: cstdio: No such file or directory
#include <cstdio>
^
compilation terminated.
