首页 > > 程序设计 > C/C++ >

【bzoj 3333】排队计划（线段树）

2018-06-17 23:47:41来源：未知阅读 ()

n个数，求一次逆序对。接着有m次修改操作，把每次输入的位置p的数之后<=它的数取出来，从小到大排序后再放回空位里，求逆序对。（N,M<=500,000 , Ai<=10^9）
思路：
1.往后修改就存后缀，而不是一般的前缀。存数 i 之后<=它的数的个数为s[i]，用于后续求逆序对。
2.修改时选出的数排序后，它们的 s[] 都清零了，也可以“删掉”它们了——更改其值为INF。
实现：
1.用树状数组（或线段树）求出初始的逆序对数 sum。
2.每次操作用线段树在p到n的区间内找到所有<=数p 的数，通过一次次找最小的数，sum减去它的 s[] 值，更改其值为INF来进行“删除”。
3.线段树中权值存最小的数的编号，这样方便直接找到它。一个个删点也不用担心超时，因为“删”了之后就不会找到它了，为O(n)，找最小的数为O(log n)，整个程序为O(n log n)的时间复杂度。

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 typedef long long LL;
  8  
  9 const LL N=500010,INF=(LL)1e9+100;
 10 LL n,m;
 11 LL b[N],s[N],c[N];
 12 struct node{LL l,r,lc,rc,id;}a[N*2];
 13 LL len=0;
 14 struct hp{LL x,t;}e[N];
 15  
 16 LL mmin(LL x,LL y)
 17 {   return x<y?x:y;   }
 18 LL cp(LL x,LL y)
 19 {   return b[x]<b[y]?x:y;   }
 20  
 21 void bt(LL l,LL r)
 22 {
 23     LL x=++len;
 24     a[x].l=l,a[x].r=r;
 25     a[x].lc=a[x].rc=-1;
 26     if (l==r) a[x].id=l;
 27     else a[x].id=0;
 28     if (l<r)
 29     {
 30       LL mid=(l+r)/2;
 31       a[x].lc=len+1,bt(l,mid);
 32       a[x].rc=len+1,bt(mid+1,r);
 33        
 34       LL lc=a[x].lc,rc=a[x].rc;
 35       a[x].id=cp(a[lc].id,a[rc].id);
 36     }
 37 }
 38 void change(LL x,LL p,LL id)
 39 {
 40     if (a[x].l==a[x].r) {a[x].id=n+1;return;}
 41     LL lc=a[x].lc,rc=a[x].rc,mid=(a[x].l+a[x].r)/2;
 42     if (p<=mid) change(lc,p,id);
 43     else change(rc,p,id);
 44     a[x].id=cp(a[lc].id,a[rc].id);
 45 }
 46 LL getmin(LL x,LL l,LL r)
 47 {
 48     if (a[x].l==l&&a[x].r==r) return a[x].id;
 49     LL lc=a[x].lc,rc=a[x].rc,mid=(a[x].l+a[x].r)/2;
 50     if (r<=mid) return getmin(lc,l,r);
 51     if (l>mid) return getmin(rc,l,r);
 52     return cp(getmin(lc,l,mid),getmin(rc,mid+1,r));
 53 }
 54  
 55 bool cmp(hp u,hp v)
 56 {   return u.x<v.x;   }
 57  
 58 LL lowbit(LL x) {return x&-x;}
 59 LL S(LL x)
 60 {
 61     LL h=0;
 62     for (LL i=x;i>=1;i-=lowbit(i))
 63       h+=c[i];
 64     return h;
 65 }
 66 void C(LL x)
 67 {   for (LL i=x;i<=n;i+=lowbit(i)) c[i]++;   }
 68  
 69 int main()
 70 {
 71     scanf("%lld%lld",&n,&m);
 72     for (LL i=1;i<=n;i++)
 73       scanf("%lld",&e[i].x),e[i].t=i;
 74     sort(e+1,e+1+n,cmp);
 75     LL x=0;
 76     e[0].x=INF;
 77     for (LL i=1;i<=n;i++)
 78     {
 79       if (e[i].x!=e[i-1].x) x++;
 80       b[e[i].t]=x;
 81     }
 82     b[n+1]=INF;
 83     LL sum=0;
 84     memset(c,0,sizeof(c));
 85     for (LL i=n;i>=1;i--)
 86     {
 87       s[i]=S(b[i]-1);
 88       sum+=s[i];
 89       C(b[i]);
 90     }
 91     printf("%lld\n",sum);
 92     bt(1,n);
 93     while (m--)
 94     {
 95       LL p;
 96       scanf("%lld",&p);
 97       LL t=b[p],k=getmin(1,p,n),h=0;
 98       while (b[k]<=t)
 99       {
100         h+=s[k];//
101         change(1,k,n+1);
102         k=getmin(1,p,n);
103       }
104       sum-=h;
105       printf("%lld\n",sum);
106     }
107     return 0;
108 }