結果

問題 No.876 Range Compress Query
ユーザー ate
提出日時 2019-09-06 22:43:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,958 bytes
コンパイル時間 3,011 ms
コンパイル使用メモリ 209,696 KB
最終ジャッジ日時 2025-01-07 16:54:51
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 10 TLE * 8
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:79:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   79 | main(){
      | ^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;

template<typename T>
T func(const T& a,const T& b){return a+b;}

template<typename T>
struct Lazy_Segment_Tree{
  
  private:
    int n;
    vector<T> node,lazy;
  
  public:
    Lazy_Segment_Tree(vector<T> v){
      int sz=v.size();
      n=1;
      while(n<sz)n<<=1;
      node.resize(2*n-1);
      lazy.resize(2*n-1,0);
      rep(i,sz)node[i+n-1]=v[i];
      for(int i=n-2;i>=0;--i)
        node[i]=func(node[2*i+1],node[2*i+2]);
    }

    void eval(int k,int l,int r){
      if(lazy[k]){
        node[k]+=lazy[k];
        if(r-l>1){
          lazy[2*k+1]+=lazy[k]/2;
          lazy[2*k+2]+=lazy[k]/2;
        }
        lazy[k]=0;
      }
    }

    void add(int a,int b,T x,int k=0,int l=0,int r=0){
      if(r<0)r=n;
      eval(k,l,r);
      if(b<=l || r<=a)return;
      if(a<=l && r<=b){
        lazy[k]+=(r-l)*x;
        eval(k,l,r);
      }
      else{
        add(a,b,x,2*k+1,l,(l+r)/2);
        add(a,b,x,2*k+2,(l+r)/2,r);
        node[k]=func(node[2*k+1],node[2*k+2]);
      }
    }

    T getsum(int a,int b,int k=0,int l=0,int r=-1){
      if(r<0)r=n;
      eval(k,l,r);
      if(b<=l || r<=a)return 0;
      if(a<=l && r<=b)return node[k];
      T vl=getsum(a,b,2*k+1,l,(l+r)/2);
      T vr=getsum(a,b,2*k+2,(l+r)/2,r);
      return func(vl,vr);
    }

    T F(ll l,ll r){
      if(l==r)return 1;
      return G(getsum(l,l+1),getsum(l+1,l+2)) + F(l+1,r);
    }
    T G(T x,T y){
      return x!=y;
    }

    void dump(){
      for(auto x:node)cout<<x<<" ";
      cout<<endl;
    }

};

main(){

  ll n,q;
  cin>>n>>q;
  vector<ll> a(n);
  rep(i,n)cin>>a[i];
  Lazy_Segment_Tree<ll> seg(a);
  rep(i,q){
    ll m,l,r;
    cin>>m>>l>>r;
    l--;r--;
    if(m==1){
      ll x;
      cin>>x;
      seg.add(l,r+1,x);
      //seg.dump();
    }
    else{
      auto tmp=seg.F(l,r+1);
      cout<<(tmp)<<endl;
      //seg.dump();
    }
  }

}
0