社区讨论

数据疑似过水

WWang1006
P2801教主的魔法参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m4lfhe15
此快照首次捕获于
2024/12/12 22:42
去年
此快照最后确认于
2025/11/04 12:57
4 个月前
查看原帖
修改操作时将 直接将右侧不完整块清空 可拿 100pts ，但是hack#1会WA
错误代码如下：
CPP
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

#define div(...)

int n,q;

int nb,sb;
int a[1000010],id[1000010];
vector<int>b[1010];int tag[1010];

void modify(int l,int r,int k){
	int bid=id[l],eid=id[r];
	if(id[l]==id[l-1]){
		int i=l;
		for(i=l;id[i]==id[l];++i){
			a[i]+=k;
		}
		b[id[l]].clear();
		for(int j=i-1;id[j]==id[l];--j){
			b[id[l]].push_back(a[j]);
		}
		sort(b[id[l]].begin(),b[id[l]].end());
		bid++;
	}
	if(id[r]==id[r+1]){
		int i=r;
		for(i=r;id[i]==id[r];--i){
			a[i]+=k;
		}
		b[id[r]].clear();
		//注意看这里 ---------------------------------------------------
		eid--;
	}
	for(int i=bid;i<=eid;++i){
		tag[i]+=k;
	}
}
int singlequery(int id,int k){
	int l=0,r=b[id].size()-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(b[id][mid]+tag[id]>=k){
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	return b[id].size()-l;
}
int query(int l,int r,int k){
	int bid=id[l],eid=id[r],ret=0;
	if(id[l]==id[l-1]){
		vector<int>v;
		for(int i=l;id[i]==id[l];++i){
			v.push_back(a[i]);
		}
		sort(v.begin(),v.end());
		for(int i=v.size()-1;i>=0&&v[i]+tag[id[l]]>=k;--i){
			ret++;
		}
		bid++;
	}
	if(id[r]==id[r+1]){
		vector<int>v;
		for(int i=r;id[i]==id[r];--i){
			v.push_back(a[i]);
		}
		sort(v.begin(),v.end());
		for(int i=v.size()-1;i>=0&&v[i]+tag[id[l]]>=k;--i){
			ret++;
		}
		eid--;
	}
	for(int i=bid;i<=eid;++i){
		ret+=singlequery(i,k);
	}
	return ret;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	div(input){
		cin>>n>>q;
		for(int i=1;i<=n;++i){
			cin>>a[i];
		}
	}
	div(prework){
		sb=ceil(sqrt(n));
		nb=ceil(1.0*n/sb);
		for(int i=1,nsb=0,nid=1;i<=n;++i){
			nsb++;
			id[i]=nid;
			b[nid].push_back(a[i]);
			if(nsb>=sb){
				nsb=0;
				nid++;
			}
		}
		for(int i=1;i<=nb;++i){
			sort(b[i].begin(),b[i].end());
		}
	}
	div(solve){
		while(q--){
			char opt;int l,r,k;
			cin>>opt>>l>>r>>k;
			if(opt=='M'){
				modify(l,r,k);
			}
			else{
				cout<<query(l,r,k)<<"\n";
			}
		}
	}
}
正确代码如下：
CPP
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

#define div(...)

int n,q;

int nb,sb;
int a[1000010],id[1000010];
vector<int>b[1010];int tag[1010];

void modify(int l,int r,int k){
	int bid=id[l],eid=id[r];
	if(id[l]==id[l-1]){
		int i=l;
		for(i=l;id[i]==id[l];++i){
			a[i]+=k;
		}
		b[id[l]].clear();
		for(int j=i-1;id[j]==id[l];--j){
			b[id[l]].push_back(a[j]);
		}
		sort(b[id[l]].begin(),b[id[l]].end());
		bid++;
	}
	if(id[r]==id[r+1]){
		int i=r;
		for(i=r;id[i]==id[r];--i){
			a[i]+=k;
		}
		b[id[r]].clear();
		for(int j=i+1;id[j]==id[r];++j){
			b[id[r]].push_back(a[j]);
		}
		sort(b[id[r]].begin(),b[id[r]].end());
		eid--;
	}
	for(int i=bid;i<=eid;++i){
		tag[i]+=k;
	}
}
int singlequery(int id,int k){
	int l=0,r=b[id].size()-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(b[id][mid]+tag[id]>=k){
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	return b[id].size()-l;
}
int query(int l,int r,int k){
	int bid=id[l],eid=id[r],ret=0;
	if(id[l]==id[l-1]){
		vector<int>v;
		for(int i=l;id[i]==id[l];++i){
			v.push_back(a[i]);
		}
		sort(v.begin(),v.end());
		for(int i=v.size()-1;i>=0&&v[i]+tag[id[l]]>=k;--i){
			ret++;
		}
		bid++;
	}
	if(id[r]==id[r+1]){
		vector<int>v;
		for(int i=r;id[i]==id[r];--i){
			v.push_back(a[i]);
		}
		sort(v.begin(),v.end());
		for(int i=v.size()-1;i>=0&&v[i]+tag[id[l]]>=k;--i){
			ret++;
		}
		eid--;
	}
	for(int i=bid;i<=eid;++i){
		ret+=singlequery(i,k);
	}
	return ret;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	div(input){
		cin>>n>>q;
		for(int i=1;i<=n;++i){
			cin>>a[i];
		}
	}
	div(prework){
		sb=ceil(sqrt(n));
		nb=ceil(1.0*n/sb);
		for(int i=1,nsb=0,nid=1;i<=n;++i){
			nsb++;
			id[i]=nid;
			b[nid].push_back(a[i]);
			if(nsb>=sb){
				nsb=0;
				nid++;
			}
		}
		for(int i=1;i<=nb;++i){
			sort(b[i].begin(),b[i].end());
		}
	}
	div(solve){
		while(q--){
			char opt;int l,r,k;
			cin>>opt>>l>>r>>k;
			if(opt=='M'){
				modify(l,r,k);
			}
			else{
				cout<<query(l,r,k)<<"\n";
			}
		}
	}
}

回复

共 2 条回复，欢迎继续交流。

正在加载回复...