結果

問題 No.1270 Range Arrange Query
ユーザー 👑 hos.lyrichos.lyric
提出日時 2020-10-23 22:52:08
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,146 ms / 7,000 ms
コード長 4,937 bytes
コンパイル時間 1,125 ms
コンパイル使用メモリ 105,280 KB
実行使用メモリ 4,704 KB
最終ジャッジ日時 2023-09-28 17:21:41
合計ジャッジ時間 7,556 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 70 ms
4,380 KB
testcase_07 AC 661 ms
4,380 KB
testcase_08 AC 104 ms
4,380 KB
testcase_09 AC 437 ms
4,376 KB
testcase_10 AC 440 ms
4,380 KB
testcase_11 AC 1,146 ms
4,584 KB
testcase_12 AC 1,144 ms
4,572 KB
testcase_13 AC 1,145 ms
4,564 KB
testcase_14 AC 13 ms
4,704 KB
testcase_15 AC 49 ms
4,664 KB
testcase_16 AC 43 ms
4,604 KB
testcase_17 AC 43 ms
4,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


template <class T, class S, class OpTT, class OpST, class OpSS>
struct SegmentTree {
  const OpTT opTT;
  const OpST opST;
  const OpSS opSS;
  const T idT;
  const S idS;

  int n;
  vector<T> ts;
  vector<S> ss;
  SegmentTree(int n_, const OpTT opTT, const OpST opST, const OpSS opSS,
              const T &idT, const S &idS)
      : opTT(opTT), opST(opST), opSS(opSS), idT(idT), idS(idS) {
    for (n = 1; n < n_; n <<= 1) {}
    ts.assign(n << 1, idT);
    ss.assign(n << 1, idS);
  }
  T &at(int a) {
    return ts[n + a];
  }
  void build() {
    for (int a = n; --a; ) ts[a] = opTT(ts[a << 1], ts[a << 1 | 1]);
  }
  T query(int a, int b, const S &s) {
    return query(1, 0, n, a, b, s);
  }

 private:
  T query(int u, int l, int r, int a, int b, const S &s) {
    if (a < l) a = l;
    if (b > r) b = r;
    if (a >= b) return idT;
    if (a == l && b == r) {
      ts[u] = opST(s, ts[u], r - l);
      ss[u] = opSS(s, ss[u]);
      return ts[u];
    }
    const int uL = u << 1, uR = u << 1 | 1;
    const int mid = (l + r) >> 1;
    // speed-up: if (ss[u] != idS)
if (ss[u] != idS)
    {
      ts[uL] = opST(ss[u], ts[uL], mid - l);
      ts[uR] = opST(ss[u], ts[uR], r - mid);
      ss[uL] = opSS(ss[u], ss[uL]);
      ss[uR] = opSS(ss[u], ss[uR]);
      ss[u] = idS;
    }
    const T resL = query(uL, l, mid, a, b, s);
    const T resR = query(uR, mid, r, a, b, s);
    ts[u] = opTT(ts[uL], ts[uR]);
    return opTT(resL, resR);
  }
};


constexpr int MAX_N = 20010;
constexpr int MAX_Q = 20010;

#ifdef LOCAL
constexpr int B = 3;
#else
constexpr int B = 141;
#endif

int N, Q;
int A[MAX_N];

struct Query { int l, r, id; };
Query P[MAX_Q];

int ans[MAX_Q];

int l, r;
int bitL[MAX_N], bitR[MAX_N];
int now;

void bitAdd(int *bit, int pos, int val) {
  for (int x = pos; x < N; x |= x + 1) bit[x] += val;
}
int bitSum(int *bit, int pos) {
  int ret = 0;
  for (int x = pos - 1; x >= 0; x = (x & (x + 1)) - 1) ret += bit[x];
  return ret;
}

int opTT(int t0, int t1) { return min(t0, t1); }
int opST(int s, int t, int sz) { return s + t; }
int opSS(int s0, int s1) { return s0 + s1; }
using Seg = SegmentTree<int, int, decltype(&opTT), decltype(&opST), decltype(&opSS)>;
Seg *seg;

void addL() {
  now += (l - bitSum(bitL, A[l] + 1));
  now += bitSum(bitR, A[l]);
  bitAdd(bitL, A[l], +1);
  seg->query(0, A[l], +1);
  ++l;
}
void remL() {
  --l;
  bitAdd(bitL, A[l], -1);
  now -= (l - bitSum(bitL, A[l] + 1));
  now -= bitSum(bitR, A[l]);
  seg->query(0, A[l], -1);
}
void addR() {
  --r;
  now += (l - bitSum(bitL, A[r] + 1));
  now += bitSum(bitR, A[r]);
  bitAdd(bitR, A[r], +1);
  seg->query(A[r] + 1, N, +1);
}
void remR() {
  now -= (l - bitSum(bitL, A[r] + 1));
  now -= bitSum(bitR, A[r]);
  bitAdd(bitR, A[r], -1);
  seg->query(A[r] + 1, N, -1);
  ++r;
}

int main() {
  for (; ~scanf("%d%d", &N, &Q); ) {
    for (int i = 0; i < N; ++i) {
      scanf("%d", &A[i]);
      --A[i];
    }
    
    for (int q = 0; q < Q; ++q) {
      scanf("%d%d", &P[q].l, &P[q].r);
      --P[q].l;
      P[q].id = q;
    }
    sort(P, P + Q, [](const Query &a, const Query &b) {
      const int ax = a.l / B;
      const int bx = b.l / B;
      return ((ax != bx) ? (ax < bx) : (ax & 1) ? (a.r > b.r) : (a.r < b.r));
    });
    
    l = 0;
    r = N;
    fill(bitL, bitL + N, 0);
    fill(bitR, bitR + N, 0);
    now = 0;
    seg = new Seg(N, &opTT, &opST, &opSS, N + 1, 0);
    for (int j = 0; j < N; ++j) {
      seg->at(j) = 0;
    }
    seg->build();
    for (int q = 0; q < Q; ++q) {
// cerr<<"query "<<P[q].l<<" "<<P[q].r<<" "<<P[q].id<<endl;
      for (; l < P[q].l; addL()) {}
      for (; l > P[q].l; remL()) {}
      for (; r > P[q].r; addR()) {}
      for (; r < P[q].r; remR()) {}
// cerr<<"  now = "<<now<<endl;
// cerr<<"  seg:";for(int j=0;j<N;++j){cerr<<" "<<seg->query(j,j+1,0);}cerr<<endl;
      ans[P[q].id] = 0;
      ans[P[q].id] += now;
      ans[P[q].id] += (r - l) * seg->query(0, N, 0);
    }
    
    for (int q = 0; q < Q; ++q) {
      printf("%d\n", ans[q]);
    }
  }
  return 0;
}
0