[Data Structure] Mo Team (2)

　　Today’s content is Bring the repair team.

Sample question: P1903 [National Training Team] Number Color/Maintenance Queue

Title description

input format

Output format

Input and output sample

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

4
4
3
4

Instructions/Tips

For 100% data, N≤50000, M≤50000, all integers appearing in all input data are greater than or equal to 1 and not more than 10^6.

This question may have a slight card constant

Source: bzoj2120

The data for this question is Luogu self-made data, and it takes 5 minutes to complete the data production using CYaRon.

---

Take the repair team

　　MO team is a very amazing offline algorithm. It can solve the problem on the interval, and optimize the violence by sorting and partitioning the query.

　　 Ordinary Mo team questions are given sequences, and they are constantly inquiring.

　　 Then if there are some modification operations in the inquiry, can Team Mo still do it?

　　 The answer is of course yes.

　　Recall the implementation method of the Mo team:

　　　　1. Pre-processing in advance

　　　　2. Ask about block sorting

　　　　3. Double Move the pointer to solve.

　　The only operation that will change due to modification is 3 operations.

　　 It can be found that: after the modification operation occurs, the interval I am currently asking for processing may not be the interval we were looking for.

　　 So what should I do?

　　 draw lessons from the idea of ​​a persistent line segment tree: back in time.

　　 We can first take the Xiu Mo team as a normal Mo team. After finishing it, if we find that the time is not right, we will go back in time.

　　 To be precise: consider the cost between operations at two points in time.

　　 In this way, just add two more while loops in the ordinary Mo team and it’s OK.

 while(now<q[i ].t)

 change(++now);

 while(now>q[i].t)

 change(now--); 

---

Code

#include

#include

#include

#include

#include

using namespace std;



const int N=50005;

int col[N],n,m,sum[1000005< /span>],be[N];

int fans,qnum,cnum,ans[N];



struct qs{

 int l,r,t,id;

}q[N];

struct cs{

 int x,i;

}c[N];



bool cmp(qs x,qs y) {

 if(be[x.l]!=be[y.l])

 return x.l<y.l;

 if(be[x.r]!=be[y.r])

 return x.r<y.r;

 return x.t<y.t;

}



void upd1(int x) {

 if(!sum[col[x]])

 ++fans;

 ++sum[col[x]];

 return;

}



void upd2(int x) {

 --sum[col[x]];

 if(!sum[col[x]])

 --fans;

 return;

}



int l,r,now;



void change(int x) {

 if(c[x].i<=r&&c[x].i>=l) {

 --sum[col[c[x].i]];

 if(!sum[col[c[x].i] ])

 --fans;

 if(!sum[c[x].x])

 ++fans;

 ++sum[c[x].x];

}

 swap(c[x].x,col[c[x].i]);

 return;

}



int main()

{

 cin>>n>>m;

 int xx=pow(n,2.0/< span style="color: #800080;">3.0);

 char opt;

 for(int i=1;i<=n;i++) {

 cin>>col[i];

 be[i]=i/xx+1;

}

 for(int i=1;i<=m;i++) {

 cin>>opt;

 if(opt=='Q') {

 ++qnum;

 cin>>q[qnum].l>>q[qnum].r;

 q[qnum].t=cnum;

 q[qnum].id=qnum;

}

 else {

 ++cnum;

 cin>>c[cnum].i>>c[cnum].x;

}

}

 sort(q+1,q+qnum+1 ,cmp);

 l=r=fans=now=0;

 for(int i=1;i<=qnum;i++) {

 while(l<q[i].l)

 upd2(l++);

 while(l>q[i].l)

 upd1(--l);

 while(r>q[i].r)

 upd2(r--);

 while(r<q[i].r)

 upd1(++r);

 while(now<q[i].t)

 change(++now);

 while(now>q[i].t)

 change(now--);

 ans[q[i].id]=fans;

}

 for(int i=1;i<=qnum;i++)

 cout<endl;

 return 0;

}

Number color

---

Double Experience CF940F Machine Learning

　　Poke here

Momo bought a set of N color brushes (some of which may be the same color), and placed In a row, you need to answer Momo’s questions. Momo will issue you the following instructions:

1. Q L R means asking you to have several different color brushes from the Lth brush to the Rth brush.

2, R P Col Replace the P brush with the color Col.

In order to meet the requirements of Momo, do you know what you need to do?

