作为一个数据结构学傻了的蒟蒻,我翻出了原来的线段树套平衡树，改了一下后开O2，3456msAC了
累死我了 =_=
请忽略那鬼畜的封装平衡树，这是一个叫做zyf树的奇怪东西，改成其他平衡树应该会快一些的
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,root;
int cnt,cur,ans;
int ls[1010101],rs[1010101],a[50010];
struct hh{int v,sz,lson,rson;}tr[101010<<7];
struct zyf_tree
{
int root;
bool leaf(int x){return !(tr[x].lson||tr[x].rson);}
void new_tr(int &k,int x)
{
k=++cnt;
tr[k].v=x;
tr[k].sz=1;
}
void push_up(int x)
{
if (leaf(x)) return;
tr[x].v=max(tr[tr[x].lson].v,tr[tr[x].rson].v);
tr[x].sz=tr[tr[x].lson].sz+tr[tr[x].rson].sz;
}
void rotate(int k,bool dir)
{
if (!dir)
{
int r=tr[k].rson;
tr[k].rson=tr[k].lson;
tr[k].lson=tr[tr[k].rson].lson;
tr[tr[k].rson].lson=tr[tr[k].rson].rson;
tr[tr[k].rson].rson=r;
push_up(tr[k].lson);
push_up(tr[k].rson);
}
else
{
int l=tr[k].lson;
tr[k].lson=tr[k].rson;
tr[k].rson=tr[tr[k].lson].rson;
tr[tr[k].lson].rson=tr[tr[k].lson].lson;
tr[tr[k].lson].lson=l;
push_up(tr[k].lson);
push_up(tr[k].rson);
}
}
void maintain(int k)
{
if (leaf(k)) return;
if (tr[tr[k].lson].sz>=tr[tr[k].rson].sz*4) rotate(k,0);
if (tr[tr[k].rson].sz>=tr[tr[k].lson].sz*4) rotate(k,1);
}
void insert(int &k,int x)
{
if (!k)
{
new_tr(k,x);
return;
}
if (leaf(k))
{
new_tr(tr[k].lson,min(x,tr[k].v));
new_tr(tr[k].rson,max(x,tr[k].v));
push_up(k);
return;
}
int l=tr[tr[k].lson].v;
if (x>l) insert(tr[k].rson,x);
else insert(tr[k].lson,x);
maintain(k);
push_up(k);
}
int rnk(int k,int x)
{
if (leaf(k))
{
if (x>tr[k].v) return 1;
return 0;
}
int l=tr[tr[k].lson].v;
if (x>l) return rnk(tr[k].rson,x)+tr[tr[k].lson].sz;
return rnk(tr[k].lson,x);
}
}zyf[1010101];
void insert(int &k,int l,int r,int pos,int x)
{
if (!k) k=++cur;
zyf[k].insert(zyf[k].root,x);
if (l==r) return;
int mid=(l+r)>>1;
if (pos<=mid) insert(ls[k],l,mid,pos,x);
else insert(rs[k],mid+1,r,pos,x);
}
void rnk(int k,int l,int r,int x,int y,int woc)
{
if (!k) return;
if (x<=l&&r<=y)
{
ans+=zyf[k].rnk(zyf[k].root,woc);
return;
}
int mid=(l+r)>>1;
if (x<=mid) rnk(ls[k],l,mid,x,y,woc);
if (y>mid) rnk(rs[k],mid+1,r,x,y,woc);
}
inline int read()
{
char ch=getchar();
int ret=0;
while (ch>'9'||ch<'0') ch=getchar();
while ('0'<=ch&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret;
}
#define sz 101010
#define ll long long
ll lastans;
ll Tr[sz];
inline void ADD(int x){while (x<=n) Tr[x]++,x+=(x&-x);}
inline ll Q(int x){int ret=0;while (x) ret+=Tr[x],x-=(x&-x);return ret;}
int place[sz];
int QUERY[sz>>1],A[sz];
bool cut[sz];
ll Ans[sz>>1];
ll tr1[sz];
inline void ADD1(int x){while (x<=n) tr1[x]++,x+=(x&-x);}
inline ll Q1(int x){int ret=0;while (x) ret+=tr1[x],x-=(x&-x);return ret;}
int main()
{
register int i;
register ll x;
n=read();m=read();
for (i=1;i<=n;i++)
{
A[i]=read();
place[A[i]]=i;
}
for (i=1;i<=m;i++) QUERY[i]=x=read(),cut[x]=1;
for (i=1;i<=n;i++) if (!cut[A[i]])
{
lastans+=Q(n)-Q(A[i]);
insert(root,1,n,i,A[i]);
ADD(A[i]);
ADD1(i);
}
for (i=m;i;--i)
{
x=QUERY[i];ans=0;
rnk(root,1,n,1,place[x],x+1);
lastans+=Q1(place[x])-ans;
ans=0;
rnk(root,1,n,place[x]+1,n,x);
lastans+=ans;
Ans[i]=lastans;
insert(root,1,n,place[x],x);
ADD1(place[x]);
}
for(i=1;i<=m;i++) printf("%lld\n",Ans[i]);
}
```
by p_b_p_b @ 2018-05-13 11:42:48
%%%%%%%%
by ylxmf2020 @ 2018-05-13 12:44:41