結果

問題 No.1270 Range Arrange Query
コンテスト
ユーザー SSRS
提出日時 2020-10-23 23:20:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,993 bytes
コンパイル時間 2,050 ms
コンパイル使用メモリ 185,904 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-21 13:14:55
合計ジャッジ時間 10,717 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 RE * 3
権限があれば一括ダウンロードができます

ソースコード

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(N);
  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