社区讨论

全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 条回复,欢迎继续交流。

正在加载回复...