gpt4 book ai didi

algorithm - 3 的倍数的惰性传播线段树

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:33:20 25 4
gpt4 key购买 nike

缩略题:给定一个包含 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、st[p].one 元素 1 mod 3 和 st[p].two 元素 2 mod 3 中的 0 mod 3 元素;当我更新时,我将这些元素(0->1、1->2、2->0)移动一个位置,然后使用惰性。更新时,我返回一对 >,这只是一种存储三元组数字的简单方法,这样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;
}

最佳答案

您可以在每个节点中存储两个值:
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]

对于节点 v,可被 3 整除的元素数是 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 整除的元素数的方法类似。

关于algorithm - 3 的倍数的惰性传播线段树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24413248/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com