摘要:值域线段树合并

「POI2011」ROT-Tree Rotations

题面

题目分析

你呀,总能给我整出点新花样.jpg

首先可以确定的是子树内的任意交换对子树外的逆序对统计并不会造成影响.

所以我们对每个叶子节点建立值域线段树,向上合并的时候计算子树按是否交换计算逆序对就好了.

代码

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
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=1000010;
lxl n,NodeCnt,TreeCnt,root,swp[2];
lxl lson[big],rson[big],c[2][big<<4],sum[big<<4],val[big],segr[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
void modify(lxl &t,lxl l,lxl r,lxl x,lxl k)
{
if(!t)t=++NodeCnt;
if(l==r)return void(sum[t]+=k);
lxl mid((l+r)>>1);
if(x<=mid)modify(c[0][t],l,mid,x,k);
else modify(c[1][t],mid+1,r,x,k);
sum[t]=sum[c[0][t]]+sum[c[1][t]];
}
void merge(lxl &p,lxl &q,lxl l,lxl r)
{
// if(!p||!q)return void(p+q);
if(!q)return;
if(!p)return void(p=q);
if(l==r)return void(sum[p]+=sum[q]);
swp[0]+=sum[c[1][p]]*sum[c[0][q]],swp[1]+=sum[c[0][p]]*sum[c[1][q]];
lxl mid((l+r)>>1);
merge(c[0][p],c[0][q],l,mid),merge(c[1][p],c[1][q],mid+1,r);
sum[p]=sum[c[0][p]]+sum[c[1][p]];
}
void in(lxl &t)
{
t=++TreeCnt;
lxl x=read();
if(x)val[t]=x,modify(segr[t],1,n,val[t],1);
else in(lson[t]),in(rson[t]);
}
lxl work(lxl u)
{
if(val[u])return 0;
lxl tmp=work(lson[u])+work(rson[u]);
swp[0]=swp[1]=0;
merge(segr[lson[u]],segr[rson[u]],1,n),segr[u]=segr[lson[u]];
// if(lson[u]==3)debug(sum[segr[lson[u]]]),debug(sum[segr[rson[u]]]);
tmp+=std::min(swp[0],swp[1]);
return tmp;
}
int main(void)
{
n=read(),in(root);
printf("%lld\n",work(root));
return 0;
}