結果

問題 No.1270 Range Arrange Query
ユーザー SSRSSSRS
提出日時 2020-10-23 23:22:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,435 ms / 7,000 ms
コード長 2,993 bytes
コンパイル時間 2,128 ms
コンパイル使用メモリ 186,112 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-21 13:16:54
合計ジャッジ時間 10,060 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 128 ms
5,376 KB
testcase_07 AC 886 ms
5,376 KB
testcase_08 AC 218 ms
5,376 KB
testcase_09 AC 624 ms
5,376 KB
testcase_10 AC 744 ms
5,376 KB
testcase_11 AC 1,435 ms
5,376 KB
testcase_12 AC 1,424 ms
5,376 KB
testcase_13 AC 1,424 ms
5,376 KB
testcase_14 AC 41 ms
5,376 KB
testcase_15 AC 65 ms
5,376 KB
testcase_16 AC 61 ms
5,376 KB
testcase_17 AC 58 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int SQRT = 535;
const int INF = 1000000000;
template <typename T>
struct binary_indexed_tree{
	int N;
	vector<T> BIT;
	binary_indexed_tree(int n){
		N = 1;
		while (N < n){
			N *= 2;
		}
		BIT = vector<T>(N + 1, 0);
	}
	void add(int i, T x){
		i++;
		while (i <= N){
			BIT[i] += x;
			i += i & -i;
		}
	}
	T sum(int i){
		T ans = 0;
		while (i > 0){
			ans += BIT[i];
			i -= i & -i;
		}
		return ans;
	}
	T sum(int L, int R){
		return sum(R) - sum(L);
	}
	T all(){
		return BIT[N];
	}
};
template <typename T>
struct lazy_segment_tree{
	int N;
	vector<T> ST;
	vector<T> lazy;
	lazy_segment_tree(vector<int> A){
		int n = A.size();
		N = 1;
		while (N < n){
			N *= 2;
		}
		ST = vector<T>(N * 2 - 1, INF);
		lazy = vector<T>(N * 2 - 1, 0);
		for (int i = 0; i < n; i++){
			ST[N - 1 + i] = A[i];
		}
		for (int i = N - 2; i >= 0; i--){
			ST[i] = min(ST[i * 2 + 1], ST[i * 2 + 2]);
		}
	}
	void eval(int i){
		if (i < N - 1){
			lazy[i * 2 + 1] += lazy[i];
			lazy[i * 2 + 2] += lazy[i];
		}
		ST[i] += lazy[i];
		lazy[i] = 0;
	}
	void range_add(int L, int R, T x, int i, int l, int r){
		eval(i);
		if (R <= l || r <= L){
			return;
		} else if (L <= l && r <= R){
			lazy[i] += x;
			eval(i);
		} else {
			int m = (l + r) / 2;
			range_add(L, R, x, i * 2 + 1, l, m);
			range_add(L, R, x, i * 2 + 2, m, r);
			ST[i] = min(ST[i * 2 + 1], ST[i * 2 + 2]);
		}
	}
	void range_add(int L, int R, T x){
		range_add(L, R, x, 0, 0, N);
	}
	T all(){
		eval(0);
		return ST[0];
	}
};
int main(){
  int N, Q;
  cin >> N >> Q;
  vector<int> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
    a[i]--;
  }
  vector<int> l(Q), r(Q);
  for (int i = 0; i < Q; i++){
    cin >> l[i] >> r[i];
    l[i]--;
  }
  vector<tuple<int, int, int, int>> query(Q);
  for (int i = 0; i < Q; i++){
    query[i] = make_tuple(l[i] / SQRT, r[i], l[i], i);
  }
  sort(query.begin(), query.end());
  binary_indexed_tree<int> BIT1(N);
  binary_indexed_tree<int> BIT2(N);
  lazy_segment_tree<int> ST(vector<int>(N, 0));
  vector<long long> ans(Q);
  int L = 0, R = N;
  int invs = 0;
  for (int i = 0; i < Q; i++){
    int l = get<2>(query[i]);
    int r = get<1>(query[i]);
    int id = get<3>(query[i]);
    while (l < L){
      L--;
      ST.range_add(0, a[L], -1);
      invs -= BIT1.sum(a[L] + 1, N);
      invs -= BIT2.sum(a[L]);
      BIT1.add(a[L], -1);
    }
    while (R < r){
      ST.range_add(a[R] + 1, N, -1);
      invs -= BIT1.sum(a[R] + 1, N);
      invs -= BIT2.sum(a[R]);
      BIT2.add(a[R], -1);
      R++;
    }
    while (L < l){
      ST.range_add(0, a[L], 1);
      invs += BIT1.sum(a[L] + 1, N);
      invs += BIT2.sum(a[L]);
      BIT1.add(a[L], 1);
      L++;
    }
    while (r < R){
      R--;
      ST.range_add(a[R] + 1, N, 1);
      invs += BIT1.sum(a[R] + 1, N);
      invs += BIT2.sum(a[R]);
      BIT2.add(a[R], 1);
    }
    ans[id] = ST.all() * (r - l) + invs;
  }
  for (int i = 0; i < Q; i++){
    cout << ans[i] << endl;
  }
}
0