The two integers N and M in the first line represent the number of initial pens and the number of things that ink will do.

The N integers in the second row respectively represent the color of the i-th brush in the initial brush row.

Lines 3 to 2+M, each line represents a thing that Momohui will do. See the stem part for the format.

For each Query query, you need to give a number in the corresponding row, which means there are several different colors from the Lth brush to the Rth brush brush.

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

4
4
3
4

Enter #1Copy

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

output#1Copy

4
4
3
4

For 100% data, N≤50000, M≤50000, all integers appearing in all input data are greater than or equal to 1 and not more than 10^6.

This question may have a slight card constant

Source: bzoj2120

The data for this question is Luogu self-made data, and it takes 5 minutes to complete the data production using CYaRon.

Take the repair team

　　MO team is a very amazing offline algorithm. It can solve the problem on the interval, and optimize the violence by sorting and partitioning the query.

　　 Ordinary Mo team questions are given sequences, and they are constantly inquiring.

　　 Then if there are some modification operations in the inquiry, can Team Mo still do it?

　　 The answer is of course yes.

　　Recall the implementation method of the Mo team:

　　　　1. Pre-processing in advance

　　　　2. Ask about block sorting

　　　　3. Double Move the pointer to solve.

　　The only operation that will change due to modification is 3 operations.

　　 It can be found that: after the modification operation occurs, the interval I am currently asking for processing may not be the interval we were looking for.

　　 So what should I do?

　　 draw lessons from the idea of ​​a persistent line segment tree: back in time.

　　 We can first take the Xiu Mo team as a normal Mo team. After finishing it, if we find that the time is not right, we will go back in time.

　　 To be precise: consider the cost between operations at two points in time.

　　 In this way, just add two more while loops in the ordinary Mo team and it’s OK.

 while(now<q[i ].t)

 change(++now);

 while(now>q[i].t)

 change(now--); 

Code

#include

#include

#include

#include

#include

using namespace std;



const int N=50005;

int col[N],n,m,sum[1000005< /span>],be[N];

int fans,qnum,cnum,ans[N];



struct qs{

 int l,r,t,id;

}q[N];

struct cs{

 int x,i;

}c[N];



bool cmp(qs x,qs y) {

 if(be[x.l]!=be[y.l])

 return x.l<y.l;

 if(be[x.r]!=be[y.r])

 return x.r<y.r;

 return x.t<y.t;

}



void upd1(int x) {

 if(!sum[col[x]])

 ++fans;

 ++sum[col[x]];

 return;

}



void upd2(int x) {

 --sum[col[x]];

 if(!sum[col[x]])

 --fans;

 return;

}



int l,r,now;



void change(int x) {

 if(c[x].i<=r&&c[x].i>=l) {

 --sum[col[c[x].i]];

 if(!sum[col[c[x].i] ])

 --fans;

 if(!sum[c[x].x])

 ++fans;

 ++sum[c[x].x];

}

 swap(c[x].x,col[c[x].i]);

 return;

}



int main()

{

 cin>>n>>m;

 int xx=pow(n,2.0/< span style="color: #800080;">3.0);

 char opt;

 for(int i=1;i<=n;i++) {

 cin>>col[i];

 be[i]=i/xx+1;

}

 for(int i=1;i<=m;i++) {

 cin>>opt;

 if(opt=='Q') {

 ++qnum;

 cin>>q[qnum].l>>q[qnum].r;

 q[qnum].t=cnum;

 q[qnum].id=qnum;

}

 else {

 ++cnum;

 cin>>c[cnum].i>>c[cnum].x;

}

}

 sort(q+1,q+qnum+1 ,cmp);

 l=r=fans=now=0;

 for(int i=1;i<=qnum;i++) {

 while(l<q[i].l)

 upd2(l++);

 while(l>q[i].l)

 upd1(--l);

 while(r>q[i].r)

 upd2(r--);

 while(r<q[i].r)

 upd1(++r);

 while(now<q[i].t)

 change(++now);

 while(now>q[i].t)

 change(now--);

 ans[q[i].id]=fans;

}

 for(int i=1;i<=qnum;i++)

 cout<endl;

 return 0;

}

Number color

Double Experience CF940F Machine Learning

　　Poke here

 while(now<q[i].t)

 change(++now);

 while(now>q[i].t)

 change(now--); 

#include

#include

#include

#include

#include

using namespace std;



const int N=50005;

int col[N],n,m,sum[1000005< /span>],be[N];

