[总结][数据结构]支持区间延迟标记的ZKW线段树模板

首先,ZKW线段树事实上并不能做到像是递归版一样的灵活,不过对于一些简单的区间标记还是可以处理,而且代码好写,常数小。
在一个线段树结构中,一个节点应当有以下属性:标记类型,维护的值类型,为了方便维护通常还记录节点的左右端点。
定义标记的结构体:

struct Mark {//这个结构体并不完整。。。
  Datatype1 d1;
  Datatype2 d2;
  ....
  Mark(Datatype1 _d1 = Init_Datatype1 , Datatype2 _d2 = Init_Datatype2 , ...):d1(_d1),d2(_d2), ...{}
  void operator += (const Mark &_c) { //用标记_c来更新当前标记
    if (d1 == Init_Datatype1 && d2 == Init_Datatype2 && ...) //无标记,以_c作为标记
     *this = _c;
    else {   //已经存在标记,更新标记
     d1 = ..
      d2 = ..
      ...
    }
  }
}null(init_Datatype1 , init_Datatype2 , ...);

null表示当前节点没有标记.
下面考虑ZKW线段树的定义,将支持以下操作.

struct SegmentTree {
  int M;                           //最后一层点的个数
  int dl[Maxsize] , dr[Maxsize];   //分别表示节点的左右端点
  Mark c[Maxsize];                 //每个节点的标记
  Datatype_ans ans[Maxsize];       //节点存放的答案
  int stack[Stacksize] , top;      //后面要用到的栈
  void build(int);                 //建立一颗支持维护[1,参数值1]的ZKW线段树
  void makeMark(int , Mark)        //用参数值2的标记更新标号为参数值1的节点
  void pushdown(int);              //将标号为参数值1的节点的标记下传
  void update(int);                //用标号为参数值1的节点的左右儿子存放的答案来更新其自身
  void pushpath(int);              //自上而下下传标号为参数值1的节点至根节点(标号为1节点)路径上所有点的标记
  void modify(int , int , Mark)    //用参数值3的标记修改[参数值1,参数值2]的区间
  Datatype_ans query(int , int)    //返回[参数值,参数值2]区间的答案
};

有一些操作是因题而异的,下面将用几个函数概括一些操作。

Datatype_ans change(Datatype_ans x , Mark _c)    //返回答案x被标记_c更新后的最终答案
Datatype_ans Merge(Datatype_ans L , Datatype_ans R) //返回以答案L作为左区间,答案R作为右区间合并后总区间答案

下面是一些详细的函数套用。
假设需要维护的区间为

void SegmentTree::build(int _size) {
  for(M = 1 , M < (_size + 2) ; M <<= 1); //最后一层的节点数必定不少于区间长度+2
  int i;
  for(i = 1 ; i < (M << 1) ; ++i)   //初始化标记
     c[i] = null;
  for(i = 0 ; i < M ; ++i)
    dl[M + i] = dr[M + i] = i , ans[i] = Init_ans_i;  //初始化节点的左右端点和答案
  for(i = M - 1 ; i >= 1 ; --i) {
    update(i);                   //维护答案
    dl[i] = dl[i << 1];          //维护左右端点
    dr[i] = dr[(i << 1) | 1];
   }
}
void makeMark(int x , Mark _c) {
    c[x] += _c;
  ans[x] = change(ans[x] , _c);
}
void pushdown(int x) {
    if (c[x] != null && x < M) {//需保证x不是叶子节点 ,否则没有必要传标记
     makeMark(x << 1  c[x]);
    makeMark((x << 1) | 1 , c[x]);
    c[x] = null;
  }
}
void update(int x) {
    ans[x] = Merge(ans[x << 1] , ans[(x << 1) | 1]); //合并答案
}
void pushpath(int x) {
    top = 0;
  for(; x ; x >>= 1)  //使用栈记录当前点至根节点路径上所有点,并由上至下下传标记
     stack[++top] = x;
  for(; top ; top--)
    pushdown(stack[top]);
}
void modify(int tl , int tr , Mark _c) {
    int insl = 0 , insr = 0;
  for(tl = tl + M - 1 , tr = tr + M + 1 ; tl ^ tr ^ 1 ; tl >>= 1 , tr >>= 1) { //经典的写法
     if (~tl & 1) {
        if (!insl)  //找到左侧第一个被询问的点进行pushpath操作
         pushpath(insl = tl ^ 1);
      makeMark(tl ^ 1 , _c);
    }
    if (tr ^ 1) {
        if (!insr) //同理,找到右侧第一个被询问的点进行pushpath操作
         pushpath(insr = tr ^ 1);
      makeMark(tr ^ 1 , _c);
    }
  }
  for(insl = insl >> 1 ; insl ; insl >>= 1) //分别从刚才记录的左右两个第一个询问到的点由底至上update
     update(insl);
  for(insr = insr >> 1 ; insr ; insr >>= 1)
    update(insr);
}
Datatype_ans query(int tl , int tr) { //不细说可以了吧?
 int insl = 0, insr = 0;
  Datatype_ans ansl = Init_ans , ansr = Init_ans;
  for(tl = tl + M - 1 , tr = tr + M + 1 ; tl ^ tr ^1 ; tl >>= 1 , tr >>= 1) {
    if (~tl & 1) {
        if (!insl)
        pushpath(insl = tl ^ 1);
      ansl = Merge(ansl , ans[tl ^ 1]);
    }
        if (tr & 1) {
        if (!insr)
        pushpath(insr = tr ^ 1);
      ansr = Merge(ans[tr ^ 1] , ansr);
    }
  }
  return Merge(ansl , ansr);
}

