1

要約された問題: n 要素の配列が与えられました。最初はすべて 0 です。

2 種類のクエリを受け取ります: 0 index1 index2。この場合、範囲 index1 index2(included) 内のすべての要素を 1 ずつ増やす必要があります。

2 番目のタイプ: 1 index1 index2。この場合、index1 と index2 (含まれる) の間の要素が 3 で割り切れる数を表す数値を出力する必要があります。

もちろん、n は非常に大きい (10^6) ため、セグメント ツリーを使用して間隔を格納し、遅延伝播を使用してログ n のツリーを更新することも良い方法です。

しかし、実際には、ここで遅延伝播を適用する方法が本当にわかりません。コインを弾くように2つだけではなく、すべての数字（3k、3k + 1、3k + 2の可能性があります）に対して3つの可能な状態を考慮する必要があるためです。問題。

クエリの間隔に含まれる間隔にフラグを立てた場合、元の配列とその値を見て更新する必要がありますが、この間隔の息子を更新する必要がある場合は、同じことをしなければなりません繰り返しますが、これは時間の無駄です....

もっと良いアイデアはありますか？ネットで検索しましたが、何も見つかりませんでした...

編集:私はあなたの提案に従い、これ(C++)をコーディングし、いくつかの基本ケースで機能しますが、提出すると10/100ポイントしか得られません。何が問題なのですか? (少し長くてコメントが少ないことは承知していますが、遅延伝播を使用した単純なセグメント ツリーです。何かわからないことがあれば教えてください!

注: 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) の位置が 1 つシフトし、lazy を使用します。更新時に、ペア < int 、ペア < int、int > > を返します。これは、3 つの数値を格納する単純な方法です。このようにして、数値 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