记录编号	413756	评测结果	ETTTTTTTTT
题目名称	[JLOI 2013][HZOI 2016]删除物品	最终得分	0
用户昵称	Hzoi_QTY	是否通过	未通过
代码语言	C++	运行时间	9.000 s
提交时间	2017-06-12 15:08:36	内存使用	6.12 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
#define M 100005
#define inf 0x7fffffff
using namespace std;
int n1,n2,n,g[M],b[M],zz[M],t=0;
struct kuai
{
       int zb,h;
} c[M];
struct tree
{
       int l,r,h;
} a[M*4];
int read()
{
    int sum=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch<='9'&&ch>='0')
    {
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum;
}
int cmp(kuai a,kuai b)
{
    return  a.h>b.h;
}
void build(int l,int r,int x)
{
     a[x].l=l;a[x].r=r;
     if(l==r)
     {
          a[x].h=1;
          return;
     }
     int mid=(l+r)/2;
     build(l,mid,x*2);
     build(mid+1,r,x*2+1);
     a[x].h=a[x*2].h+a[x*2+1].h;
}
void change(int l,int x)
{
     if(a[x].l==a[x].r)
     {
          a[x].h=0;
          return;
     }
     int mid=(a[x].l+a[x].r)/2;
     if(l<=mid)
         change(l,x*2);
     else
         change(l,x*2+1);
     a[x].h=a[x*2].h+a[x*2+1].h;
}
int q(int l,int r,int x)
{
    if(l<=a[x].l&&r>=a[x].r)
    {
        return a[x].h;
    }
    int mid=(a[x].l+a[x].r)/2,s=0;
    if(l<=mid)
       s+=q(l,r,x*2);
    if(mid<r)
        s+=q(l,r,x*2+1);
    return s;
}
int main()
{
    freopen("remove.in","r",stdin);
    freopen("remove.out","w",stdout);
   n1=read();n2=read();
   n=n1+n2;
   for(int i=1;i<=n1;i++)
      g[i]=read();
   for(int i=1;i<=n2;i++)
      b[i]=read();
   for(int i=1;i<=n1;i++)
     zz[n1-i+1]=g[i];
   for(int i=1;i<=n2;i++)
      zz[n1+i]=b[i];
   for(int i=1;i<=n;i++)
       c[i].zb=i,c[i].h=zz[i];
   sort(c+1,c+n+1,cmp);
   build(1,n,1);
   if(c[1].zb>n1)
      t=c[1].zb-n1-1;
   else
      t=n1-c[1].zb;
   change(c[1].zb,1);
   for(int i=2;i<=n;i++)
   {
        if(c[i-1].zb>c[i].zb)
        {
            int k=q(c[i].zb,c[i-1].zb,1);           
            t+=k-1;
        }
        else
        {
            int k=q(c[i-1].zb,c[i].zb,1);
            t+=k-1;
        }
        change(c[i].zb,1);
   }
   cout<<t;
  // while(1);
}