This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/static_range_inversions_query #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../io/single.cpp" #include "../../vector/compress.cpp" #include "../../algorithm/mo.cpp" #include "../../datastructure/binaryindexedtree.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,q; cin>>n>>q; auto as=read(n); auto dc=dict(compress(as)); vector<int> cs(n); for(int i=0;i<n;i++) cs[i]=dc[as[i]]; using ll = long long; ll res=0; vector<ll> ans(q); BIT<int> bit(n); auto expandL=[&](int i){bit.add(cs[i],+1);res+=bit.query(0,cs[i]);}; auto expandR=[&](int i){bit.add(cs[i],+1);res+=bit.query(cs[i]+1,n);}; auto shrinkL=[&](int i){bit.add(cs[i],-1);res-=bit.query(0,cs[i]);}; auto shrinkR=[&](int i){bit.add(cs[i],-1);res-=bit.query(cs[i]+1,n);}; Mo mo(n,400,expandL,expandR,shrinkL,shrinkR); for(int i=0;i<q;i++){ int l,r; cin>>l>>r; mo.add(l,r); } mo.build(); for(int i=0;i<q;i++){ int k=mo.process(); ans[k]=res; } for(auto a:ans) cout<<a<<'\n'; return 0; }
#line 1 "test/yosupo/static_range_inversions_query.test.cpp" // verification-helper: PROBLEM https://judge.yosupo.jp/problem/static_range_inversions_query #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "io/single.cpp" #line 3 "io/single.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T=int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "vector/compress.cpp" #line 3 "vector/compress.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename V> V compress(V vs){ sort(vs.begin(),vs.end()); vs.erase(unique(vs.begin(),vs.end()),vs.end()); return vs; } template<typename T> map<T, int> dict(const vector<T> &vs){ map<T, int> res; for(int i=0;i<(int)vs.size();i++) res[vs[i]]=i; return res; } map<char, int> dict(const string &s){ return dict(vector<char>(s.begin(),s.end())); } template<typename T> vector<T> compressed(vector<T> vs){ auto dc=dict(compress(vs)); for(auto &v:vs) v=dc[v]; return vs; } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 1 "algorithm/mo.cpp" #line 3 "algorithm/mo.cpp" using namespace std; #endif //BEGIN CUT HERE struct Mo{ using F = function<void(int)>; vector<int> ls,rs,ord; int n,width,nl,nr,ptr; F expandL,expandR; F shrinkL,shrinkR; Mo(int n,int width,F expandL,F expandR,F shrinkL,F shrinkR): n(n),width(width),nl(0),nr(0),ptr(0), expandL(expandL),expandR(expandR), shrinkL(shrinkL),shrinkR(shrinkR){} Mo(int n,int width,F expand,F shrink): Mo(n,width,expand,expand,shrink,shrink){} void add(int l,int r){ ls.emplace_back(l); rs.emplace_back(r); } void build(){ ord.resize(ls.size()); iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(), [&](int a,int b){ if(ls[a]/width!=ls[b]/width) return ls[a]<ls[b]; if(rs[a]==rs[b]) return ls[a]<ls[b]; return bool((rs[a]<rs[b])^((ls[a]/width)&1)); }); } int process(){ if(ptr==(int)ord.size()) return -1; const int idx=ord[ptr++]; while(nl>ls[idx]) expandL(--nl); while(nr<rs[idx]) expandR(nr++); while(nl<ls[idx]) shrinkL(nl++); while(nr>rs[idx]) shrinkR(--nr); return idx; } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "datastructure/binaryindexedtree.cpp" #line 3 "datastructure/binaryindexedtree.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T> class BIT{ private: // \sum_{j < i} v[j] T sum(int i){ T s(0); for(int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } public: int n; vector<T> bit; BIT(int n_):n(n_+1),bit(n_+2,0){} // v[i] += a void add(int i,T a){ for(int x=++i;x<=n;x+=(x&-x)) bit[x]+=a; } // \sum_{l <= i < r} v[i] T query(int l,int r){return sum(r)-sum(l);} // min({x | sum(x) >= w}) int lower_bound(const T w){ if(w<=0) return 0; T r=w; int x=0,p=1; while(p<n) p<<=1; for(int k=p;k>0;k>>=1){ if(x+k<=n and bit[x+k]<r){ r-=bit[x+k]; x+=k; } } x++; assert(sum(x-1)<w and sum(x)>=w); return x; } // min({x | sum(x) > w}) int upper_bound(T w){return lower_bound(w+1);} }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 11 "test/yosupo/static_range_inversions_query.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,q; cin>>n>>q; auto as=read(n); auto dc=dict(compress(as)); vector<int> cs(n); for(int i=0;i<n;i++) cs[i]=dc[as[i]]; using ll = long long; ll res=0; vector<ll> ans(q); BIT<int> bit(n); auto expandL=[&](int i){bit.add(cs[i],+1);res+=bit.query(0,cs[i]);}; auto expandR=[&](int i){bit.add(cs[i],+1);res+=bit.query(cs[i]+1,n);}; auto shrinkL=[&](int i){bit.add(cs[i],-1);res-=bit.query(0,cs[i]);}; auto shrinkR=[&](int i){bit.add(cs[i],-1);res-=bit.query(cs[i]+1,n);}; Mo mo(n,400,expandL,expandR,shrinkL,shrinkR); for(int i=0;i<q;i++){ int l,r; cin>>l>>r; mo.add(l,r); } mo.build(); for(int i=0;i<q;i++){ int k=mo.process(); ans[k]=res; } for(auto a:ans) cout<<a<<'\n'; return 0; }