結果
| 問題 |
No.3305 Shift Sort
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 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 |
ソースコード
//#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;
}