【BZOJ 2957】楼房重建&&Codechef COT5 Count on a Treap&&【NOIP模拟赛】Weed 线段树的分治维护

时间：2021-05-24 10:03:20

线段树是一种作用于静态区间上的数据结构，可以高效查询连续区间和单点，类似于一种静态的分治。他最迷人的地方在于“lazy标记”，对于lazy标记一般随我们从父区间进入子区间而下传，最终给到叶子节点，但还有一种做法就是对于作用域一整个区间的标记，就将其放置在此区间节点，查询时再结算其贡献，但无论怎样我们都要保证我们查询到的区间信息的真实性完整性，这就意味着我们接触一个区间若要了解到他的全部有用信息，并不用进入其下层区间（以上两种标记方式往往再结合出现时有巧妙的用处）。于是我们必须高效地合并子区间的信息以维护此区间的信息，对于多数信息我们可以在O（1）时间内高效完成，但是有一些时候我们的合并并不顺利，并不能直接结算，这个时候我们会多记录一些附加信息来便于合并，但是如果这样行不通我们还有另外一种高效的方式，就是在合并的时候我们再对子区间进行分治（往往利用线段树静态分治的天然优势），如果能得到O（log）的复杂度（或者其他可以接受的复杂度），那么就是可行的，这种方法在题目中的三道题中均有应用。

关于【BZOJ 2957】楼房重建，比较裸，直接讲解下两道。懒的说了

Codechef COT5 Count on a Treap

关于这道题你一看题干就不能去打Treap。我们想一想笛卡尔树，那么我们就把这些点用key值（二叉树）排序，然后发现得到的区间里，如果用val值（堆）从大到小切割区间，就得到了我们想要的Treap。两个数之间的最大值（val）就他们的lca，那么我们又发现，每个点向两边的上升序列长度和就是他的深度，这样我们就得到了一种可行方案，现在我们就是要找上升序列列长度，方法同上题。

#pragma GCC optimize("O3")

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define mid ((l+r)>>1)

typedef long long LL;

const LL N=;

typedef std::pair<LL,LL> pii;

struct Segment_Tree{

  Segment_Tree *ch[];

  int zlen,ylen,pos;LL max;

  inline void pushup(){

    if(ch[]->max>ch[]->max) max=ch[]->max,pos=ch[]->pos;

    else max=ch[]->max,pos=ch[]->pos;

  }

}*root,node[N<<];

int n,sz,T;LL q[N][];

pii poi[N];

inline void build(Segment_Tree *&p,int l,int r){

  p=node+(sz++),p->zlen=p->ylen=;

  if(l==r){p->max=,p->pos=l;return;}

  build(p->ch[],l,mid),build(p->ch[],mid+,r);

  p->pushup();

}

inline int zcalc(Segment_Tree *p,int l,int r,LL max){

  if(p==NULL||p->max<=max)return ;

  if(l==r)return p->max>max;

  if(p->ch[]->max<=max)return zcalc(p->ch[],mid+,r,max);

  else return zcalc(p->ch[],l,mid,max)+p->zlen-p->ch[]->zlen;

}

inline int ycalc(Segment_Tree *p,int l,int r,LL max){

  if(p==NULL||p->max<=max)return ;

  if(l==r)return p->max>max;

  if(p->ch[]->max<=max)return ycalc(p->ch[],l,mid,max);

  else return ycalc(p->ch[],mid+,r,max)+p->ylen-p->ch[]->ylen;

}

inline void U(Segment_Tree *p,int l,int r,int pos,LL val){

  if(l==r){p->max=val;return;}

  if(pos<=mid)U(p->ch[],l,mid,pos,val);

  else U(p->ch[],mid+,r,pos,val);

  p->pushup();

  p->zlen=p->ch[]->zlen+zcalc(p->ch[],mid+,r,p->ch[]->max);

  p->ylen=p->ch[]->ylen+ycalc(p->ch[],l,mid,p->ch[]->max);

}

inline pii Q(Segment_Tree *p,int l,int r,int z,int y){

  if(z<=l&&r<=y)return std::make_pair(p->max,p->pos);

  pii ret=std::make_pair(-,-),temp;

  if(z<=mid)temp=Q(p->ch[],l,mid,z,y);

  if(temp.first>ret.first)ret=temp;

  if(mid<y)temp=Q(p->ch[],mid+,r,z,y);

  if(temp.first>ret.first)ret=temp;

  return ret;

}

