1

精简问题：给定一个包含 n 个元素的数组，最初它们都是 0。

您将收到两种类型的查询：0 index1 index2，在这种情况下，您必须将 index1 index2（包括）范围内的所有元素都加一。

第二种类型：1 index1 index2，在这种情况下，您必须打印一个数字来表示 index1 和 index2（包括）之间有多少元素可以被 3 整除。

当然，由于 n 非常大（10^6），好的方法是使用分段树来存储区间，并使用惰性传播来更新 log n 中的树。

但是我实际上真的不知道如何在这里应用惰性传播，因为您必须考虑每个数字的三种可能状态（可能是 3k,3k+1,3k+2），而不仅仅是两个作为翻转硬币问题。

如果我在查询间隔中包含的某个间隔上放置一个标志，我必须查看原始数组及其值来更新它，但是当我必须更新这个间隔的儿子时，我必须做同样的事情再次，这是浪费时间....

有更好的主意吗？我在网上搜索但一无所获...

编辑：我遵循您的建议并编写此代码（C++），并且适用于某些基本情况，但是当我提交它时，我只得到 10/100 分，它有什么问题？（我知道它有点长，没有太多评论，但它是一个具有惰性传播的简单 Segment Tree，如果您有什么不明白的地方，请告诉我！

注意： st[p].zero 包含存储在索引 p 中的间隔为 0 mod 3 的元素，st[p].one 元素 1 mod 3 和 st[p].two 元素 2 mod 3；当我更新时，我将这些元素（0->1、1->2、2->0）移动一个位置并使用惰性。更新时，我返回一个pair < int , pair< int, int >> ，只是存储三组数字的简单方法，这样a可以返回数字0,1,2 mod 3的差。

int sol;

struct mod{
    mod(){ zero=0; one=0;two=0;}
    int zero;
    int one;
    int two;  
};

class SegmentTree {         
public: int lazy[MAX_N];
  mod st[MAX_N];    
  int n;        
  int left (int p) { return p << 1; }     
  int right(int p) { return (p << 1) + 1; }

  void build(int p, int L, int R){
        if(L == R)
            st[p].zero=1;
        else{
            st[p].zero = R - L + 1;
            build(left(p), L, (L + R) / 2);
            build(right(p), ((L + R) / 2) + 1, R);
        }
        return;
  }

  void query(int p, int L, int R, int i, int j) {            
    if (L > R || i > R || j < L) return; 

    if(lazy[p]!=0){     // Check if this no has to be updated
        for(int k=0;k<lazy[p];k++){
            swap(st[p].zero,st[p].two);
            swap(st[p].one, st[p].two);
        }
        if(L != R){
            lazy[left(p)] = (lazy[left(p)] + lazy[p]) % 3;
            lazy[right(p)] = (lazy[right(p)] + lazy[p]) % 3;
        }
        lazy[p] = 0;
    } 


    if (L >= i && R <= j) { sol += st[p].zero;   return; }              


    query(left(p) , L              , (L+R) / 2, i, j);
    query(right(p), (L+R) / 2 + 1, R          , i, j);

    return; 
  }          

  pair < int, ii > update_tree(int p, int L, int R, int i, int j) {

    if (L > R || i > R || j < L){
      pair< int, pair< int, int > >  PP; PP.first=PP.second.first=PP.second.second=INF;
      return PP;
    }

    if(lazy[p]!=0){     // Check if this no has to be updated
        for(int k=0;k<lazy[p];k++){
            swap(st[p].zero,st[p].two);
            swap(st[p].one, st[p].two);
        }
        if(L != R){
            lazy[left(p)] = (lazy[left(p)] + lazy[p]) % 3;
            lazy[right(p)] = (lazy[right(p)] + lazy[p]) % 3;
        }
        lazy[p] = 0;
    } 

    if(L>=i && R<=j){
        swap(st[p].zero, st[p].two);
        swap(st[p].one, st[p].two);
        if(L != R){
            lazy[left(p)] = (lazy[left(p)] + 1) % 3;
            lazy[right(p)] = (lazy[right(p)] + 1) % 3;
        }
        pair< int, pair< int, int > > t; t.first = st[p].zero-st[p].one; t.second.first = st[p].one-st[p].two; t.second.second = st[p].two-st[p].zero;
        return t;
    }

    pair< int, pair< int, int > > s = update_tree(left(p), L, (L+R)/2, i, j); // Updating left child
    pair< int, pair< int, int > > s2 = update_tree(right(p), 1+(L+R)/2, R, i, j); // Updating right child
    pair< int, pair< int, int > > d2;
    d2.first = ( (s.first!=INF ? s.first : 0) + (s2.first!=INF ? s2.first : 0) ); // Calculating difference from the ones given by the children
    d2.second.first = ( (s.second.first!=INF ? s.second.first : 0) + (s2.second.first!=INF ? s2.second.first : 0) );
    d2.second.second = ( (s.second.second!=INF ? s.second.second : 0) + (s2.second.second!=INF ? s2.second.second : 0) );
    st[p].zero += d2.first; st[p].one += d2.second.first; st[p].two += d2.second.second; // Updating root 
    return d2;  // Return difference
  }

