小小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)() #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){ ();(); 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=(); auto it=(); while(it!=()){ 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){ (i,1,j); (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; (i,i,1,da,xiao); if(i<=m){ ll big=-ma,small=ma; if(da==-ma){ (i,i,1,big,small); zuoxiao[i]=small; zuoda[i]=big; } else{ (i,da,1,big,small); zuoxiao[i]=small; zuoda[i]=big; } } else { ll big=-ma,small=ma; if(small==ma){ (i,i,1,big,small); youda[i]=big; } else{ (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{ (m+1,zuoda[i],1,bi,sm); zuoda[i]=max(zuoda[i],bi); bi=-ma,sm=ma; (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{ (m+1,zuoda[i],1,bi,sm); zuoda[i]=max(zuoda[i],bi); bi=-ma,sm=ma; (i,i,1,bi,sm); zuoda[i]=max(zuoda[i],bi); } } for(ll i=l;i<=m;i++){ (i,1,zuoda[i]); } for(ll i=m+1;i<=r;i++){ (i,1,youxiao[i]); } } } int main() { ios_base::sync_with_stdio(false); (0); ();(); 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; } 为什么在哪吒那里就是风火轮，太乙真人拿过来就变成????了
(转载)关于O2优化
CCF-CSP认证 202303 500分题解