結果

問題 No.876 Range Compress Query
ユーザー kkktymkkktym
提出日時 2019-09-07 13:01:25
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 154 ms / 2,000 ms
コード長 1,414 bytes
コンパイル時間 1,799 ms
コンパイル使用メモリ 69,492 KB
実行使用メモリ 9,836 KB
最終ジャッジ日時 2023-09-08 15:40:29
合計ジャッジ時間 2,944 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 3 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 148 ms
9,580 KB
testcase_12 AC 125 ms
9,392 KB
testcase_13 AC 127 ms
9,424 KB
testcase_14 AC 147 ms
9,652 KB
testcase_15 AC 111 ms
9,180 KB
testcase_16 AC 145 ms
9,684 KB
testcase_17 AC 148 ms
9,656 KB
testcase_18 AC 154 ms
9,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
typedef long long ll;
template <typename X>
struct RCQ{
  vector<X> dif;
  vector<X> dat;
  int n;

  RCQ(int _n)
  {
    n = 1;
    while(n<_n) n*=2;
    dif.assign(2*n-1,0);
    dat.assign(2*n-1,0);
  }

  void update(int k,X y)
  {
    k += n-1;
    dif[k] += y;
    if(dif[k] == 0) dat[k] = 0;
    else dat[k] = 1;
    while(k>0){
      k = (k-1)/2;
      dat[k] = dat[2*k+1] + dat[2*k+2];
    }
  }

  X query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return 0;

    if(a<=l&&r<=b) return dat[k];
    else{
      X vl = query(a,b,2*k+1,l,(l+r)/2);
      X vr = query(a,b,2*k+2,(l+r)/2,r);
      return vl+vr;
    }
  }
  
};
int _n,q;
vector<ll> a,x;
vector<int> com,l,r; 
int main()
{
  cin >> _n >> q;
  a.resize(_n);
  rep(i,_n) cin >> a[i];
  com.resize(q);
  l.resize(q);
  r.resize(q);
  x.resize(q);    
  rep(i,q){
    cin >> com[i] >> l[i] >> r[i];
    l[i]--;r[i]--;
    if(com[i] == 1) cin >> x[i];
  }
  
  RCQ<ll> rcq(_n-1);
  rep(i,_n-1){
    ll y = a[i+1]-a[i];
    rcq.update(i,y);
  }
  
  rep(i,q){
    if(com[i]==1){
      if(l[i]!=0){
	rcq.update(l[i]-1,x[i]);
      }
      if(r[i]!=_n-1){
	rcq.update(r[i],-x[i]);
      }
    }
    else{
      cout << rcq.query(l[i],r[i],0,0,rcq.n)+1 << "\n";
    }
  }  
  return 0;
}
0