离散化离散化差分

数组开不了1e9但是好在坐标点会很分散那么相当于将点“挤到”1-n的位置一个位置映射了一个坐标点排序后坐标的相对位置并不发生改变离散化由此得来。#includebits/stdc.h #define int long long #define fi first #define se second #define endl \n using namespace std; typedef pairint,intpii; void solve(){ int n,m;cinnm; vectorpiip(n1); mapint,intmp; vectorinta,x(n10); for(int i1;in;i){ cinp[i].fip[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 i1;in;i){ auto [pos,val]p[i]; int idxlower_bound(a.begin(),a.end(),pos)-a.begin(); x[idx]val; } vectorintpre(n10); pre[0]x[0]; for(int i1;in5;i){ pre[i]pre[i-1]x[i]; } while(m--){ int l,r;cinlr; int Llower_bound(a.begin(),a.end(),l)-a.begin(); int Rupper_bound(a.begin(),a.end(),r)-a.begin(); R--; if(R0){ cout0endl; continue; } if(L0){ coutpre[R]endl; continue; } coutpre[R]-pre[L-1]endl; } } signed main(){ ios::sync_with_stdio(0);cin.tie(0); int T1;//cinT; while(T--){ solve(); } }2025icpc南昌邀请赛D:#includebits/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;cinnABC; vectorintlx(n10),ly(n10),lz(n10),rx(n10),ry(n10),rz(n10); vectorintx(2*n10),y(2*n10),z(2*n10),prex(2*n10),prey(2*n10),prez(2*n10); mapint,intmpx,mpy,mpz; vectorinta,b,c; for(int i1;in;i){ cinlx[i]ly[i]lz[i]; cinrx[i]ry[i]rz[i]; int mnxmin(lx[i],rx[i]),mxxmax(lx[i],rx[i]); int mnymin(ly[i],ry[i]),mxymax(ly[i],ry[i]); int mnzmin(lz[i],rz[i]),mxzmax(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 i1;in;i){ int Lupper_bound(a.begin(),a.end(),lx[i])-a.begin(); int Rupper_bound(a.begin(),a.end(),rx[i])-a.begin(); x[L],x[R]--; } for(int i1;in;i){ int Lupper_bound(b.begin(),b.end(),ly[i])-b.begin(); int Rupper_bound(b.begin(),b.end(),ry[i])-b.begin(); y[L],y[R]--; } for(int i1;in;i){ int Lupper_bound(c.begin(),c.end(),lz[i])-c.begin(); int Rupper_bound(c.begin(),c.end(),rz[i])-c.begin(); z[L],z[R]--; } int ans0; prex[0]x[0],prey[0]y[0],prey[0]y[0]; ansmax(ans,prex[0]); ansmax(ans,prey[0]); ansmax(ans,prez[0]); for(int i1;in*2;i){ prex[i]prex[i-1]x[i]; prey[i]prey[i-1]y[i]; prez[i]prez[i-1]z[i]; ansmax(ans,prex[i]); ansmax(ans,prey[i]); ansmax(ans,prez[i]); } coutans; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); int T1;//cinT; while(T--){ solve(); } }