結果

問題 No.876 Range Compress Query
コンテスト
ユーザー vjudge1
提出日時 2026-07-24 21:51:05
言語 C++14
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 27 ms / 2,000 ms
+ 924µs
コード長 1,047 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 994 ms
コンパイル使用メモリ 182,400 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-07-24 21:52:20
合計ジャッジ時間 3,063 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,q,a[N],b[N],t1[N],t2[N];
void u1(int i,int x){for(;i<=n;i+=i&-i)t1[i]+=x;}
int q1(int i){int s=0;for(;i;i-=i&-i)s+=t1[i];return s;}
void u2(int i,int x){for(;i<=n;i+=i&-i)t2[i]+=x;}
int q2(int i){int s=0;for(;i;i-=i&-i)s+=t2[i];return s;}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<n;++i)b[i]=(a[i]!=a[i+1]);
    for(int i=1;i<n;++i)u2(i,b[i]);
    while(q--){
        int op;cin>>op;
        if(op==1){
            int l,r,x;cin>>l>>r>>x;
            u1(l,x);if(r<n)u1(r+1,-x);
            if(l>1){
                int p=a[l-1]+q1(l-1),c=a[l]+q1(l),nb=(p!=c);
                if(nb!=b[l-1])u2(l-1,nb-b[l-1]),b[l-1]=nb;
            }
            if(r<n){
                int c=a[r]+q1(r),p=a[r+1]+q1(r+1),nb=(c!=p);
                if(nb!=b[r])u2(r,nb-b[r]),b[r]=nb;
            }
        }else{
            int l,r;cin>>l>>r;
            cout<<(l==r?1:1+q2(r-1)-q2(l-1))<<'\n';
        }
    }
}
0