結果

問題 No.1270 Range Arrange Query
ユーザー n_vipn_vip
提出日時 2020-10-23 23:42:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,478 ms / 7,000 ms
コード長 7,045 bytes
コンパイル時間 2,181 ms
コンパイル使用メモリ 160,704 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-21 13:44:10
合計ジャッジ時間 10,606 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 80 ms
6,940 KB
testcase_07 AC 768 ms
6,940 KB
testcase_08 AC 120 ms
6,944 KB
testcase_09 AC 514 ms
6,940 KB
testcase_10 AC 542 ms
6,944 KB
testcase_11 AC 1,455 ms
6,940 KB
testcase_12 AC 1,478 ms
6,940 KB
testcase_13 AC 1,448 ms
6,940 KB
testcase_14 AC 21 ms
6,944 KB
testcase_15 AC 486 ms
6,940 KB
testcase_16 AC 261 ms
6,940 KB
testcase_17 AC 380 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 auto

using 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_captures
template<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));}
#endif
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> 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; //998244353

const 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;
}
0