站外题,传进树状数组 Add 的 x 莫名其妙变 0 了。
#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