結果

問題 No.3446 Range Adjacent Differences
ユーザー Taiki0715
提出日時 2026-02-18 22:57:06
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 1,649 ms / 2,200 ms
コード長 10,551 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,201 ms
コンパイル使用メモリ 361,192 KB
実行使用メモリ 89,800 KB
最終ジャッジ日時 2026-02-18 22:57:40
合計ジャッジ時間 27,268 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using P=pair<ll,ll>;
template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;
template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}
template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}
template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;}
template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;}
template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}
template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}
template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}
template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}
#define overload3(_1,_2,_3,name,...) name
#define rep1(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define reps(i,l,r) rep2(i,l,r)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcountll(x)
#define fin(x) return cout<<(x)<<'\n',static_cast<void>(0)
#define yn(x) cout<<((x)?"Yes\n":"No\n")
#define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end())
template<typename T>
inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();}
ll myceil(ll a,ll b){return (a+b-1)/b;}
template<typename T,size_t n,size_t id=0>
auto vec(const int (&d)[n],const T &init=T()){
  if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));
  else return init;
}
#ifdef LOCAL
#include<debug.h>
#define SWITCH(a,b) (a)
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
#define SWITCH(a,b) (b)
template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}
#endif
struct Timer{
  clock_t start;
  Timer(){
    start=clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(16);
  }
  inline double now(){return (double)(clock()-start)/1000;}
  #ifdef LOCAL
  ~Timer(){
    cerr<<"time:";
    cerr<<now();
    cerr<<"ms\n";
  }
  #endif
}timer;
void SOLVE();
int main(){
  int testcase=1;
  //cin>>testcase;
  for(int i=0;i<testcase;i++){
    SOLVE();
  }
}
#include<type_traits>
#include<concepts>
template<typename T>
constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);}
template<typename T>
constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);}

template<typename T>
constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);}
template<typename T>
constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);}

template<typename T>
constexpr std::enable_if_t<std::is_integral_v<T>,T>floor_pow2(T n){return n==0?0:T(1)<<msb(n);}

template<typename T>
constexpr std::enable_if_t<std::is_integral_v<T>,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);}

