Сокращенная задача: вам дан массив из n элементов, изначально все они равны 0.
Вы получите два типа запроса: 0 index1 index2, в этом случае вам нужно увеличить на единицу все элементы в диапазоне index1 index2 (включено).
Второй тип: 1 index1 index2, в этом случае вы должны напечатать число, представляющее, сколько элементов между index1 и index2 (включительно) делится на 3.
Конечно, поскольку n очень велико (10 ^ 6), хорошим подходом является использование дерева сегментов для хранения интервалов, а также использование ленивого распространения для обновления дерева в журнале n.
Но я на самом деле действительно не знаю, как применить здесь ленивое распространение, потому что вы должны учитывать три возможных состояния для каждого числа (может быть 3k,3k+1,3k+2), а не только два, как подбрасывание монеты проблема.
Если я поставлю флаг на какой-то интервал, который включен в интервал моего запроса, я должен обновить его, глядя на исходный массив и его значение, но когда мне нужно обновить сын этого интервала, я должен сделать то же самое опять же, это пустая трата времени....
Любая лучшая идея? Искал в сети, но ничего не нашел...
РЕДАКТИРОВАТЬ: я следую вашим предложениям, и я кодирую это (С++) и работает для некоторых базовых случаев, но когда я отправляю его, я получаю только 10/100 баллов, что с этим не так? (Я знаю, что это немного длинно и в нем мало комментариев, но это простое дерево сегментов с ленивым распространением, если вы что-то не понимаете, пожалуйста, скажите мне!
ПРИМЕЧАНИЕ: st[p].zero содержит элементы 0 mod 3 в интервале, хранящемся в индексе p, элементы st[p].one 1 mod 3 и элементы st[p].two 2 mod 3; Когда я обновляю, я сдвигаю на одну позицию эти элементы (0->1, 1->2, 2->0) и использую lazy. При обновлении я возвращаю пару ‹ int , пара ‹ int, int > >, просто простой способ сохранить тройку чисел. Таким образом, a может вернуть разницу чисел 0,1,2 по модулю 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;
}