线段树的模板就到这里。容易证明它的建树为,每一次询问和修改复杂度均为,且代码好写,由于避免了递归和讨论,常数较小。
我用这种线段树在BZOJ上通过了1798,这是一道双标记经典题目。目前通过各种常数优化,暂时Rank1...
下面是代码:

#include <cstdio>
#include <cstring>
#include <cctype>
inline int getc() {
    static const int L = 1 << 15;
    static char buf[L] , *S = buf , *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf , 1 , L , stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint() {
    int c;
    while(!isdigit(c = getc()));
    int tmp = c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 3) + (tmp << 1) + c - '0';
    return tmp;
}
typedef long long LL;
int mod;
struct Mark {
    int u , v;
    Mark(int _u = -1 , int _v = -1):u(_u),v(_v){}
    bool operator == (const Mark &b) const {
        return u == b.u && v == b.v;
    }
    bool operator != (const Mark &b) const {
        return u != b.u || v != b.v;
    }
    void operator += (const Mark &b) {
        if (u == -1 && v == -1)
            *this = b;
        else {
            u = (LL)u * b.u % mod;
            v = ((LL)v * b.u + b.v) % mod;
        }
    }
}null(-1 , -1);
void inc(int &a , int b , int c) {
    a = ((LL)b + c >= mod) ? b - mod + c : b + c;
}
#define N ((131072 << 1) + 10)
int sav[100010];
struct SegmentTree {
    int M , sum[N] , size[N];
    Mark c[N];
    void build(int _size) {
        for(M = 1 ; M < (_size + 2) ; M <<= 1);
        int i;
        for(i = 0 ; i < M ; ++i)
            sum[M + i] = sav[i] , size[M + i] = 1;
        for(i = M - 1 ; i >= 1 ; --i) {
            inc(sum[i] , sum[i << 1] , sum[(i << 1) | 1]);
            size[i] = size[i << 1] + size[(i << 1) | 1];
        }
    }
    int stack[25] , top;
    void make_Mark(int x , Mark _c) {
        c[x] += _c;
        sum[x] = ((LL)sum[x] * _c.u + (LL)_c.v * size[x]) % mod;
    }
    void pushdown(int x) {
        if (c[x] != null && x < M) {
            if (x << 1)
                make_Mark(x << 1 , c[x]);
            if ((x << 1) | 1)
                make_Mark((x << 1) | 1 , c[x]);
            c[x] = null;
        }
    }
    void update_path(int x) {
        top = 0;
        for(; x ; x >>= 1)
            stack[++top] = x;
        while(top--)
            pushdown(stack[top]);
    }
    int query(int tl , int tr) {
        int insl = 0 , insr = 0 , res = 0;
        for(tl = tl + M - 1 , tr = tr + M + 1 ; tl ^ tr ^ 1 ; tl >>= 1 , tr >>= 1) {
            if (~tl & 1) {
                if (!insl)
                    update_path(insl = tl ^ 1);
                inc(res , res , sum[tl ^ 1]);
            }
            if (tr & 1) {
                if (!insr)
                    update_path(insr = tr ^ 1);
                inc(res  ,res , sum[tr ^ 1]);
            }
        }
        return res;
    }
    void modify(int tl , int tr , Mark _c) {
        int insl = 0 , insr = 0;
        for(tl = tl + M - 1 , tr = tr + M + 1 ; tl ^ tr ^ 1 ; tl >>= 1 , tr >>= 1) {
            if (~tl & 1) {
                if (!insl)
                    update_path(insl = tl ^ 1);
                make_Mark(tl ^ 1 , _c);
            }
            if (tr & 1) {
                if (!insr)
                    update_path(insr = tr ^ 1);
                make_Mark(tr ^ 1 , _c);
            }
        }
        for(insl = insl >> 1 ; insl ; insl >>= 1)
            inc(sum[insl] , sum[insl << 1] , sum[(insl << 1) | 1]);
        for(insr = insr >> 1 ; insr ; insr >>= 1)
            inc(sum[insr] , sum[insr << 1] , sum[(insr << 1) | 1]);
    }
}ZKW;
int n;
int main() {
    n = getint();
    mod = getint();
    int i;
    for(i = 1 ; i <= n ; ++i)
        sav[i] = getint() , sav[i] %= mod;
    ZKW.build(n);
    int ask = getint();
    int sign , a , b , x;
    while(ask--) {
        sign = getint();
        a = getint();
        b = getint();
        if (sign == 1) {
            x = getint();
            ZKW.modify(a , b , Mark(x % mod, 0));
        }
        else if (sign == 2) {
            x = getint();
            ZKW.modify(a , b , Mark(1 , x % mod));
        }
        else
            printf("%d\n" , ZKW.query(a , b));
    }
    return 0;
}
comments powered by Disqus