自定义博客皮肤VIP专享

*博客头图：

点击选择上传的图片

格式为PNG、JPG，宽度*高度大于1920*100像素，不超过2MB，主视觉建议放在右侧，请参照线上博客头图

请上传大于1920*100像素的图片！

博客底图：

点击选择上传的图片

图片格式为PNG、JPG，不超过1MB，可上下左右平铺至整个背景

栏目图：

点击选择上传的图片

图片格式为PNG、JPG，图片宽度*高度为300*38像素，不超过0.5MB

主标题颜色：

RGB颜色，例如：#AFAFAF

Hover：

RGB颜色，例如：#AFAFAF

副标题颜色：

RGB颜色，例如：#AFAFAF

预览取消提交

自定义博客皮肤

-+

上一步保存

小衣同学的博客

算法竞赛相关内容

博客等级

码龄7年

992
原创

1679
点赞

2334
收藏

1419
粉丝

关注

私信

热门文章

分类专栏

最新评论

CCF-CSP认证 202303 500分题解
小小181: 只能反复观摩了
CCF-CSP认证 202303 500分题解
小小181: 我是艺术家，这就是艺术
CCF-CSP认证 202303 500分题解
小小181: 邢璐楠
CCF-CSP认证 202303 500分题解
小小181: 本来想着左右都讨论能不能合并，看衣老师没合并，我就
CCF-CSP认证 202303 500分题解
小小181: #include<iostream> #include<map> #include<vector> #include<cstring> #include<algorithm> #include<bits×dc++.h> #define fin for(ll i=1;i<=n;i++) #define fim for(ll i=1;i<=m;i++) #define fkn for(ll k=1;k<=n;k++) #define fjn for(ll j=1;j<=n;j++) #define fjm for(ll j=1;j<=m;j++) #define lowbit(x) ((x)&-(x)) #define r0 return 0 #define r1 return 1 #define ct continue #define sz(x) (int)x.size() #define rt return #define lsi t[i<<1] #define rsi t[i<<1|1] #define ar(x) array<ll,(x)> #define re(x,y,z) for(ll x=y;x<=z;x++) #define dl deque<ll> using namespace std; typedef long long int ll; typedef pair<ll,ll> pll; typedef vector<ll> vll; typedef vector<string> vs; const ll ma=5e6; ll b,c,d,e,n,m; //__builtin_popcount(i) ll i,j,k; vll g[ma]; map<array<ll,2>,ll> mp; map<ll,vll> ji; struct T{ ll l,r,ls,rs,num,lz; }t[(ll)5e7+5];ll cnt=1; struct Shu{ ll num; struct J { ll l,r; ll mx,mi; J (){ mx=-ma; mi=ma; } }t[ma]; Shu(){ } void init(ll l,ll r,ll u){ t[u].l=l,t[u].r=r; if(t[u].l==t[u].r){ rt; } ll m=l+r>>1; init(l,m,u<<1); init(m+1,r,u<<1|1); } void ud(ll u){ t[u].mx=max(t[u<<1].mx,t[u<<1|1].mx); t[u].mi=min(t[u<<1].mi,t[u<<1|1].mi); } void dan(ll x,ll u,ll da,ll xiao){ if(t[u].l==t[u].r){ t[u].mx=da; t[u].mi=xiao; rt; } ll m=t[u].l+t[u].r>>1; if(x<=m){ dan(x,u<<1,da,xiao); } else { dan(x,u<<1|1,da,xiao); } ud(u); } #define tul t[u].l #define tur t[u].r #define tu t[u] void xudan(ll x,ll u,ll dao){ if(t[u].l==t[u].r){ t[u].mx=max(t[u].mx,dao); t[u].mn=min(t[u].mi,dao); rt; } ll m=t[u].l+tur>>1; if(x<=m){ xudan(x,u<<1,dao); } else{ xudan(x,u<<1|1,dao); } ud(u); } ll zhenyuan(ll l,ll r,ll u,ll &da,ll &xiao){ if(l<=t[u].l&&t[u].r<=r){ da=max(da,t[u].mx); xiao=min(xiao,t[u].mi); r0; } ll m=t[u].l+t[u].r>>1; if(m>=l){ zhenyuan(l,r,u<<1,da,xiao); } if(m<r){ zhenyuan(l,r,u<<1|1,da,xiao); } } }shu[ma],sh,xu; ll ans=0; ll zuoxiao[ma],youda[ma]; ll zuoda[ma],youxiao[ma]; ll shuzu[ma]; map<array<ll,2>,ll> tmpl,tmpr; void ru(ll x,ll l,ll r){ while(x<=r){ shuzu[x]++; x+=lowbit(x); } } ll cha(ll rr,ll l,ll r){ ll s=0; while(x>=l){ s+=shuzu[x]; x-=lowbit(x); } return s; } void tree(ll l,ll r){ tmpl.clear();tmpr.clear(); ll m=l+r>>1; for(ll i=l;i<=r;i++){ shuzu[i]=0; } for(i=l;i<=m;i++){ tmpl[{i,zuoxiao[i]}]; } for(ll i=m+1;i<=r;i++){ tmpr[{youda[i],i}]; } tmpl[{ma,ma}]; auto i=tmpl.begin(); auto it=tmpr.begin(); while(it!=tmpr.end()){ array<ll,2> ta=(it->first),wo=(i->first); while(wo[0]<=ta[0]){ ru(wo[1],l,r); i++; ta=(it->first),wo=(i->first); } ans+=cha(ta[1],l,r); ta++; } } ll fen(ll l,ll r){ ll m=l+r>>1; ll aa=fen(l,m),bb=fen(m+1,r); for(ll i=l;i<=m;i++){ for(auto j:g[i]){ if(j<=r&&j>=m+1){ xu.xudan(i,1,j); xu.xudan(j,1,i); } else{ } } } for(ll i=l;i<=r;i++){ if(i<=m){ zuoxiao[i]=ma; zuoda[i]=-ma; } else { youda[i]=-ma; youxiao[i]=ma; } } for(ll i=l;i<=r;i++){ ll da=-ma,xiao=ma; sh.zhenyuan(i,i,1,da,xiao); if(i<=m){ ll big=-ma,small=ma; if(da==-ma){ xu.zhenyuan(i,i,1,big,small); zuoxiao[i]=small; zuoda[i]=big; } else{ xu.zhenyuan(i,da,1,big,small); zuoxiao[i]=small; zuoda[i]=big; } } else { ll big=-ma,small=ma; if(small==ma){ xu.zhenyuan(i,i,1,big,small); youda[i]=big; } else{ xu.zhenyuan(xiao,i,1,big,small); youda[i]=big; } youxiao[i]=small; } tree(l,r); for(i=l;i<=m;i++){ ll bi=-ma,sm=ma; if(zuoda[i]==-ma){ } else{ sh.zhenyuan(m+1,zuoda[i],1,bi,sm); zuoda[i]=max(zuoda[i],bi); bi=-ma,sm=ma; sh.zhenyuan(i,i,1,bi,sm); zuoda[i]=max(zuoda[i],); } } for(ll i=m+1;i<=r;i++){ ll bi=-ma,sm=ma; if(youxiao[i]==ma){ } else{ sh.zhenyuan(m+1,zuoda[i],1,bi,sm); zuoda[i]=max(zuoda[i],bi); bi=-ma,sm=ma; sh.zhenyuan(i,i,1,bi,sm); zuoda[i]=max(zuoda[i],bi); } } for(ll i=l;i<=m;i++){ xu.xudan(i,1,zuoda[i]); } for(ll i=m+1;i<=r;i++){ xu.xudan(i,1,youxiao[i]); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); sh.init();xu.init(); cin>>n>>m; fim { cin>>b>>c; if(mp[{b,c}]==0){ mp[{b,c}]=1; g[b].push_back(c); ji[b].push_back(c); } else{ } } fen(1,n); return 0; } 为什么在哪吒那里就是风火轮，太乙真人拿过来就变成🐖了

单调栈/单调队列

关注

文章平均质量分 75

具有单调性质的栈和队列

关注数：文章数：10 文章阅读量：5311 文章收藏量：6

作者: 小衣同学

No Saturday , no Sunday , no holiday .

展开