膜拜大佬：https://blog.csdn.net/xyz32768/article/details/88831233

题目链接：

http://codeforces.com/contest/1139/problem/F

题意：

有n个物品，物品有三个属性分别是$p_i，s_i，b_i$

有m个人，人有两个属性分别是$pref_j$，$inc_j$

 

一个人能买某个物品必须满足:，

$p_i \leq inc_j \leq s_i$

$|b_i-pref_j| \leq (inc_j-p_i)$

 

数据范围：

$1 \leq n \leq 10^5$

$1 \leq m \leq 10^5$

其它都是$1$到$10^9$

分析： 

每次减边，然后对整体二分图匹配复杂度大概是$O\left ( n^{3} \right )$

于是想到逆序处理，从后往前处理，逆过程就是加边，由于加边后的ans肯定是递增的，所以复杂度降成$O\left ( n^{2} \right )$

如果用邻接矩阵复杂度是$O\left ( n^{3} \right )$用邻接表是$O\left (  n^{2} \right )$，因为对于二分图这道题的边数为$n$，属于稀疏图，所以用邻接表比较合适

ac代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct Node
{
    int is,id,x;
    bool operator <(const Node &a)const
    {
        if(x!=a.x)return x<a.x;
        else return is<a.is;
    }
};
int a[maxn*4],s[maxn],p[maxn],inc[maxn],b[maxn],treea[maxn*4],treeb[maxn*4],pb[maxn];
int ans[maxn];
map<int,int>ma;
int cnt=0,tt=0;
Node que[maxn*3];
int getid(int x)
{
    x=-x;
    return ma[x];
}
void add1(int x,int y)
{
    for(int i=x;i<4*maxn;i+=(i&-i))treea[i]+=y;
}
void add2(int x,int y)
{
    for(int i=x;i<4*maxn;i+=(i&-i))treeb[i]+=-y;
}
int quer1(int x)
{
    int res=0;
    for(int i=x;i>=1;i-=(i&-i))res+=treea[i];
    return res;
}
int quer2(int x)
{
    int res=0;
    for(int i=x;i>=1;i-=(i&-i))res+=treeb[i];
    return res;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&p[i]);
    for(int i=1;i<=n;i++)scanf("%d",&s[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=m;i++)scanf("%d",&inc[i]);
    for(int i=1;i<=m;i++)scanf("%d",&pb[i]);

    for(int i=1;i<=n;i++)
    {
        a[++cnt]=-(p[i]+b[i]-1),a[++cnt]=-(b[i]-p[i]);
        que[++tt]=Node{0,i,p[i]};
        que[++tt]=Node{2,i,s[i]};
    }

    for(int i=1;i<=m;i++)
    {
        a[++cnt]=-(inc[i]+pb[i]),a[++cnt]=-(pb[i]-inc[i]);
        que[++tt]=Node{1,i,inc[i]};
    }
    sort(que+1,que+1+tt);
    sort(a+1,a+cnt+1);
    int pz=1;
    for(int i=1;i<=cnt;i++)
        if(ma[a[i]]==0)ma[a[i]]=pz++;

    for(int i=1;i<=tt;i++)
    {

        Node now=que[i];
        if(now.is==0)
        {
            add1(getid(b[now.id]-p[now.id]),1);
            add2(getid(p[now.id]+b[now.id]-1),1);
        }
        else if(now.is==1)
        {
            ans[now.id]=quer1(getid(pb[now.id]-inc[now.id]))+quer2(getid(inc[now.id]+pb[now.id]));
        }
        else if(now.is==2)
        {
            add1(getid(b[now.id]-p[now.id]),-1);
            add2(getid(p[now.id]+b[now.id]-1),-1);
        }
    }
    for(int i=1;i<=m;i++)
    {
         printf("%d ",ans[i]);
    }
    return 0;
}