写的线段树二分,不知道哪里错了,WA on 28,AT现在下不了数据也,帮我调一下,谢谢
#include<bits/stdc++.h>
#define MAXN 1000005
int gi(){
char c;int x=0,f=0;
while(!isdigit(c=getchar()))f|=(c=='-');
while(isdigit(c))x=(x*10)+(c^48),c=getchar();
return f?-x:x;
}
std::mt19937 rnd(std::random_device{}());
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
int n,l[MAXN],r[MAXN],m,ans[MAXN];
struct Q{int x,id;}q[MAXN];
namespace segtree{
#define ls x<<1
#define rs x<<1|1
#define mid ((l+r)>>1)
int mx[MAXN<<2],tag[MAXN<<2],mn[MAXN<<2];
void up(int x){mx[x]=std::max(mx[ls],mx[rs]);mn[x]=std::min(mn[ls],mn[rs]);}
void addtag(int x,int w){mx[x]+=w,mn[x]+=w,tag[x]+=w;}
void down(int x){
if(!tag[x])return;
addtag(ls,tag[x]),addtag(rs,tag[x]);
tag[x]=0;
}
void build(int x,int l,int r){
if(l==r)return mx[x]=mn[x]=q[l].x,void();
build(ls,l,mid),build(rs,mid+1,r);
up(x);
}
int find(int x,int l,int r,int p){ //找到线段树中第一个大于等于p的
if(l==r)return l;
down(x);
if(mx[ls]>=p)return find(ls,l,mid,p);
else if(mx[rs]>=p)return find(rs,mid+1,r,p);
return -1;
}
int find2(int x,int l,int r,int p){ //找到线段树中最后一个小于等于p的
if(l==r)return l;
down(x);
if(mn[rs]<=p)return find2(rs,mid+1,r,p);
else if(mn[ls]<=p)return find2(ls,l,mid,p);
return -1;
}
void upd(int x,int l,int r,int ql,int qr,int w){
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr)return addtag(x,w);
down(x);
if(ql<=mid)upd(ls,l,mid,ql,qr,w);
if(mid<qr)upd(rs,mid+1,r,ql,qr,w);
up(x);
}
int query(int x,int l,int r,int p){
if(l==r)return mx[x];
down(x);
return p<=mid?query(ls,l,mid,p):query(rs,mid+1,r,p);
}
#undef ls
#undef rs
#undef mid
}
using namespace segtree;
int main(){
n=gi();
for(int i=1;i<=n;i++)l[i]=gi(),r[i]=gi();
m=gi();
for(int i=1,x;i<=m;i++)x=gi(),q[i]=(Q){x,i};
std::sort(q+1,q+m+1,[&](Q i,Q j){return i.x<j.x;});
build(1,1,m);
for(int i=1;i<=n;i++){
int L=find(1,1,m,l[i]),R=find2(1,1,m,r[i]);
if(L<=R&&L>=1&&R>=1&&L<=m&&R<=m)upd(1,1,m,L,R,1);
}
for(int i=1;i<=m;i++)ans[q[i].id]=query(1,1,m,i);
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}