Soulation to P3939

代码之前有误,请勿粘贴

现已修正

题目描述

从标准输入中读入数据。输入第 1 行两个正整数

输入第 2 行

输入接下来

样例

输入

6 5 
1 2 3 2 3 3  
1 1 3 2 
1 4 6 3  
2 3 
1 1 3 2  
1 4 6 3

输出

算法
二分查找,Vector

预备知识(大佬略)

1.lower_bound()

　　　　在从小到大的排序数组中，lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址。

　　　　　　　　通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

2.upper_bound()

　　　　在从小到大的排序数组中，upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，　　　　　　　　　　　　 通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

3.简单的下标知识

　　　　已知区间左右端点[i,j],则长度为(j-i+1)

正片

显然, 这是一个模拟题

我们可以运用vector这个容器记录rabbit的种类

1.

　当查询区间[l,r]中c颜色只兔子时,我们可用二分查找在[l,r]区间中中c颜色的集合的左右端点[st,ed](预备知识1,2)

st为vector[c]中第一个大于等与l的下标
小心,有一个小坑: ed是vector[c]中第一个大于r的下标-1

　　 Why? Why is it not the first subscript greater than or equal to r in vector[c]

　　　为啥不是vector[c]中第一个大于等与r的下标?

　　　因为[l,r]区间包含[st,ed],所以l<=st<=ed<=r,但vector[c]中第一个大于等与r的下标会超过r,

　　　　　　所以ed是vector[c]中第一个大于r的下标-1

所以长度为max(0,ed-st+1)

2.

当交换两只兔子时 u,u+1

我们照葫芦画瓢找到交换的两个数的位置st,ed

　　　　当st==ed时,就不用交换

将st,ed所属的迭代器进行修改

　　　　1.vector[u][st]++ 相当于把改颜色内的u变成u+1

　　　　2.vector[u+1][st]-- 相当于把改颜色内的u变成u+1

最后在交换a[u],a[u+1]即可

#include
using namespace std;
const int N=3e5+10;
int n,m;
vector<int > rab[N];
int col[N];
int main() 
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>col[i];
        rab[col[i]].push_back(i);
    }
    while(m--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int l,r,c;
            cin>>l>>r>>c;
            int st=lower_bound(rab[c].begin(),rab[c].end(),l)-rab[c].begin();//区间左端点
            int ed=upper_bound(rab[c].begin(),rab[c].end(),r)-rab[c].begin()-1;//右端点
            //cout<
             cout<1<<endl;
        }
        else
        {
            int u;
            cin>>u;
            if(col[u]==col[u+1])continue;
            int st=lower_bound(rab[col[u]].begin(),rab[col[u]].end(),u)-rab[col[u]].begin();
            int ed=lower_bound(rab[col[u+1]].begin(),rab[col[u+1]].end(),u+1)-rab[col[u+1]].begin();
            
            rab[col[u]][st]++;
            rab[col[u+1]][ed]--;
             
            swap(col[u],col[u+1]);    
        }
    }
    return 0;
}

　　　　　　　　　　　　　　　完结撒花

luogu题解

Soulation to P3939

预备知识(大佬略)

正片

1.

2.

相关

标签