悬关,全 RE 求调
查看原帖
悬关,全 RE 求调
740333
Rannio楼主2025/8/1 15:59
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10000,M=33353;
int n,m;
int a[N],b[N],tot,res[N];
int lp=1,rp,len,cnt[N];
struct node{
	int l,r,lid,id;
}q[M*3];
bitset<N> bit1,ans[M];
void add(int x){bit1.set(x+cnt[x]);cnt[x]++;}
void del(int x){cnt[x]--;bit1.reset(x+cnt[x]);}
void move(int l,int r){
	while(lp<l) del(a[lp]),lp++;
	while(lp>l) lp--,add(a[lp]);
	while(rp<r) rp++,add(a[rp]);
	while(rp>r) del(a[rp]),rp--;
}
bool cmp(node x,node y){return x.lid==y.lid?x.r<y.r:x.lid<y.lid;}
void init(){
	memset(cnt,0,sizeof cnt);
	lp=1,rp=0,tot=0;
	bit1.reset();
}
void work(){
	if(!m) return ;
	int ii=0;
	for(;ii<M-10&&m;ii++){
		m--;
		int x_1,y_1,x_2,y_2,x_3,y_3;
		scanf("%lld%lld%lld%lld%lld%lld",&x_1,&y_1,&x_2,&y_2,&x_3,&y_3);
		q[++tot]={x_1,y_1,x_1/len+1,ii};
		q[++tot]={x_2,y_2,x_2/len+1,ii};
		q[++tot]={x_3,y_3,x_3/len+1,ii};
		res[ii]=y_1+y_2+y_3-x_1-x_2-x_3+3;
		ans[ii].set();
	}
	sort(q+1,q+tot+1,cmp);
	for(int i=1;i<=tot;i++){
		move(q[i].l,q[i].r);
		ans[q[i].id]&=bit1;
	}
	for(int i=0;i<ii;i++) printf("%lld\n",res[i]-(int)ans[i].count()*3ll);
	init();
}
signed main(){
	scanf("%lld%lld",&n,&m);
	len=ceil(sqrt(n))+1;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b;
	for(int i=1;i<=3;i++) work();
	return 0;
}
2025/8/1 15:59
加载中...