結果
| 問題 | No.1270 Range Arrange Query |
| ユーザー |
 n_vip
|
| 提出日時 | 2020-10-23 23:42:35 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,549 ms / 7,000 ms |
| コード長 | 7,045 bytes |
| コンパイル時間 | 2,274 ms |
| コンパイル使用メモリ | 155,248 KB |
| 最終ジャッジ日時 | 2025-01-15 14:19:04 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 |
ソースコード
#include <string>#include <vector>#include<iostream>#include<cstdio>#include<cstdlib>#include<stack>#include<queue>#include<cmath>#include<algorithm>#include<functional>#include<list>#include<deque>#include<bitset>#include<set>#include<map>#include<unordered_map>#include<unordered_set>#include<cstring>#include<sstream>#include<complex>#include<iomanip>#include<numeric>#include<cassert>#include<random>#define X first#define Y second#define pb push_back#define rep(X,Y) for (int (X) = 0;(X) < (int)(Y);++(X))#define reps(X,S,Y) for (int (X) = (int)(S);(X) < (int)(Y);++(X))#define rrep(X,Y) for (int (X) = (int)(Y)-1;(X) >=0;--(X))#define rreps(X,S,Y) for (int (X) = (int)(Y)-1;(X) >= (int)(S);--(X))#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))#define peat(X,Y) for (;(X) < (Y);++(X))#define all(X) (X).begin(),(X).end()#define rall(X) (X).rbegin(),(X).rend()#define eb emplace_back#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())#define Endl endl#define NL <<"\n"#define cauto const autousing namespace std;using ll=long long;using pii=pair<int,int>;using pll=pair<ll,ll>;template<class T> using vv=vector<vector<T>>;template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}//#undef NUIP#ifdef NUIP#include "benri.h"#else#define out(args...)#endif#ifdef __cpp_init_capturestemplate<typename T>vector<T> table(int n, T v){ return vector<T>(n, v);}template <class... Args> auto table(int n, Args... args){auto val = table(args...); return vector<decltype(val)>(n, move(val));}#endiftemplate<class A,class B> pair<A,B> operator+(const pair<A,B> &p,const pair<A,B> &q){ return {p.X+q.X,p.Y+q.Y};}template<class A,class B,class C,class D> pair<A,B>& operator+=(pair<A,B> &p,const pair<C,D> &q){ p.X+=q.X; p.Y+=q.Y; return p;}template<class A,class B> pair<A,B> operator-(const pair<A,B> &p,const pair<A,B> &q){ return {p.X-q.X,p.Y-q.Y};}template<class A,class B,class C,class D> pair<A,B>& operator-=(pair<A,B> &p,const pair<C,D> &q){ p.X-=q.X; p.Y-=q.Y; return p;}template<class A,class B> istream& operator>>(istream &is, pair<A,B> &p){ is>>p.X>>p.Y; return is;}template<class T=ll> T read(){ T re; cin>>re; return move(re);}template<class T=ll> T read(const T &dec){ T re; cin>>re; return re-dec;}template<class T=ll> vector<T> readV(const int sz){ vector<T> re(sz); for(auto &x:re) x=read<T>(); return move(re);}template<class T=ll> vector<T> readV(const int sz, const T &dec){ vector<T> re(sz); for(auto &x:re) x=read<T>(dec); return move(re);}vv<int> readG(const int &n,const int &m){ vv<int> g(n); rep(_,m){ cauto a=read<int>(1),b=read<int>(1); g[a].pb(b); g[b].pb(a);} return move(g);}vv<int> readG(const int &n){ return readG(n,n-1);}const ll MOD=1e9+7; //998244353const int SQ=200;const int BK=21234/SQ+2;const int nn=21234;ll bit[nn+1];ll sum(int i){ ++i;ll s=0;while(i>0){s+=bit[i];i-=i&-i;}return s;}void add(int i,ll x){ ++i;while(i<=nn){bit[i]+=x;i+=i&-i;}}template<class T>struct MinMax{T mn,mx;MinMax(T mn,T mx):mn(mn),mx(mx){}MinMax(T v):mn(v),mx(v){}MinMax():mn(MOD),mx(-MOD){}MinMax operator+(const MinMax &seg){return MinMax(min(mn,seg.mn),max(mx,seg.mx));}static MinMax e;};template<class T> MinMax<T> MinMax<T>::e=MinMax();template<class T>ostream& operator<<(ostream &os, const MinMax<T> &seg){ return os<<"("<<seg.mn<<","<<seg.mx<<")";}template<class T>struct Add{T ad;Add(T ad=0):ad(ad){}void operator+=(const Add &lfun){ad+=lfun.ad;}bool operator==(const Add &lfun){ return ad==lfun.ad;}void eval(MinMax<T> &s,int l,int r){s.mn+=ad;s.mx+=ad;}static Add e;};template<class T> Add<T> Add<T>::e=Add();template<class T>ostream& operator<<(ostream &os, const Add<T> &lfun){ return os<<"("<<lfun.ad<<")";}template<class Seg, class Ope>struct LazySegTree{vector<Seg> segs;vector<Ope> opes;void lazy_eval(int k,int a,int b){if(opes[k]==Ope::e) return;opes[k].eval(segs[k],a,b);if(2*k+2<opes.size()){opes[2*k+1]+=opes[k];opes[2*k+2]+=opes[k];}opes[k]=Ope::e;}void upd_node(int k){segs[k]=segs[2*k+1]+segs[2*k+2];}void upd(int l,int r,Ope ope,int k,int a,int b){lazy_eval(k,a,b);if(b<=l || r<=a) return;if(l<=a && b<=r){opes[k]+=ope;lazy_eval(k,a,b);return;}int m=(a+b)/2;upd(l,r,ope,2*k+1,a,m);upd(l,r,ope,2*k+2,m,b);upd_node(k);}void upd(int l,int r,Ope ope){out(l,r,ope,1);upd(l,r,ope,0,0,segs.size()/2);}Seg query(int l,int r,int k,int a,int b){lazy_eval(k,a,b);if(b<=l || r<=a)return Seg::e;if(l<=a && b<=r){return segs[k];}int m=(a+b)/2;Seg vl=query(l,r,2*k+1,a,m);Seg vr=query(l,r,2*k+2,m,b);upd_node(k);return vl+vr;}LazySegTree(int n){int pw=1;while(pw<n) pw*=2;segs.resize(2*pw);opes.resize(2*pw);}template<class Int>LazySegTree(vector<Int> vs){int n=vs.size();int pw=1;while(pw<n) pw*=2;segs.resize(2*pw);opes.resize(2*pw);rep(i,n) segs[pw-1+i]=vs[i];rrep(i,pw-1) segs[i]=segs[i*2+1]+segs[i*2+2];}void operator()(int l,int r,Ope ope){out(l,r,ope,1);upd(l,r,ope,0,0,segs.size()/2);};void rb(int r,Ope ope){ operator()(0,r,ope); }void lb(int l,Ope ope){ operator()(l,segs.size()/2,ope); }Seg operator()(int l,int r){ return query(l,r,0,0,segs.size()/2);};Seg rb(int r){ operator()(0,r); }Seg lb(int l){ operator()(l,segs.size()/2); }Seg operator()(){ return segs[0];}};int main(){ios_base::sync_with_stdio(false); cin.tie(0);cout<<fixed<<setprecision(0);cauto n=read();cauto q=read();cauto vs=readV(n);cauto ps=readV<pii>(q,{1,0});vector<ll> linv(n+1),rinv(n+1);rep(i,n){add(vs[i],1);linv[i+1]=i+1-sum(vs[i])+linv[i];}fill(bit,bit+nn+1,0);rrep(i,n){add(vs[i],1);rinv[i]=sum(vs[i]-1)+rinv[i+1];}out(linv,rinv,1);LazySegTree<MinMax<int>,Add<int>> init(vector<int>(n+1,0));for(cauto v:vs) init.lb(v+1,1);vv<int> qs(BK);rep(i,q) qs[ps[i].X/SQ].eb(i);vector<ll> re(q);rep(bk,BK)if(qs[bk].size()){sort(all(qs[bk]),[&](cauto &i,cauto &j){ return ps[i].Y<ps[j].Y;});auto st=init;int l=0,r=0;for(cauto i:qs[bk]){cauto [L,R]=ps[i];reps(i,r,R) st.lb(vs[i]+1,-1);rreps(i,L,l) st.rb(vs[i],-1);reps(i,l,L) st.rb(vs[i],1);l=L; r=R;re[i]=st().mn*(r-l)+linv[l]+rinv[r];}}out(re,1);rep(bk,BK)if(qs[bk].size()){int l=0,r=0;ll cur=0;fill(bit,bit+nn+1,0);for(cauto v:vs) add(v,1);for(cauto i:qs[bk]){cauto [L,R]=ps[i];reps(i,r,R) add(vs[i],-1);rreps(i,L,l) cur-=sum(vs[i]-1);reps(i,l,L) cur+=sum(vs[i]-1);l=L; r=R;out(l,r,cur,1);re[i]+=cur;}cur=0; l=0; r=0;fill(bit,bit+nn+1,0);for(cauto i:qs[bk]){cauto [L,R]=ps[i];reps(i,r,R) cur-=l-sum(vs[i]);rreps(i,L,l) add(vs[i],-1);reps(i,l,L) add(vs[i],1);l=L; r=R;out(l,r,cur,1);re[i]+=cur;}}out(re,1);for(cauto &v:re) cout<<v NL;return 0;}