关于值传递求助
  • 板块学术版
  • 楼主Nazq
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/5 17:35
  • 上次更新2025/1/5 17:55:49
查看原帖
关于值传递求助
1051166
Nazq楼主2025/1/5 17:35

站外题,传进树状数组 Addxx 莫名其妙变 00 了。

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5,V=1e6+5;
struct node{
	int l,r;
}a[N];
bool cmpA(const node &a,const node &b){
	if(a.r!=b.r)return a.r<b.r;
	return a.l>b.l;
}
struct node2{
	int l,r,id;
}q[N<<1];
bool cmpB(const node2 &a,const node2 &b){
	if(a.r!=b.r)return a.r<b.r;
	return a.l>b.l;
}
int n,m,ans[N],cnt,len;
int t[V];

void Add(int x,int k){//
	while(x<=len){
		t[x]+=k;
		x+=x&-x;
	}
}
int Ask(int x){
	int ret=0;
	while(x){
		ret+=t[x];
		x-=x&-x;
	}
	return ret;
}
int main(){
	while(~scanf("%d%d",&n,&m)){
		len=0;
		for(int i=1;i<=n;++i){
			scanf("%d%d",&a[i].l,&a[i].r);
			len=max(len,a[i].l);
		}
		cnt=0;
		for(int i=1,c;i<=m;++i){
			scanf("%d",&c);
			int p,lst=0;
			while(c--){
				scanf("%d",&p);
				if(lst+1<=p-1)
					q[++cnt]=(node2){lst+1,p-1,i};
				lst=p;
			}
			if(lst+1<=len)
				q[++cnt]=(node2){lst+1,len,i};
		}
		sort(a+1,a+n+1,cmpA);
		sort(q+1,q+cnt+1,cmpB);

		for(int i=1;i<=m;++i)
			ans[i]=0;

		int l=1;
		for(int i=1;i<=cnt;++i){
			while(l<=n&&a[l].r<=q[i].r){
				if(a[l].l==0)//
					printf("%d\n",a[l].r);
				else Add(a[l].l,1);
				++l;
			}
			if(q[i].l<=len)
				ans[q[i].id]+=Ask(len)-Ask(q[i].l-1);
		}

		while(l)Add(a[l--].l,-1);
		for(int i=1;i<=m;++i)
			printf("%d\n",n-ans[i]);
	}
	return 0;
}

3 3
1 3
4 5
6 7
3 1 4 7
2 4 5
1 8
2025/1/5 17:35
加载中...