MnZn求助
查看原帖
MnZn求助
147401
koishi_offical楼主2021/11/2 20:41

为什么会wa两个点啊QAQ

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct node 
  {
      int l,r;
  } f[N];
bool cmp(node x,node y)
  {
      if(x.r==y.r) return x.l>y.l;
      return x.r<y.r;
  }
int stk1[N],top1,stk2[N],top2;
int typ[N<<2],num;
int a[N<<2];
int minn[N<<4],lazy[N<<4];
int n,m;
void build(int k,int l,int r)
  {
      if(l==r) 
       {
           minn[k]=a[l];
           return;
       }
      int mid=l+r>>1;
      build(k<<1,l,mid);
      build(k<<1|1,mid+1,r);
      minn[k]=min(minn[k<<1],minn[k<<1|1]);
  }
void add(int k,int v)
  {
      minn[k]+=v;
      lazy[k]+=v;
  }
void pushdown(int k,int v)
  {
      if(!lazy[k]) return;
      add(k<<1,lazy[k]);
      add(k<<1|1,lazy[k]);
      lazy[k]=0;
  }
int query(int k,int l,int r,int x,int y)
  {
      if(l>y||r<x) return 0x3f3f3f3f;
      if(l>=x&&r<=y) return minn[k];
      pushdown(k,lazy[k]);
      int mid=l+r>>1;
      int ans=0x3f3f3f3f;
      if(x<=mid) ans=min(ans,query(k<<1,l,mid,x,y));
      if(y>mid) ans=min(ans,query(k<<1|1,mid+1,r,x,y));
      return ans;
  }
void change(int k,int l,int r,int x,int y,int v)
  {
      if(l>y||r<x) return;
      if(l>=x&&r<=y) 
        {
            add(k,v);
            return; 
        }
      pushdown(k,lazy[k]);
      int mid=l+r>>1;
      if(x<=mid) change(k<<1,l,mid,x,y,v);
      if(y>mid) change(k<<1|1,mid+1,r,x,y,v);
      minn[k]=min(minn[k<<1],minn[k<<1|1]);
  }
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
     {
         cin>>f[i].l>>f[i].r;
         typ[++num]=f[i].l;
         typ[++num]=f[i].r;
     }
    for(int i=1;i<=m;i++)
      {
          cin>>stk1[++top1]>>stk2[++top2];
          typ[++num]=stk1[top1];
      }
    sort(typ+1,typ+num+1);
    int maxn=unique(typ+1,typ+num+1)-typ-1;
    //cout<<num<<endl;
    for(int i=1;i<=n;i++)
      {
          f[i].l=lower_bound(typ+1,typ+maxn+1,f[i].l)-typ;
          f[i].r=lower_bound(typ+1,typ+maxn+1,f[i].r)-typ;
      }
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=m;i++)
      {
          int x=lower_bound(typ+1,typ+maxn+1,stk1[i])-typ;
          a[x]=min(a[x],max(stk2[i],0));
      }
    sort(f+1,f+n+1,cmp);
    build(1,1,maxn);
    int ans=0;
    for(int i=1;i<=n;i++)
      {
          if(query(1,1,maxn,f[i].l,f[i].r)>0) 
            {
              ans++;
              change(1,1,maxn,f[i].l,f[i].r,-1);
            }
      }
    cout<<ans;
}
2021/11/2 20:41
加载中...