#include using namespace std; #define ALL(x) (x).begin(), (x).end() #define REP(i,n) for(int i=0; ib ? 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 void execute(F1&& add_left, F2&& add_right, F3&& del_left, F4&& del_right, F5&& out) { vector qi(q); iota(qi.begin(),qi.end(),0); // https://nyaannyaan.github.io/library/misc/mo.hpp.html const int wid=max(1,1.0*n/max(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]rs[b]; }); int nl=0, nr=0; for(int& i: qi){ while(nl>ls[i]) add_left(--nl); while(nrrs[i]) del_right(--nr); out(i); } } private: int n, q; vector ls, rs; }; struct FenwickTree { FenwickTree()=default; FenwickTree(int n) { this->n=n; dat=vector(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 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 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 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 A(N); REP(i,N) cin>>A[i], A[i]--; vector 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<>T; while(T--) solve(); }