int fans,qnum,cnum,ans[N];



struct qs{

 int l,r,t,id;

}q[N];

struct cs{

 int x,i;

}c[N];



bool cmp(qs x,qs y) {

 if(be[x.l]!=be[y.l])

 return x.l<y.l;

 if(be[x.r]!=be[y.r])

 return x.r<y.r;

 return x.t<y.t;

}



void upd1(int x) {

 if(!sum[col[x]])

 ++fans;

 ++sum[col[x]];

 return;

}



void upd2(int x) {

 --sum[col[x]];

 if(!sum[col[x]])

 --fans;

 return;

}



int l,r,now;



void change(int x) {

 if(c[x].i<=r&&c[x].i>=l) {

 --sum[col[c[x].i]];

 if(!sum[col[c[x].i] ])

 --fans;

 if(!sum[c[x].x])

 ++fans;

 ++sum[c[x].x];

}

 swap(c[x].x,col[c[x].i]);

 return;

}



int main()

{

 cin>>n>>m;

 int xx=pow(n,2.0/< span style="color: #800080;">3.0);

 char opt;

 for(int i=1;i<=n;i++) {

 cin>>col[i];

 be[i]=i/xx+1;

}

 for(int i=1;i<=m;i++) {

 cin>>opt;

 if(opt=='Q') {

 ++qnum;

 cin>>q[qnum].l>>q[qnum].r;

 q[qnum].t=cnum;

 q[qnum].id=qnum;

}

 else {

 ++cnum;

 cin>>c[cnum].i>>c[cnum].x;

}

}

 sort(q+1,q+qnum+1 ,cmp);

 l=r=fans=now=0;

 for(int i=1;i<=qnum;i++) {

 while(l<q[i].l)

 upd2(l++);

 while(l>q[i].l)

 upd1(--l);

 while(r>q[i].r)

 upd2(r--);

        while(r<q[i].r)

            upd1(++r);

        while(now<q[i].t)

            change(++now);

        while(now>q[i].t)

            change(now--);

        ans[q[i].id]=fans;

}

    for(int i=1;i<=qnum;i++)

        cout<endl;

 return 0;

}

数颜色

#include

#include

#include

#include

#include

using namespace std;



const int N=50005;

int col[N],n,m,sum[1000005],be[N];

int fans,qnum,cnum,ans[N];



struct qs{

    int l,r,t,id;

}q[N];

struct cs{

    int x,i;

}c[N];



bool cmp(qs x,qs y) {

    if(be[x.l]!=be[y.l])

        return x.l<y.l;

    if(be[x.r]!=be[y.r])

        return x.r<y.r;

    return x.t<y.t;

}



void upd1(int x) {

    if(!sum[col[x]])

        ++fans;

    ++sum[col[x]];

    return;

}



void upd2(int x) {

    --sum[col[x]];

    if(!sum[col[x]])

        --fans;

    return;

}



int l,r,now;



void change(int x) {

    if(c[x].i<=r&&c[x].i>=l) {

        --sum[col[c[x].i]];

        if(!sum[col[c[x].i]])

            --fans;

        if(!sum[c[x].x])

            ++fans;

        ++sum[c[x].x];

}

    swap(c[x].x,col[c[x].i]);

    return;

}



int main()

{

    cin>>n>>m;

    int xx=pow(n,2.0/3.0);

    char opt; 

    for(int i=1;i<=n;i++) {

        cin>>col[i];

        be[i]=i/xx+1;

}

    for(int i=1;i<=m;i++) {

        cin>>opt;

        if(opt==‘Q‘) {

            ++qnum;

            cin>>q[qnum].l>>q[qnum].r;

            q[qnum].t=cnum;

            q[qnum].id=qnum;

}

        else {

            ++cnum;

            cin>>c[cnum].i>>c[cnum].x;

}

}

    sort(q+1,q+qnum+1,cmp);

    l=r=fans=now=0;

    for(int i=1;i<=qnum;i++) {

        while(l<q[i].l)

            upd2(l++);

        while(l>q[i].l)

            upd1(--l);

        while(r>q[i].r)

            upd2(r--);

        while(r<q[i].r)

            upd1(++r);

        while(now<q[i].t)

            change(++now);

        while(now>q[i].t)

            change(now--);

        ans[q[i].id]=fans;

}

    for(int i=1;i<=qnum;i++)

        cout<endl;

 return 0;

}