P1531 I Hate It

it2022-05-05  77

https://www.luogu.org/problemnew/show/P1531

#include <iostream> #include <cstdio> #include <cmath> #define ll long long using namespace std; const int MAXN=800005; int n,m,u,v; char x; ll k,jl[MAXN]; struct cyq{ int l,r; ll num,tip; }a[MAXN]; void build(int p,int l,int r){ a[p].l=l;a[p].r=r; if(l==r) {a[p].num=jl[l];return;} int mid=(l+r)>>1; build(p*2,l,mid);build(p*2+1,mid+1,r); a[p].num=max(max(a[p*2].num,a[p*2+1].num),a[p].num); } void change(int p) { if(u==a[p].r && a[p].l==u){ a[p].num=max(a[p].num,k); return; } int mid = (a[p].l + a[p].r) / 2; if (u > mid) change(p * 2 + 1); else change(p * 2); a[p].num = max(a[p].num,k); } ll ask(int p) { if(u<=a[p].l && v>=a[p].r) return a[p].num; long long ans=0; int mid=(a[p].l+a[p].r)>>1; if(u<=mid) ans=max(ans,ask(p*2)); if(v>mid) ans=max(ans,ask(p*2+1)); return ans; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&jl[i]); build(1,1,n); while(m--){ cin>>x; if(x=='U') { scanf("%d%lld",&u,&k); if(jl[u]<k) change(1); } if(x=='Q') { scanf("%d%d",&u,&v); printf("%lld\n",ask(1)); } } return 0; }

最新回复(0)