#include using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const pair&p){ os< ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,pair&p){ is>>p.first>>p.second; return is; } template istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } template struct FractionalCascading{ vector> seg; vector> L,R; vector xs; int sz; // O(nlogn) FractionalCascading(vector> ps){ sort(begin(ps),end(ps)); if(ps.size()) xs.push_back(ps[0].first); for(auto &p:ps)if(xs.back()!=p.first)xs.push_back(p.first); xs.push_back(numeric_limits::max()); sz=1; while(sz<(int)xs.size()) sz<<=1; seg.resize(2*sz); L.resize(2*sz); R.resize(2*sz); int pos=0; for(auto &p:ps){ if(xs[pos]!=p.first) pos++; seg[pos+sz].push_back(p.second); } for(int k=sz-1;k>0;k--){ seg[k].resize(seg[2*k].size()+seg[2*k+1].size()); L[k].resize(seg[k].size()+1); R[k].resize(seg[k].size()+1); merge(begin(seg[2*k]),end(seg[2*k]),begin(seg[2*k+1]),end(seg[2*k+1]),begin(seg[k])); int li=0,ri=0; for(int i=0;i<(int)seg[k].size();i++){ L[k][i]=li,R[k][i]=ri; if(li<(int)seg[2*k].size() and seg[2*k][li]==seg[k][i]) li++; else ri++; } L[k][seg[k].size()]=(int)seg[2*k].size(); R[k][seg[k].size()]=(int)seg[2*k+1].size(); } } int sub(int a,int b,int lw,int hi,int k,int l,int r){ if(r<=a or b<=l) return 0; if(a<=l and r<=b) return hi-lw; return sub(a,b,L[k][lw],L[k][hi],2*k,l,(l+r)/2)+sub(a,b,R[k][lw],R[k][hi],2*k+1,(l+r)/2,r); } // [le,ri), [lw,hi) int count(Tx le,Tx ri,Ty lw,Ty hi){ int lwid=lower_bound(begin(seg[1]),end(seg[1]),lw)-begin(seg[1]); int hiid=lower_bound(begin(seg[1]),end(seg[1]),hi)-begin(seg[1]); int leid=lower_bound(begin(xs),end(xs),le)-begin(xs); int riid=lower_bound(begin(xs),end(xs),ri)-begin(xs); return sub(leid,riid,lwid,hiid,1,0,sz); } }; void solve(){ int n,q;cin>>n>>q; vectorc(n); cin>>c; vector> d; map pre; rep(i,n){ if(pre.count(c[i])) d.push_back({i,pre[c[i]]}); pre[c[i]]=i; } FractionalCascading seg(d); while(q--){ int l,r;cin>>l>>r;l--; int ans=r-l-seg.count(l,r,l,r); cout<>n; ll a[n],l[n],r[n]; rep(i,n) cin>>a[i]; rep(i,n) cin>>l[i]>>r[i]; vector> ps; rep(i,n) ps.push_back({i,a[i]+r[i]}); FractionalCascading seg(ps); ll ans=0; rep(i,n){ int idx=lower_bound(a,a+n,a[i]-l[i])-a; // [idx,i) // [a[i],INF) ans+=seg.count(idx,i,a[i],LINF); } cout<