template<std::integral T>
constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);}
template<std::integral T>
constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);}
struct VanEmdeBoasTree{
private:
  int n;
  int l,r;
  int s,sl;
  int mask;
  using u64=uint64_t;
  struct veb3{
    u64 aux=0;
    inline void insert(int x){aux|=u64(1)<<x;}
    inline void erase(int x){aux&=~(u64(1)<<x);}
    inline bool empty()const{return aux==0;}
    inline void clear(){aux=0;}
    inline int predecessor(int x)const{
      if(x<0)return -1;
      u64 sh=aux<<(63-x);
      return sh==0?-1:x-__builtin_clzll(sh);
    }
    inline int successor(int x)const{
      u64 sh=aux>>x;
      return sh==0?64:x+__builtin_ctzll(sh);
    }
    inline bool contains(int x)const{return aux>>x&1;}
  };
  struct veb2{
    int l,r;
    int s,sl;
    int mask;
    int mn,mx;
    std::vector<veb3>child;
    veb3 aux;
    veb2(){}
    veb2(int log2n):l(log2n/2),r((log2n+1)/2),s(1<<log2n),sl(1<<(log2n/2)),mask((1<<((log2n+1)/2))-1),mn(1<<log2n),mx(-1){
      child.resize(sl);
    }
    void insert(int x){
      if(x<=mn){
        if(x==mn)return;
        std::swap(x,mn);
        if(x==s)mx=mn;
        if(x>=mx)return;
      }
      else if(x>=mx){
        if(x==mx)return;
        std::swap(x,mx);
        if(x<=mn)return;
      }
      int nx=x>>r;
      if(child[nx].empty())aux.insert(nx);
      child[nx].insert(x&mask);
    }
    void erase(int x){
      if(x<=mn){
        if(x<mn)return;
        x=mn=successor(mn+1);
        if(x>=mx){
          if(x>mx)mx=-1;
          return;
        }
      }
      else if(x>=mx){
        if(x>mx)return;
        x=mx=predecessor(mx-1);
        if(x<=mn)return;
      }
      int nx=x>>r;
      child[nx].erase(x&mask);
      if(child[nx].empty())aux.erase(nx);
    }
    bool empty()const{return mx<mn;}
    void clear(){
      mn=s,mx=-1;
      for(int i=0;i<sl;i++)child[i].clear();
      aux.clear();
    }
    int predecessor(int x)const{
      if(x>=mx)return mx;
      if(x<mn)return -1;
      int nx=x>>r;
      int res=child[nx].predecessor(x&mask);
      if(res>=0)return (nx<<r)+res;
      nx=aux.predecessor(nx-1);
      return nx<0?mn:((nx<<r)+child[nx].predecessor(mask));
    }
    int successor(int x)const{
      if(x<=mn)return mn;
      if(x>mx)return s;
      int nx=x>>r;
      int res=child[nx].successor(x&mask);
      if(res<=mask)return (nx<<r)+res;
      nx=aux.successor(nx+1);
      return nx>=sl?mx:((nx<<r)+child[nx].successor(0));
    }
    inline bool contains(int x)const{return successor(x)==x;}
  };
  std::vector<veb2>child;
  veb2 aux;
  int mn,mx;
  int N;
public:
  VanEmdeBoasTree():mn(0),mx(-1){}
  VanEmdeBoasTree(int n):N(n){
    if(n<16)n=16;
    n=ceil_pow2(n);
    int log2n=msb(n);
    assert(n<=(1<<24));
    mn=-1;
    mx=n;
    l=log2n/2,r=(log2n+1)/2;
    s=1<<log2n,sl=1<<l;
    mask=(1<<r)-1;
    aux=veb2(l);
    child.resize(sl,veb2(r));
  }
  void insert(int x){
    if(x<=mn){
      if(x==mn)return;
      std::swap(x,mn);
      if(x==s)mx=mn;
      if(x>=mx)return;
    }
    else if(x>=mx){
      if(x==mx)return;
      std::swap(x,mx);
      if(x<=mn)return;
    }
    int nx=x>>r;
    if(child[nx].empty())aux.insert(nx);
    child[nx].insert(x&mask);
  }
  void erase(int x){
    if(x<=mn){
      if(x<mn)return;
      x=mn=successor(mn+1);
      if(x>=mx){
        if(x>mx)mx=-1;
        return;
      }
    }
    else if(x>=mx){
      if(x>mx)return;
      x=mx=predecessor(mx-1);
      if(x<=mn)return;
    }
    int nx=x>>r;
    child[nx].erase(x&mask);
    if(child[nx].empty())aux.erase(nx);
  }
  void clear(){
    mn=s,mx=-1;
    for(int i=0;i<sl;i++)child[i].clear();
    aux.clear();
  }
  int predecessor(int x)const{
    if(x>=mx)return mx;
    if(x<mn)return -1;
    int nx=x>>r;
    int res=child[nx].predecessor(x&mask);
    if(res>=0)return (nx<<r)+res;
    nx=aux.predecessor(nx-1);
    return nx<0?mn:((nx<<r)+child[nx].predecessor(mask));
  }
  int successor(int x)const{
    if(x<=mn)return mn;
    if(x>mx)return N;
    int nx=x>>r;
    int res=child[nx].successor(x&mask);
    if(res<=mask)return std::min(N,(nx<<r)+res);
    nx=aux.successor(nx+1);
    return std::min(N,(nx>=sl?mx:((nx<<r)+child[nx].successor(0))));
  }
  inline bool contains(int x)const{return successor(x)==x;}
};
std::vector<int>mo_order(int n,const std::vector<std::pair<int,int>>&query){
  int z=ceil_pow2(n+1);
  auto hilbert=[&](int x,int y)->long long {
    long long rx,ry,res=0;
    for(long long s=z>>1;s;s>>=1){
      rx=(x&s)>0,ry=(y&s)>0;
      res+=s*s*((rx*3)^ry);
      if(ry)continue;
      if(rx){
        x=z-1-x;
        y=z-1-y;
      }
      std::swap(x,y);
    }
    return res;
  };
  std::vector<long long>h(query.size());
  for(int i=0;i<(int)query.size();i++)h[i]=hilbert(query[i].first,query[i].second);
  std::vector<int>ord(query.size());
  std::iota(ord.begin(),ord.end(),0);
  std::sort(ord.begin(),ord.end(),[&](int lhs,int rhs){return h[lhs]<h[rhs];});
  return ord;
}
struct Mo{
private:
  int n,z;
  std::vector<std::pair<int,int>>Q;
public:
  Mo(int N):n(N){
    z=1;
    while(z<=n)z<<=1;
  }
  void add(int l,int r){
    Q.emplace_back(l,r);
  }
public:
  void build(const auto &add,const auto &del,const auto &out){
    int q=Q.size();
    std::vector<int>ord=mo_order(n,Q);
    int l=0,r=0;
    for(int i:ord){
      if(Q[i].first<l)add(Q[i].first,l),l=Q[i].first;
      if(r<Q[i].second)add(r,Q[i].second),r=Q[i].second;
      if(l<Q[i].first)del(l,Q[i].first),l=Q[i].first;
      if(Q[i].second<r)del(Q[i].second,r),r=Q[i].second;
      out(i);
    }
  }
};
void SOLVE(){
  int n,q;
  cin>>n>>q;
  vector<int>a(n);
  cin>>a;
  int mx=*max_element(all(a));
  a--;
  VanEmdeBoasTree veb(mx),diff(mx);
  vector<int>cnt(mx),cntdiff(mx);
  Mo mo(n);
  vector<pair<int,char>>query(q);
  rep(i,q){
    int l,r,x;
    char c;
    cin>>l>>r>>x>>c;
    l--;
    mo.add(l,r);
    query[i]={x,c};
  }
  vector<int>ans(q);
  int sz=0;
  #define ADD(x)\
  if(++cntdiff[x]==1)diff.insert(x);
  #define ERASE(x)\
  if(--cntdiff[x]==0)diff.erase(x);
  auto add=[&](int l,int r){
    if(sz==0){
      cnt[a[l]]++;
      veb.insert(a[l++]);
      sz++;
    }
    rep(i,l,r){
      int pre=veb.predecessor(a[i]);
      int nxt=veb.successor(a[i]+1);
      if(++cnt[a[i]]==1)veb.insert(a[i]);
      if(pre!=-1&&nxt<mx)ERASE(nxt-pre);
      if(pre!=-1)ADD(a[i]-pre);
      if(nxt<mx)ADD(nxt-a[i]);
    }
    sz+=r-l;
  };
  auto erase=[&](int l,int r){
    sz-=r-l;
    rep(i,l,r){
      if(--cnt[a[i]]==0)veb.erase(a[i]);
      int pre=veb.predecessor(a[i]);
      int nxt=veb.successor(a[i]+1);
      if(pre!=-1&&nxt<mx)ADD(nxt-pre);
      if(pre!=-1)ERASE(a[i]-pre);
      if(nxt<mx)ERASE(nxt-a[i]);
    }
  };
  auto out=[&](int i){
    auto [x,c]=query[i];
    if(c=='L'){
      chmin(x,mx-1);
      ans[i]=diff.predecessor(x);
    }
    else{
      if(x>=mx){
        ans[i]=-1;
        return;
      }
      ans[i]=diff.successor(x);
      if(ans[i]>=mx)ans[i]=-1;
    }
  };
  mo.build(add,erase,out);
  rep(i,q)cout<<ans[i]<<'\n';
}
0