inline void Qz(Segment_Tree *p,int l,int r,int z,int y,int &ans,LL &max){

  if(z<=l&&r<=y){ans+=zcalc(p,l,r,max),max=std::max(max,p->max);return;}

  if(z<=mid)Qz(p->ch[],l,mid,z,y,ans,max);

  if(mid<y)Qz(p->ch[],mid+,r,z,y,ans,max);

}

inline void Qy(Segment_Tree *p,int l,int r,int z,int y,int &ans,LL &max){

  if(z<=l&&r<=y){ans+=ycalc(p,l,r,max),max=std::max(max,p->max);return;}

  if(mid<y)Qy(p->ch[],mid+,r,z,y,ans,max);

  if(z<=mid)Qy(p->ch[],l,mid,z,y,ans,max);

}

inline int Q(int pos){

  int ret=,ans=;LL max=poi[pos].second;

  if(pos!=)Qy(root,,n,,pos-,ans,max);

  ret+=ans,ans=,max=poi[pos].second;

  if(pos!=n)Qz(root,,n,pos+,n,ans,max);

  ret+=ans;return ret;

}

int main(){

  scanf("%d",&T);for(int i=;i<=T;++i){

    scanf("%lld",&q[i][]);

    if(q[i][]&)scanf("%lld",&q[i][]);

    else scanf("%lld%lld",&q[i][],&q[i][]);

    if(q[i][]==)poi[++n]=std::make_pair(q[i][],q[i][]);

  }

  std::sort(poi+,poi+(n+)),build(root,,n);

  for(int i=,pos,l,r,mi;i<=T;++i)

    switch(q[i][]){

      case :

        pos=std::lower_bound(poi+,poi+(n+),std::make_pair(q[i][],0LL))-poi;

        U(root,,n,pos,q[i][]);break;

      case :

        pos=std::lower_bound(poi+,poi+(n+),std::make_pair(q[i][],0LL))-poi;

        U(root,,n,pos,);break;

      case :

        l=std::lower_bound(poi+,poi+(n+),std::make_pair(q[i][],0LL))-poi;

        r=std::lower_bound(poi+,poi+(n+),std::make_pair(q[i][],0LL))-poi;

        if(l>r)l^=r^=l^=r;mi=Q(root,,n,l,r).second;

        printf("%d\n",Q(l)+Q(r)-Q(mi)*);break;

    }

}

Codechef COT5 Count on a Treap

【NOIP模拟赛】Weed

这道题十分巧妙，我们在线段树上记录三个值，要删之前的多少点，剩下多少点，剩下多少东西，然后单点修改，查询root，维护同理。

#pragma GCC optimize("O3")

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define mid ((l+r)>>1)

const int N=;

inline void read(int &sum){

  register char ch=getchar();

  for(sum=;ch<''||ch>'';ch=getchar());

  for(;ch>=''&&ch<='';sum=(sum<<)+(sum<<)+ch-'',ch=getchar());

}

struct Segment_Tree{

  Segment_Tree *ch[];

  int del,sum,num;

}*root,node[N<<];

int sz,n,m;

inline void build(Segment_Tree *&p,int l,int r){

  p=node+(sz++);if(l==r)return;

  build(p->ch[],l,mid),build(p->ch[],mid+,r);

}

inline int Q(Segment_Tree *p,int l,int r,int del){

  if(p->num<=del)return ;

  if(l==r)return p->sum;

  if(p->ch[]->num>=del)return p->sum-p->ch[]->sum+Q(p->ch[],mid+,r,del);

  else return Q(p->ch[],l,mid,del-p->ch[]->num+p->ch[]->del);

}

inline void U(Segment_Tree *p,int l,int r,int pos,int key,int opt){

  if(l==r){

    if(opt)p->sum=,p->num=,p->del=key;

    else p->del=,p->num=,p->sum=key;

    return;

  }

  if(pos<=mid)U(p->ch[],l,mid,pos,key,opt);

  else U(p->ch[],mid+,r,pos,key,opt);

  if(p->ch[]->num<=p->ch[]->del)

    p->del=p->ch[]->del+p->ch[]->del-p->ch[]->num,p->sum=p->ch[]->sum,p->num=p->ch[]->num;

  else

    p->del=p->ch[]->del,p->num=p->ch[]->num+p->ch[]->num-p->ch[]->del,

    p->sum=p->ch[]->sum+Q(p->ch[],l,mid,p->ch[]->del);

}

int main(){

  read(n),read(m),build(root,,n);

  for(int i=,x,y;i<=n;++i)

    read(x),read(y),U(root,,n,i,y,x);

  int pos,opt,key;

  while(m--){

    read(pos),read(opt),read(key);

    U(root,,n,pos,key,opt);

    printf("%d\n",root->sum);

  }

}

【NOIP模拟赛】Weed

相关文章