  public:
  SegmentTree(const vi &_A) {
    n = (int)_A.size();            
    build(1, 0, n - 1);                                  
  }

  void query(int i, int j) { return query(1, 0, n - 1, i, j); }   

  pair< int, pair< int, int > > update_tree(int i, int j) {
    return update_tree(1, 0, n - 1, i, j); }
};


int N,Q;

int main() {
    FILE * in; FILE * out;
    in = fopen("input.txt","r"); out = fopen("output.txt","w");

    fscanf(in, "%d %d" , &N, &Q);
    //cin>>N>>Q;
    int arr[N];
    vi A(arr,arr+N);

    SegmentTree *st = new SegmentTree(A);

    for(int i=0;i<Q;i++){
        int t,q,q2; 
        fscanf(in, "%d %d %d " , &t, &q, &q2);
        //cin>>t>>q>>q2;
        if(q > q2) swap(q, q2);
        if(t){
            sol=0;
            st->query(q,q2);
            fprintf(out, "%d\n", sol);           
            //cout<<sol<<endl;
        }
        else{
            pair<int, pair< int, int > > t = st->update_tree(q,q2);
        }
    }

    fclose(in); fclose(out);
    return 0;
}
4

2 回答 2

2

您可以在每个节点中存储两个值：
1) int count[3]- 此节点的段中有多少个 0、1 和 2。
2) int shift- 移位值（最初为零）。

操作按以下方式执行（我使用伪代码）：

add_one(node v)
    v.shift += 1
    v.shift %= 3

propagate(node v)
    v.left_child.shift += v.shift
    v.left_child.shift %= 3
    v.right_child.shift += v.shift
    v.right_child.shift %= 3 
    v.shift = 0
    for i = 0..2:
        v.count[i] = get_count(v.left, i) + get_count(v.right, i)

get_count(node v, int remainder)
    return v.count[(remainder + v.shift) % 3]

一个节点能被 3 整除的元素个数v是get_count(v, 0). 节点的更新是add_one操作。一般来说，它可以用作普通的段树（回答范围查询）。

整个树更新如下所示：

update(node v, int left, int right)
    if v is fully covered by [left; right]
        add_one(v)
    else:
        propagate(v)
        if [left; right] intersects with the left child:
            update(v.left, left, right)
        if[left; right] intersects with the right child:
            update(v.right, left, right)
        for i = 0..2:
            v.count[i] = get_count(v.left, i) + get_count(v.right, i)

以类似的方式获得可被 3 整除的元素数。

于 2014-06-25T16:21:07.073 回答
1

似乎您永远不必关心元素的值，只关心它们的值模 3。

保留分段树，按照您的建议使用延迟更新。每个节点都知道 0、1 和 2 以 3 为模的事物的数量（记忆化）。

每次更新都会命中 log(n) 个节点。当更新到达一个节点时，您记得您必须更新后代（延迟更新）并且您循环子树中记忆的事物数量，即 0、1 和 2 模 3。

每个查询命中 log(n) 个节点；它们是相同的节点，相同间隔的更新会命中。每当查询遇到尚未完成的延迟更新时，它会在递归之前将更新推送到后代。除此之外，它所做的只是将每个完全包含在查询间隔中的最大子树中的 0 模 3 元素的数量相加。

于 2014-06-25T16:18:53.977 回答