离散化离散化差分
数组开不了1e9，但是好在坐标点会很分散，那么相当于将点“挤到”1-n的位置，一个位置映射了一个坐标点，排序后，坐标的相对位置并不发生改变，离散化由此得来。
#include<bits/stdc++.h> #define int long long #define fi first #define se second #define endl '\n' using namespace std; typedef pair<int,int>pii; void solve(){ int n,m;cin>>n>>m; vector<pii>p(n+1); map<int,int>mp; vector<int>a,x(n+10); for(int i=1;i<=n;i++){ cin>>p[i].fi>>p[i].se; if(mp[p[i].fi]==0){ a.push_back(p[i].fi); mp[p[i].fi]++; } } sort(a.begin(),a.end()); for(int i=1;i<=n;i++){ auto [pos,val]=p[i]; int idx=lower_bound(a.begin(),a.end(),pos)-a.begin(); x[idx]+=val; } vector<int>pre(n+10); pre[0]=x[0]; for(int i=1;i<=n+5;i++){ pre[i]=pre[i-1]+x[i]; } while(m--){ int l,r;cin>>l>>r; int L=lower_bound(a.begin(),a.end(),l)-a.begin(); int R=upper_bound(a.begin(),a.end(),r)-a.begin(); R--; if(R<0){ cout<<0<<endl; continue; } if(L==0){ cout<<pre[R]<<endl; continue; } cout<<pre[R]-pre[L-1]<<endl; } } signed main(){ ios::sync_with_stdio(0);cin.tie(0); int T=1;//cin>>T; while(T--){ solve(); } }2025icpc南昌邀请赛D:
#include<bits/stdc++.h> #define int long long #define fi first #define se second #define endl '\n' using namespace std; void solve(){ int n,A,B,C;cin>>n>>A>>B>>C; vector<int>lx(n+10),ly(n+10),lz(n+10),rx(n+10),ry(n+10),rz(n+10); vector<int>x(2*n+10),y(2*n+10),z(2*n+10),prex(2*n+10),prey(2*n+10),prez(2*n+10); map<int,int>mpx,mpy,mpz; vector<int>a,b,c; for(int i=1;i<=n;i++){ cin>>lx[i]>>ly[i]>>lz[i]; cin>>rx[i]>>ry[i]>>rz[i]; int mnx=min(lx[i],rx[i]),mxx=max(lx[i],rx[i]); int mny=min(ly[i],ry[i]),mxy=max(ly[i],ry[i]); int mnz=min(lz[i],rz[i]),mxz=max(lz[i],rz[i]); lx[i]=mnx,rx[i]=mxx; ly[i]=mny,ry[i]=mxy; lz[i]=mnz,rz[i]=mxz; rx[i]++,ry[i]++,rz[i]++; if(mpx[lx[i]]==0) a.push_back(lx[i]),mpx[lx[i]]++; if(mpx[rx[i]]==0) a.push_back(rx[i]),mpx[rx[i]]++; if(mpy[ly[i]]==0) b.push_back(ly[i]),mpy[ly[i]]++; if(mpy[ry[i]]==0) b.push_back(ry[i]),mpy[ry[i]]++; if(mpz[lz[i]]==0) c.push_back(lz[i]),mpz[lz[i]]++; if(mpz[rz[i]]==0) c.push_back(rz[i]),mpz[rz[i]]++; } sort(a.begin(),a.end()),sort(b.begin(),b.end()),sort(c.begin(),c.end()); for(int i=1;i<=n;i++){ int L=upper_bound(a.begin(),a.end(),lx[i])-a.begin(); int R=upper_bound(a.begin(),a.end(),rx[i])-a.begin(); x[L]++,x[R]--; } for(int i=1;i<=n;i++){ int L=upper_bound(b.begin(),b.end(),ly[i])-b.begin(); int R=upper_bound(b.begin(),b.end(),ry[i])-b.begin(); y[L]++,y[R]--; } for(int i=1;i<=n;i++){ int L=upper_bound(c.begin(),c.end(),lz[i])-c.begin(); int R=upper_bound(c.begin(),c.end(),rz[i])-c.begin(); z[L]++,z[R]--; } int ans=0; prex[0]=x[0],prey[0]=y[0],prey[0]=y[0]; ans=max(ans,prex[0]); ans=max(ans,prey[0]); ans=max(ans,prez[0]); for(int i=1;i<=n*2;i++){ prex[i]=prex[i-1]+x[i]; prey[i]=prey[i-1]+y[i]; prez[i]=prez[i-1]+z[i]; ans=max(ans,prex[i]); ans=max(ans,prey[i]); ans=max(ans,prez[i]); } cout<<ans; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); int T=1;//cin>>T; while(T--){ solve(); } }