70WA求助
查看原帖
70WA求助
776873
da17_楼主2024/4/12 17:45

第5(似乎输出了个负数),第7,第9个点WA了,实在找不出错了,求助

#include <iostream>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <map>
using namespace std;

const int N=1e5+5,M=7e4+5;
typedef long long ll;
int n,m,a[N],len,b[N],cnt[N],h[N],Ans[M/3+5];
struct node{ int l,r,id; }t[M+5];
bitset<N>ans[M/3+5],s;
int cmp(node x,node y){ return b[x.l]==b[y.l]?b[x.l]&1?x.r<y.r:x.r>y.r:x.l<y.l; }
int _get(int x){ return lower_bound(h+1,h+1+n,x)-h; }
void add(int x){ cnt[x]++,s[x+cnt[x]-1]=1; }
void del(int x){ s[x+cnt[x]-1]=0,cnt[x]--; }
void solve(int num){
	int tot=0;
	for(int i=1;i<=num;i++)
		for(int j=0;j<3;j++)
			++tot,scanf("%d%d",&t[tot].l,&t[tot].r),t[tot].id=i;
	sort(t+1,t+1+tot,cmp);
	int l=1,r=0;
	for(int j=1;j<=tot;j++){
		int u=t[j].l,v=t[j].r,p=t[j].id;
		while(l>u) add(a[--l]);
		while(r<v) add(a[++r]);
		while(l<u) del(a[l++]);
		while(r>v) del(a[r--]);
		if(ans[p].any()) ans[p]&=s;
		else ans[p]=s; Ans[p]+=r-l+1;
	}
	for(int j=1;j<=num;j++)
		printf("%d\n",Ans[j]-ans[j].count()*3),ans[j].reset(),Ans[j]=0;
	for(;l<=r;) del(a[l++]);
}
map<int,int>mp;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i),h[i]=a[i];
	sort(h+1,h+1+n,less<int>());
	for(int i=1;i<=n;i++) if(!mp[h[i]]) mp[h[i]]=i;
	for(int i=1;i<=n;i++) a[i]=mp[[i]];
	len=pow(n,2./3);
	for(int i=1;i<=n;i++)
		b[i]=(i-1)/len+1;
	int i; for(i=1;i+M/3<=m;i+=M/3) solve(M/3); solve(m-i+1);
	
	return 0;
}
2024/4/12 17:45
加载中...