結果

問題 No.3305 Shift Sort
ユーザー Nyaa Uruzu
提出日時 2025-10-05 16:04:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 613 ms / 2,000 ms
コード長 3,392 bytes
コンパイル時間 3,266 ms
コンパイル使用メモリ 291,596 KB
実行使用メモリ 34,628 KB
最終ジャッジ日時 2025-10-05 16:05:35
合計ジャッジ時間 15,840 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for (ll i=0;i<(ll)n;i++)
#define rrep(i,n) for (ll i=n-1;i>=(ll)0;i--)
#define loop(i,m,n) for(ll i=m;i<=(ll)n;i++)
#define rloop(i,m,n) for(ll i=m;i>=(ll)n;i--)
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vdbg(a) rep(ii,a.size()){cout<<a[ii]<<" ";}cout<<endl;
#define vpdbg(a) rep(ii,a.size()){cout<<"{"<<a[ii].first<<","<<a[ii].second<<"} ";}cout<<endl;
#define vvdbg(a) rep(ii,a.size()){rep(jj,a[ii].size()){cout<<a[ii][jj]<<" ";}cout<<endl;}
#define setdbg(a) for(const auto & ii:a){cout<<ii<<" ";}cout<<endl;
#define inf 4000000000000000000LL
#define mod 998244353LL
//#define mod 1000000007LL
#define eps 0.000000001
random_device rnd;// 非決定的な乱数生成器
mt19937 mt(rnd());// メルセンヌ・ツイスタの32ビット版、引数は初期シード



//整数同士の累乗の計算をする。
ll power(ll A, ll B) {
	ll result = 1;
	for (ll i=0;i<B;i++){
		result *= A;
	}
	return result;
}

//底がaの対数xを計算。ただし小数点は繰り上げ。
ll logax(ll a, ll x){
	if(x<=1)return 0;
	ll result = 1;
	ll power = 1;
	while (power < (x+a-1) / a){
		power *= a;
		result++;
	}
	return result;
}

//powerとlogが前提条件
//セグ木,乗せる値の型が必要
template<typename T>
struct SegTree{
	ll size;
	ll tall;
	vector<T> data;
	function<T(T,T)> p;
	//セグ木に乗せる値の初期値をa配列にし、putの関数をセグ木に乗せる、dをデフォルト値に。
	SegTree(vector<T> a,function<T(T,T)> put,T d) : data(power(2,logax(2,a.size())+1)) {
		size = data.size()/2;
		tall=logax(2,size)+1;
		p=put;
		ll tmp=size;
		data = vector<T>(size*2,d);
		while(tmp!=0){
			if(tmp==size)rep(i,a.size())data[tmp+i]=a[i];
			else rep(i,tmp) data[tmp+i]=p(data[2*(tmp+i)],data[2*(tmp+i)+1]);
			tmp/=2;
		}
	}
	//更新、t番目の値をxにする。
	void update(ll t,T x){
		t+=size;
		while(t!=0){
			if(t>=size)data[t]=x;
			else data[t]=p(data[2*t],data[2*t+1]);
			t/=2;
		}
	}
	//取得、l~r区間内の評価値を取得する。
	T get(ll l,ll r){
		//lとrが範囲外なら範囲内に正す
		l=max(0LL,l);
		r=min(r,size-1);
		r++;
		T ans=data[0];
		ll pos=l+size;
		ll wid=1;
		//出来る限り上に上げきる。
		while(l+(wid*2)<=r){
			while(l%(wid*2)==0&&l+(wid*2)<=r)pos/=2,wid*=2;
			ans=p(ans,data[pos]);
			pos++;
			l+=wid;
		}
		//上げ終わったので今度は下げる
		while(l!=r){
			while(l+wid>r)pos*=2,wid/=2;
			ans=p(ans,data[pos]);
			pos++;
			l+=wid;
		}
		return ans;
	}
};

ll sums(ll a,ll b){
	return a+b;
}

//メイン
int main(){
	ll n,q;
	cin>>n>>q;
	vl a(n+1);
	loop(i,1,n)cin>>a[i],a[i]--;
	a[0]=n;

	vl prevbig(n+1,0);
	vvl inv(n+1);

	vector<pair<ll,ll>> st;
	st.push_back({n,0});
	loop(i,1,n){
		while(st.back().first<a[i]){
			st.pop_back();
		}
		prevbig[i]=st.back().second;
		inv[st.back().second].push_back(i);
		st.push_back({a[i],i});
	}

	vector<vector<pair<ll,ll>>> query(n+1);
	rep(i,q){
		ll l,r;
		cin>>l>>r;

		query[l].push_back({r,i});
	}

	SegTree<ll> seg(vl(n+1,0),sums,0);
	vl ans(q,0);
	rloop(i,n,1){
		rep(j,inv[i].size()){
			seg.update(inv[i][j],1);
		}
		rep(j,query[i].size()){
			ll right=query[i][j].first;
			ll index=query[i][j].second;
			ans[index]=seg.get(i,right);
		}
	}

	rep(i,q)cout<<ans[i]<<endl;
	return 0;
}
0