結果
| 問題 |
No.3305 Shift Sort
|
| コンテスト | |
| ユーザー |
Today03
|
| 提出日時 | 2025-10-05 16:29:45 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,206 bytes |
| コンパイル時間 | 3,289 ms |
| コンパイル使用メモリ | 291,276 KB |
| 実行使用メモリ | 9,744 KB |
| 最終ジャッジ日時 | 2025-10-05 16:30:25 |
| 合計ジャッジ時間 | 27,477 ms |
|
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | WA * 14 TLE * 6 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define REP(i,n) for(int i=0; i<n; i++)
bool chmax(auto& a, auto b) { return a<b ? a=b, true : false; }
bool chmin(auto& a, auto b) { return a>b ? a=b, true : false; }
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;
#ifdef DEBUG
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif
/// @brief Mo's Algorithm
/// @ref https://ei1333.hateblo.jp/entry/2017/09/11/211011
struct Mo {
/// @brief コンストラクタ
Mo(int n) {
this->n=n;
q=0;
}
/// @brief クエリ [l, r) を追加する
void add(int l, int r) {
q++;
ls.push_back(l);
rs.push_back(r);
}
/// @brief クエリを実行する
/// @param add_left `add_left(i)` i 番目の要素が左から加わるときの処理
/// @param add_right `add_right(i)` i 番目の要素が右から加わるときの処理
/// @param del_left `del_left(i)` i 番目の要素が左から抜けるときの処理
/// @param del_right `del_right(i)` i 番目の要素が右から抜けるときの処理
/// @param out `out(i)` i 番目のクエリの答えを求めたときの処理
/// @note O(N sqrt(Q))
template<typename F1, typename F2, typename F3, typename F4, typename F5>
void execute(F1&& add_left, F2&& add_right, F3&& del_left, F4&& del_right, F5&& out) {
vector<int> qi(q); iota(qi.begin(),qi.end(),0);
// https://nyaannyaan.github.io/library/misc/mo.hpp.html
const int wid=max<int>(1,1.0*n/max<double>(1.0,sqrt(q*2.0/3.0)));
sort(qi.begin(),qi.end(),[&](int a, int b) {
if(ls[a]/wid!=ls[b]/wid) return ls[a]<ls[b];
if((ls[a]/wid)&1) return rs[a]<rs[b];
return rs[a]>rs[b];
});
int nl=0, nr=0;
for(int& i: qi){
while(nl>ls[i]) add_left(--nl);
while(nr<rs[i]) add_right(nr++);
while(nl<ls[i]) del_left(nl++);
while(nr>rs[i]) del_right(--nr);
out(i);
}
}
private:
int n, q;
vector<int> ls, rs;
};
struct FenwickTree {
FenwickTree()=default;
FenwickTree(int n) {
this->n=n;
dat=vector<ll>(n,0);
}
void add(int i, ll x) {
i++;
while(i<=n) dat[i-1]+=x, i+=i&-i;
}
ll sum(int l, int r) { return sum(r)-sum(l); }
ll operator[](int i) { return sum(i,i+1); }
int size() { return n; }
private:
int n;
vector<ll> dat;
ll sum(int r) {
ll ret=0;
while(r>0) ret+=dat[r-1], r-=r&-r;
return ret;
}
};
/// @brief 可換群
namespace Abel {
/// @brief 和
template<typename T>
struct Sum {
using Type=T;
static Type id() { return T(0); }
static Type op(const Type& a, const Type& b) { return a+b; }
static Type inv(const Type& x) { return -x; }
};
/// @brief XOR
template<typename T>
struct Xor {
using Type=T;
static Type id() { return T(0); }
static Type op(const Type& a, const Type& b) { return a^b; }
static Type inv(const Type& x) { return x; }
};
}
//----------------------------------------------------------
void solve() {
int N,Q; cin>>N>>Q;
vector<int> A(N); REP(i,N) cin>>A[i], A[i]--;
vector<ll> ans(Q);
Mo mo(N);
FenwickTree ft(N);
ll cur=0;
auto add_left=[&](int i) {
cur+=ft.sum(0,A[i]);
ft.add(A[i],+1);
};
auto add_right=[&](int i) {
cur+=min(ft.sum(A[i]+1,N),1ll);
ft.add(A[i],+1);
};
auto del_left=[&](int i) {
cur-=ft.sum(0,A[i]);
ft.add(A[i],-1);
};
auto del_right=[&](int i) {
cur-=min(ft.sum(A[i]+1,N),1ll);
ft.add(A[i],-1);
};
auto out=[&](int q) { ans[q]=cur; };
REP(i,Q) {
int l,r; cin>>l>>r;
l--;
mo.add(l,r);
}
debug(N,Q,A);
mo.execute(add_left,add_right,del_left,del_right,out);
for(ll x: ans) cout<<x<<'\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
//cout<<fixed<<setprecision(15);
int T=1; //cin>>T;
while(T--) solve();
}
Today03