1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
| #include<iostream>
#include<cstdio>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int N=100000+1000;
struct TreeInTree
{
#define mid ((now_l+now_r)>>1)
#define lson (now<<1)
#define rson (now<<11)
#define root son[r][1]
static const int M=N*25;
int fa[M],son[M][2],size[M],cnt[M],num[M],to;
inline void update(int x)
{
size[x]=size[son[x][0]]+size[son[x][1]]+cnt[x];
}
inline void rotate(int x,int type)
{
int y=fa[x],z=fa[y];
son[z][y==son[z][1]]=x,fa[x]=z;
son[y][!type]=son[x][type],fa[son[x][type]]=y;
son[x][type]=y,fa[y]=x;
update(y),update(x);
}
void splay(int x,int to)
{
while(fa[x]!=to)
{
if(x==son[fa[x]][fa[x]==son[fa[fa[x]]][1]] and fa[fa[x]]!=to)
rotate(fa[x],x==son[fa[x]][0]);
rotate(x,x==son[fa[x]][0]);
}
}
void Insert(int w,int r)
{
if(root==0)
{
root=++to,fa[root]=r;
num[root]=w,update(root);
return;
}
int now=root,last=root;
while(now!=0)
last=now,now=son[now][w>num[now]];
now=++to,fa[now]=last,son[last][w>num[last]]=now;
num[now]=w,update(now);
splay(now,r);
}
int Query1(int x,int r)
{
int now=root,ans=0;
while(now!=0)
{
if(num[now]>=x)
now=son[now][0];
else
{
if(num[now]>num[ans]) ans=now;
now=son[now][1];
}
}
if(ans==0) return 0;
splay(ans,r);
return size[son[ans][0]]+cnt[ans];
}
int Query2(int x,int r)
{
int now=root,ans=0;
num[0]=0x3f3f3f3f;
while(now!=0)
{
if(num[now]>x)
{
if(num[now]<num[ans]) ans=now;
now=son[now][0];
}
else
now=son[now][1];
}
num[0]=0;
if(ans==0) return 0;
splay(ans,r);
return size[son[ans][1]]+cnt[ans];
}
int t[N<<2];
void Build(int now,int now_l,int now_r)
{
t[now]=++to;
if(now_l==now_r) return;
Build(lson,now_l,mid);
Build(rson,mid+1,now_r);
}
inline void Insert2(int x,int w,int now,int now_l,int now_r)
{
Insert(w,t[now]);
if(now_l!=now_r)
{
if(x<=mid) Insert2(x,w,lson,now_l,mid);
else Insert2(x,w,rson,mid+1,now_r);
}
}
int Query3(int l,int r,int w,int type,int now,int now_l,int now_r)
{
if(now_l>=l and now_r<=r)
{
if(type==1) return Query1(w,t[now]);
else return Query2(w,t[now]);
}
int sum=0;
if(l<=mid) sum+=Query3(l,r,w,type,lson,now_l,mid);
if(r>mid) sum+=Query3(l,r,w,type,rson,mid+1,now_r);
return sum;
}
#undef mid
#undef lson
#undef rson
}tit;
int n,m,p[N],q[N],unOK[N];
long long ans[N];
int main()
{
freopen("3157.in","r",stdin);
freopen("3157.out","w",stdout);
int t=clock();
n=read(),m=read();
for(int i=1;i<=n;i++)
p[read()]=i;
for(int i=1;i<=m;i++)
q[i]=read(),unOK[q[i]]=true;
tit.Build(1,1,n);
for(int i=1;i<=n;i++)
if(unOK[i]==false)
{
tit.Insert2(p[i],i,1,1,n);
ans[m+1]+=tit.Query3(p[i],n,i,1,1,1,n)+tit.Query3(1,p[i],i,2,1,1,n);
}
for(int i=m;i>=1;i--)
{
tit.Insert2(p[q[i]],q[i],1,1,n);
ans[i]=ans[i+1]+tit.Query3(p[q[i]],n,q[i],1,1,1,n)+tit.Query3(1,p[q[i]],q[i],2,1,1,n);
}
for(int i=1;i<=m;i++)
printf("%lld\n",ans[i]);
cerr<<clock()-t<<endl;
return 0;
}
|
… 那咋搞啊。 那我上个线段树套权值线段树吧 然后又码了半个小时。 时空复杂度均为$O(n∗log2n)$ (这明显要MLE啊，问题是题解蜜汁能过) 可惜现实依旧苦感： 
难道，改数据了？ 接着，我copy了一发题解，交上去，A掉了… 到目前为止，我还是想不通为啥开同样的数组，他A了，我T了。难道说他外层套的树状数组可以有效减少空间的消耗？ 想不通，还请各位dalao赐教。
