社区讨论
全wa求助
P1903【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo1ge4qq
- 此快照首次捕获于
- 2023/10/22 20:37 2 年前
- 此快照最后确认于
- 2023/11/02 21:01 2 年前
感谢!!!
CPP#include <algorithm>
#include <cmath>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#define int long long
using namespace std;
int n, m;
const int szed = 1000010;
int st[szed], ed[szed], a[szed], sum[szed],bl[szed];
unordered_map<int, int> mp[szed];
int ask(int l,int r){
unordered_set<int> sts;
int aws=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;i++){
sts.insert(a[i]);
}
aws=sts.size();
}
else{
for(int i=l;i<=ed[bl[l]];i++){
sts.insert(a[i]);
}
for(int i=st[bl[r]];i<=r;i++){
sts.insert(a[i]);
}
aws=sts.size();
for(int i=bl[l]+1;i<bl[r];i++){
aws+=sum[i];
}
}
return aws;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int sz = n / sqrt(n);
for (int i = 1; i <= sz; i++) {
st[i] = (i - 1) * sz + 1;
ed[i] = (i == sz ? n : i * sz);
unordered_set<int> sts;
for(int i2=st[i];i2<=ed[i];i2++){
cin >> a[i2];
bl[i2]=i;
sts.insert(a[i2]);
mp[i][a[i2]]++;
}
sum[i]=sts.size();
}
while (m--) {
char op;
cin >> op;
int num1, num2;
cin >> num1 >> num2;
int loc=bl[num1];
if(op=='R'){
mp[loc][a[num1]]--;
if(mp[loc][a[num1]]==0){
sum[loc]--;
}
a[num1]=num2;
mp[loc][num2]++;
if(mp[loc][num2]==1){
sum[loc]++;
}
}
else{
cout<<ask(num1,num2)<<endl;
}
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...