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("%I64d%I64d",&n,&m);
72 for (LL i=1;i<=n;i++)
73 scanf("%I64d",&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("%I64d\n",sum);
92 bt(1,n);
93 while (m--)
94 {
95 LL p;
96 scanf("%I64d",&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("%I64d\n",sum);
106 }
107 return 0;
108 }
