CF896C 一种vector写法

· · 题解

这里介绍一种 vector 写法（来自某位 dalao）

首先，用 l,r,x 三个信息分别维护区间左右端点，和值。用vector 存这个结构体（显然的

struct Seg{int l,r; ll v;};
vector<Seg> vec;

那么当要涉及的区间跨越了这结构上的区间时候，就要进行区间分裂了。

  1. 假设要分裂开的区间是 [u,v]，如果存在 l,r（在一个Seg内） 使得 l<u\leq r，此时就可以将 [l,r] 分裂为 [l,u-1],[u,r] 两个区间。（对于 v 的处理之后再做）。

  2. 若 \exists [l,r]|(l\leq v<r)，则 [l,r]\to[l,v],[v+1,r]。这样保证了区间的完整性。

  3. 如果 对于操作1 不存在这样的 [l,r]，则一定存在 l=u 或者 l 超过了左右边界；如果 对于操作2 不存在这样的 [l,r]，则一定存在 r=v 或者 r 超过了左右边界。事实上，由于取模的原因，l,r 不可能越界。故此时无需分裂区间，直接加入即可。

对于步骤1，在此位置的 l 改为 u，并在这前面 insert 进 \{pastl,u-1,val\} 即可。pastl 即 l 修改前的值。

这里要注意了，在 O(n) 遍历的方法里，步骤2能不能直接从步骤1后面继续找？乍一看觉得可以，但实测是过不了的，再往前退 2 步找也是不行。这其实因为发生了说明3里的情况。步骤1的指针都跑到数组末尾了，这当然是不行的。所以要加入判断，如果找到了对应的 [l,r] ，则可以从这里继续，反之则需要从开头找（其实步骤1也可以结合二分 lower_bound ，这样就 O(logn) 找了，步骤二就可以直接往后推）。

示例代码：

void split(int l,int r){
  for(auto it=vec.begin();it!=vec.end();++it){
    auto[u,v,w]=*it; if(u<l&&l<=v){
      it->l=l,vec.insert(it,{u,l-1,w}); break; }
    //由于没有引用，所以可以直接这么写
  }
  for(auto it=vec.begin();it!=vec.end();++it){
    auto[u,v,w]=*it; if(u<=r&&r<v){
      it->l=r+1,vec.insert(it,{u,r,w}); break; }
  }
}

对于操作1，先 split 开 l,r，之后模拟即可

split(l,r); 
for(auto&[u,v,w]:vec) 
  if(l<=u&&v<=r) w+=x;

对于操作2，先 split 开 l,r，之后找到对应位置，擦掉对应区间信息，再填上一个新的即可

split(l,r); 
for(wz1=0;l>vec[wz1].l;) ++wz1; 
for(wz2=wz1;wz2<vec.size()&&vec[wz2].r<=r;) ++wz2;   
vec.erase(vec.begin()+wz1,vec.begin()+wz2); //[l,r)
vec.insert(vec.begin()+wz1,{l,r,x});

对于操作3，找区间第 x 小。这个需要一些小 trick。建一个 vector 存这段区间的信息。按照值从小到大排序，然后减去长度，遍历即可。

vector<pair<ll,int>> px; 
for(auto[u,v,w]:vec) 
  if(u<=r&&l<=v) px.push_back({w,min(v,r)-max(u,l)+1});
sort(px.begin(),px.end()); 
for(auto[p,q]:px) 
  if((x-=q)<=0){cout<<p<<'\n'; break;}

操作4，只要 Seg区间 与 [l,r] 有交集，即可计算答案。

y=rnd()%vmax+1,ans=0; 
for(auto[u,v,w]:vec) 
  if(u<=r&&l<=v)
    (ans+=1ll*(min(v,r)-max(u,l)+1)*qpow(w,x,y)%y)%=y;
cout<<ans<<'\n';

结语：这份代码其实还不够完美，可以用二分找第一个 \ge l 的数，也可以在遍历到 r 右边时，立马 break。但这种思路很好理解，每次 O(\frac{n}{区间长度}) 的复杂度可以接受。

想看代码实现细节的，戳这里 完整代码