• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

题目链接

如果只进行第一个操作,那是一个非常简单的操作。每次直接相乘是好的,但是我们还是要进行第二次运算:要去掉之前相乘的数字,需要将每次相乘的数字按顺序存储。我们可以考虑用数组或者\(vector\)来顺序存储。但是我们会发现,这样的话,每次输出都需要把所有的数相乘,这个运算就是\(O(q)\)的时间复杂度。另外,我们有\(T\)组测试数据,所以如果使用顺序存储结构来存储乘法器,最终的时间复杂度将达到\ (O (TQ 2) \。所以我们需要思考一种更好的存储结构来降低每次查询的时间复杂度,而段树正好可以实现这一点。

我们每次都可以把值上传到根节点,这样当前的\(x\)就是我们的\(tr[1]。val\),第\(i\)个存储的乘数是\(tr。val\),如果要去掉第\(k\)个乘数。也就是说,我们只需要单点修改就可以达到我们想要的目的。

结构段{

int l,r;

i64 val

} tr[N ^ 2];

int q,mod

void pushup(int u) {

trval=(tr[u 1]。val * tr[u 1 | 1]。val)% mod;

}

void build(int u,int l,int r) {

tr={l,r,1 };

if (l==r)返回;

int mid=(l r)1;

build(u 1,l,mid),build(u 1 | 1,mid 1,r);

俯卧撑(u);

}

void modify(int u,int x,i64 v) {

if (tr)。l==tr。r) {

trval=v;

返回;

}

int mid=(tr)。l tr。r)1;

if (mid=x) modify(u 1,x,v);

else modify(u 1 | 1,x,v);

俯卧撑(u);

}

void solve() {

std:cin q mod

build(1,1,q);

rep(i,1,q 1) {

i64 op,m;

STD : CIN op m;

if (op==1)修改(1,I,m),tr[1]。val %=mod

否则{

modify(1,m,1);

tr[1]。val %=mod

}

std:cout tr[1]。val ' \ n

}

}

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now