This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using namespace std;
using ll=long long;
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
const int N=400010,MOD=1e9+7,M=1<<19;
const char en='\n';
const ll LLINF=1ll<<60;
int n,q,h[N],ti[N],a[N],b[N],seg[M*2+10];
void upd(int i,int x)
{
for (i+=M;i;i/=2) seg[i]+=x;
}
int ge(int l,int r,int lo=0,int hi=M,int i=1)
{
if (lo>=l && hi<=r) return seg[i];
if (lo>=r || hi<=l) return 0;
int mid=(lo+hi)/2;
return ge(l,r,lo,mid,i*2)+ge(l,r,mid,hi,i*2+1);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>q;
set<int> s;
for (int i=0;i<n;++i) cin>>h[i],s.insert(h[i]);
for (int i=0;i<q;++i)
{
cin>>ti[i];
if (ti[i]==1)
{
cin>>a[i];
s.insert(a[i]);
}
else
{
cin>>a[i]>>b[i];
s.insert(b[i]);
}
}
vi v(all(s));
for (int i=0;i<n;++i) h[i]=lower_bound(all(v),h[i])-v.begin();
for (int i=0;i<q;++i)
{
if (ti[i]==1) a[i]=lower_bound(all(v),a[i])-v.begin();
else b[i]=lower_bound(all(v),b[i])-v.begin();
}
for (int i=0;i<n;++i)
{
upd(h[i],1);
if (i) upd(min(h[i],h[i-1]),-1);
}
for (int i=0;i<q;++i)
{
if (ti[i]==1)
{
cout<<ge(a[i],M)<<en;
}
else
{
--a[i];
upd(h[a[i]],-1);
if (a[i]) upd(min(h[a[i]],h[a[i]-1]),1);
if (a[i]<n-1) upd(min(h[a[i]],h[a[i]+1]),1);
h[a[i]]=b[i];
upd(h[a[i]],1);
if (a[i]) upd(min(h[a[i]],h[a[i]-1]),-1);
if (a[i]<n-1) upd(min(h[a[i]],h[a[i]+1]),-1);
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |