結果

問題 No.1270 Range Arrange Query
コンテスト
ユーザー kotatsugame
提出日時 2020-10-24 03:18:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5,411 ms / 7,000 ms
コード長 3,803 bytes
コンパイル時間 1,454 ms
コンパイル使用メモリ 97,856 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-21 14:51:50
合計ジャッジ時間 25,951 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
a.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]

ソースコード

diff # 

#line 1 "a.cpp"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#line 2 "/home/kotatsugame/library/datastructure/lazysegtree.cpp"
#include<functional>
template<typename T>
struct lazysegtree{
	using F=function<T(T,T)>;
	using G=function<T(T,T,int,int)>;
	const F calcfn,lazycalcfn;
	const G updatefn;
	int n;
	T defvalue;
	vector<T>dat,lazy;
	vector<bool>lazyflag;
	lazysegtree(int n_=0,T defvalue_=0,
		const F calcfn_=[](T a,T b){return a+b;},
		const F lazycalcfn_=[](T a,T b){return a+b;},
		const G updatefn_=[](T a,T b,int l,int r){return a+b*(r-l);}
	):defvalue(defvalue_),
		calcfn(calcfn_),lazycalcfn(lazycalcfn_),updatefn(updatefn_)
	{
		n=1;
		while(n<n_)n<<=1;
		dat.assign(2*n-1,defvalue);
		lazy.assign(2*n-1,T());
		lazyflag.assign(2*n-1,false);
	}
	void copy(const vector<T>&v)
	{
		for(int i=0;i<v.size();i++)dat[i+n-1]=v[i];
		for(int i=n-2;i>=0;i--)dat[i]=calcfn(dat[2*i+1],dat[2*i+2]);
	}
	void eval(int i,int l,int r)
	{
		if(lazyflag[i])
		{
			dat[i]=updatefn(dat[i],lazy[i],l,r);
			if(r-l>1)
			{
				lazy[2*i+1]=lazyflag[2*i+1]?lazycalcfn(lazy[2*i+1],lazy[i]):lazy[i];
				lazy[2*i+2]=lazyflag[2*i+2]?lazycalcfn(lazy[2*i+2],lazy[i]):lazy[i];
				lazyflag[2*i+1]=lazyflag[2*i+2]=true;
			}
			lazyflag[i]=false;
		}
	}
	void update(int a,int b,T x,int k=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return;
		else if(a<=l&&r<=b)
		{
			lazy[k]=lazyflag[k]?lazycalcfn(lazy[k],x):x;
			lazyflag[k]=true;
			eval(k,l,r);
		}
		else
		{
			update(a,b,x,2*k+1,l,(l+r)/2);
			update(a,b,x,2*k+2,(l+r)/2,r);
			dat[k]=calcfn(dat[2*k+1],dat[2*k+2]);
		}
	}
	T query(int a,int b,int k=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return defvalue;
		else if(a<=l&&r<=b)return dat[k];
		else return calcfn(
			query(a,b,2*k+1,l,(l+r)/2),
			query(a,b,2*k+2,(l+r)/2,r)
		);
	}
};
#line 1 "/home/kotatsugame/library/datastructure/BIT.cpp"
//1-indexed
#line 3 "/home/kotatsugame/library/datastructure/BIT.cpp"
template<typename T>
struct BIT{
	int n;
	vector<T>bit;
	BIT(int n_=0):n(n_),bit(n_+1){}
	T sum(int i)
	{
		T ans=0;
		for(;i>0;i-=i&-i)ans+=bit[i];
		return ans;
	}
	void add(int i,T a)
	{
		if(i==0)return;
		for(;i<=n;i+=i&-i)bit[i]+=a;
	}
	int lower_bound(T k)//k<=sum(ret)
	{
		if(k<=0)return 0;
		int ret=0,i=1;
		while((i<<1)<=n)i<<=1;
		for(;i;i>>=1)
			if(ret+i<=n&&bit[ret+i]<k)k-=bit[ret+=i];
		return ret+1;
	}
};
#line 7 "a.cpp"
int N,Q;
int A[20000];
const int B=100;
vector<pair<pair<int,int>,int> >G[20000];
int ans[20000];
main()
{
	cin>>N>>Q;
	for(int i=0;i<N;i++)
	{
		cin>>A[i];
		A[i]--;
	}
	for(int i=0;i<Q;i++)
	{
		int l,r;cin>>l>>r;
		l--;
		G[l/B].push_back(make_pair(make_pair(l,r),i));
	}
	int all=0;
	BIT<int>L(N),R(N);
	lazysegtree<int>P(N,(int)1e9,
	[](int a,int b){return a<b?a:b;},
	[](int a,int b){return a+b;},
	[](int a,int b,int l,int r){return a+b;});
	P.copy(vector<int>(N,0));
	int l=0,r=N;
	for(int Gi=0;Gi*B<N;Gi++)
	{
		sort(G[Gi].begin(),G[Gi].end(),[](pair<pair<int,int>,int>a,pair<pair<int,int>,int>b)
		{
			return a.first.second<b.first.second;
		});
		for(pair<pair<int,int>,int>p:G[Gi])
		{
			while(l>p.first.first)
			{
				l--;
				all-=L.sum(N-A[l]-1);
				all-=R.sum(A[l]);
				L.add(N-A[l],-1);
				P.update(0,A[l],-1);
			}
			while(r<p.first.second)
			{
				all-=R.sum(A[r]);
				all-=L.sum(N-A[r]-1);
				R.add(A[r]+1,-1);
				P.update(A[r]+1,N,-1);
				r++;
			}
			while(l<p.first.first)
			{
				all+=L.sum(N-A[l]-1);
				all+=R.sum(A[l]);
				L.add(N-A[l],1);
				P.update(0,A[l],1);
				l++;
			}
			while(r>p.first.second)
			{
				r--;
				all+=R.sum(A[r]);
				all+=L.sum(N-A[r]-1);
				R.add(A[r]+1,1);
				P.update(A[r]+1,N,1);
			}
			ans[p.second]=P.query(0,N)*(r-l)+all;
		}
	}
	for(int i=0;i<Q;i++)cout<<ans[i]<<endl;
}
0