2 条题解
-
0
题解
#include <bits/stdc++.h> //by wangtairan114 using namespace std; #define INF 0x3f3f3f3f3f3f3f3fll #define IINF 0x3f3f3f3f #define DINF 10000000 #define ll long long #define sc scanf #define pr printf #define v1 first #define v2 second #define lowbit(x) ((x)&(-x)) const int N=300005; #define lson k*2,l,mid #define rson k*2+1,mid+1,r #define mid ((l+r)>>1) struct node{ ll mn;//最小值 ll smn;//次小值 ll cntmn;//最小值个数 }p[N<<2]; ll a[N]; ll tgst[N<<2],tgad[N<<2],tgmx[N<<2]; node merge(node x,node y){ node ans; if(x.mn>y.mn)swap(x,y);//比较最小值 ans.mn=x.mn; ans.cntmn=x.cntmn; if(x.mn==y.mn){ ans.cntmn+=y.cntmn;//如果最小值相同将个数累加 ans.smn=min(x.smn,y.smn);//更新次小值 } else ans.smn=min(x.smn,y.mn); return ans; } void push_up(int k){p[k]=merge(p[k*2],p[k*2+1]);} void push_st(int k,int l,int r,ll va){ p[k].mn=va; p[k].smn=INF; p[k].cntmn=r-l+1; tgst[k]=va; tgad[k]=0; tgmx[k]=-INF; } void push_ad(int k,int l,int r,ll va){ p[k].mn+=va; if(p[k].smn!=INF)p[k].smn+=va; tgad[k]+=va; if(tgmx[k]!=-INF)tgmx[k]+=va; } void push_mx(int k,int l,int r,ll va){ if(p[k].mn>=va)return; p[k].mn=va; tgmx[k]=va; } void push_down(int k,int l,int r){//下传懒标记 if(tgst[k]!=-INF){push_st(lson,tgst[k]);push_st(rson,tgst[k]);}//先赋值 if(tgad[k]){push_ad(lson,tgad[k]);push_ad(rson,tgad[k]);}//下传加法标记 if(tgmx[k]!=-INF){push_mx(lson,tgmx[k]);push_mx(rson,tgmx[k]);}//下传max标记 tgst[k]=-INF; tgad[k]=0; tgmx[k]=-INF; } void build(int k,int l,int r){ tgmx[k]=-INF; tgst[k]=-INF; tgad[k]=0; if(l==r){ p[k].mn=a[l]; p[k].smn=INF;//不存在次小值时赋值为inf p[k].cntmn=1; return; } build(lson); build(rson); push_up(k); } void modify_st(int k,int l,int r,const int lbor,const int rbor,ll va){//区间赋值 if(lbor<=l&&r<=rbor){push_st(k,l,r,va);return;} push_down(k,l,r); if(mid>=lbor)modify_st(lson,lbor,rbor,va); if(mid<rbor)modify_st(rson,lbor,rbor,va); push_up(k); } void modify_ad(int k,int l,int r,const int lbor,const int rbor,ll va){//区间加 if(lbor<=l&&r<=rbor){push_ad(k,l,r,va);return;} push_down(k,l,r); if(mid>=lbor)modify_ad(lson,lbor,rbor,va); if(mid<rbor)modify_ad(rson,lbor,rbor,va); push_up(k); } void modify_mx(int k,int l,int r,const int lbor,const int rbor,ll va){//区间取max if(p[k].mn>=va)return;//如果当前区间最小值大于修改的值，直接返回 if(lbor<=l&&r<=rbor&&p[k].smn>va){push_mx(k,l,r,va);return;}//如果区间合法且小于次小值，进行修改 push_down(k,l,r);//否则继续下传 if(mid>=lbor)modify_mx(lson,lbor,rbor,va); if(mid<rbor)modify_mx(rson,lbor,rbor,va); push_up(k); } ll query(int k,int l,int r,const int lbor,const int rbor){ if(lbor<=l&&r<=rbor){ if(p[k].mn==0)return p[k].cntmn; return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:10:14
#include <bits/stdc++.h> //by wangtairan114 using namespace std; #define INF 0x3f3f3f3f3f3f3f3fll #define IINF 0x3f3f3f3f #define DINF 10000000 #define ll long long #define sc scanf #define pr printf #define v1 first #define v2 second #define lowbit(x) ((x)&(-x)) const int N=300005; #define lson k*2,l,mid #define rson k*2+1,mid+1,r #define mid ((l+r)>>1) struct node{ ll mn;//最小值 ll smn;//次小值 ll cntmn;//最小值个数 }p[N<<2]; ll a[N]; ll tgst[N<<2],tgad[N<<2],tgmx[N<<2]; node merge(node x,node y){ node ans; if(x.mn>y.mn)swap(x,y);//比较最小值 ans.mn=x.mn; ans.cntmn=x.cntmn; if(x.mn==y.mn){ ans.cntmn+=y.cntmn;//如果最小值相同将个数累加 ans.smn=min(x.smn,y.smn);//更新次小值 } else ans.smn=min(x.smn,y.mn); return ans; } void push_up(int k){p[k]=merge(p[k*2],p[k*2+1]);} void push_st(int k,int l,int r,ll va){ p[k].mn=va; p[k].smn=INF; p[k].cntmn=r-l+1; tgst[k]=va; tgad[k]=0; tgmx[k]=-INF; } void push_ad(int k,int l,int r,ll va){ p[k].mn+=va; if(p[k].smn!=INF)p[k].smn+=va; tgad[k]+=va; if(tgmx[k]!=-INF)tgmx[k]+=va; } void push_mx(int k,int l,int r,ll va){ if(p[k].mn>=va)return; p[k].mn=va; tgmx[k]=va; } void push_down(int k,int l,int r){//下传懒标记 if(tgst[k]!=-INF){push_st(lson,tgst[k]);push_st(rson,tgst[k]);}//先赋值 if(tgad[k]){push_ad(lson,tgad[k]);push_ad(rson,tgad[k]);}//下传加法标记 if(tgmx[k]!=-INF){push_mx(lson,tgmx[k]);push_mx(rson,tgmx[k]);}//下传max标记 tgst[k]=-INF; tgad[k]=0; tgmx[k]=-INF; } void build(int k,int l,int r){ tgmx[k]=-INF; tgst[k]=-INF; tgad[k]=0; if(l==r){ p[k].mn=a[l]; p[k].smn=INF;//不存在次小值时赋值为inf p[k].cntmn=1; return; } build(lson); build(rson); push_up(k); } void modify_st(int k,int l,int r,const int lbor,const int rbor,ll va){//区间赋值 if(lbor<=l&&r<=rbor){push_st(k,l,r,va);return;} push_down(k,l,r); if(mid>=lbor)modify_st(lson,lbor,rbor,va); if(mid<rbor)modify_st(rson,lbor,rbor,va); push_up(k); } void modify_ad(int k,int l,int r,const int lbor,const int rbor,ll va){//区间加 if(lbor<=l&&r<=rbor){push_ad(k,l,r,va);return;} push_down(k,l,r); if(mid>=lbor)modify_ad(lson,lbor,rbor,va); if(mid<rbor)modify_ad(rson,lbor,rbor,va); push_up(k); } void modify_mx(int k,int l,int r,const int lbor,const int rbor,ll va){//区间取max if(p[k].mn>=va)return;//如果当前区间最小值大于修改的值，直接返回 if(lbor<=l&&r<=rbor&&p[k].smn>va){push_mx(k,l,r,va);return;}//如果区间合法且小于次小值，进行修改 push_down(k,l,r);//否则继续下传 if(mid>=lbor)modify_mx(lson,lbor,rbor,va); if(mid<rbor)modify_mx(rson,lbor,rbor,va); push_up(k); } ll query(int k,int l,int r,const int lbor,const int rbor){ if(lbor<=l&&r<=rbor){ if(p[k].mn==0)return p[k].cntmn; return 0; } push_down(k,l,r); ll ans=0; if(mid>=lbor)ans+=query(lson,lbor,rbor); if(mid<rbor)ans+=query(rson,lbor,rbor); return ans; } int n,q; int main(){ sc("%d%d",&n,&q); for(int i=1; i <= n; i++) sc("%lld",&a[i]); build(1,1,n); while(q--){ int op; sc("%d",&op); if(op==1){ int l,r; ll va; sc("%d%d%lld",&l,&r,&va); modify_st(1,1,n,l,r,va); } else if(op==2){ int l,r; ll va; sc("%d%d%lld",&l,&r,&va); modify_ad(1,1,n,l,r,va); modify_mx(1,1,n,l,r,0); } else { int l,r; sc("%d%d",&l,&r); pr("%lld\n",query(1,1,n,l,r)); } } return 0; }
- 1
