#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define Mp make_pair
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input19.txt" , "r" , stdin) ;
const int N = 1e5+23;
int Mn[4*N], Mx[4*N], lpz[4*N];
ll sum[4*N];
int c[N];
int n, k, q;
void build(int l=1, int r=n+1, int ind=0){
lpz[ind]=-1;
if(r-l==1){
Mx[ind]=sum[ind]=c[l];
return;
}
int mid=(r+l)>>1;
build(l, mid, 2*ind+1); build(mid, r, 2*ind+2);
Mx[ind]=max(Mx[2*ind+1], Mx[2*ind+2]); sum[ind]=sum[2*ind+1]+sum[2*ind+2];
}
void upd(int lx, int rx, ll x, int l=1, int r=n+1, int ind=0){
if(lx>=r || rx<=l || (!Mx[ind] && x==k)) return;
if(r-l==1){
if(x==k) sum[ind]=Mx[ind]=sum[ind]/k;
else sum[ind]=Mx[ind]=-x;
return;
}
int mid=(r+l)>>1;
upd(lx, rx, x, l, mid, 2*ind+1); upd(lx, rx, x, mid, r, 2*ind+2);
Mx[ind]=max(Mx[2*ind+1], Mx[2*ind+2]); sum[ind]=sum[2*ind+1]+sum[2*ind+2];
}
ll get(int lx, int rx, int l=1, int r=n+1, int ind=0){
if(lx>=r || rx<=l) return 0;
if(lx<=l && rx>=r) return sum[ind];
int mid=(r+l)>>1;
return get(lx, rx, l, mid, 2*ind+1)+get(lx, rx, mid, r, 2*ind+2);
}
int main()
{
fast_io
cin>>n>>q>>k;
for (int i=1; i<=n; i++) cin>>c[i];
build();
while(q--){
int t; cin>>t;
if(t==1){
int i, x; cin>>i>>x;
upd(i, i+1, -x);
}
else if(t==2){
int l, r; cin>>l>>r; r++;
if(k!=1) upd(l, r, k);
}
else{
int l, r; cin>>l>>r; r++;
cout<<get(l, r)<<endl;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |