BZOJ

BZOJ 2141

传送门

正常的解法是树套树然而我不会 所以写了个分块

假设现在要交换$l$与$r$，使答案发生变化的只会出现在$l$之后$r$之前也就是$l,r$之间，只需要查询区间中的变化就行了

对于$(l,r)$中的一个$i$，若$h_i>h_l$或$h_i<h_r$，交换后会分别产生一对新的逆序对，逆序对减少时同理

这样就得到了暴力的方法，每次循环这个区间，判断$4$种情况即可

把序列分块，每块建个树状数组，对于每次修改，区间两边不满一块的暴力，整块的直接在树状数组里查

这题有元素重复的情况，离散化的时候需要注意一下

有空了把树套树的坑填了

UPD: 咕咕咕


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
program bzoj_2141;
type rec=record x,id:longint; end;
     arr=array[1..20000]of longint;
var bit:array[0..150]of arr;
    ll,rr:array[1..150]of longint;
    t:array[1..20000]of rec;
    a:array[1..20000]of longint;
    n,m,i,x,y,size,ans,tot,block:longint;

procedure swap(var a,b:longint);
var p:longint;
begin
  p:=a;
  a:=b;
  b:=p;
end;

function c(x:longint):longint;
begin
  exit(x and -x);
end;

procedure modify(var b:arr;p,d:longint);
begin
  while p<=tot do
  begin
    inc(b[p],d);
    inc(p,c(p));
  end;
end;

function query(var b:arr;p:longint):longint;
begin
  query:=0;
  while p>0 do
  begin
    inc(query,b[p]);
    dec(p,c(p));
  end;
end;

procedure qsort(l,r:longint);
var i,j:longint;
    mid,p:rec;
begin
  i:=l;
  j:=r;
  mid:=t[(l+r)>>1];
  repeat
    while t[i].x<mid.x do inc(i);
    while t[j].x>mid.x do dec(j);
    if i<=j then
    begin
      p:=t[i];
      t[i]:=t[j];
      t[j]:=p;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then qsort(i,r);
  if l<j then qsort(l,j);
end;

procedure update(t,l,r:longint);
begin
  dec(ans,ord(t<l)+ord(t>r));
  inc(ans,ord(t>l)+ord(t<r));
end;

procedure solve;
var l,r,i:longint;
begin
  if x>y then swap(x,y);
  l:=(x-1) div size+1;
  r:=(y-1) div size+1;
  if l<>r then
  begin
    for i:=x+1 to rr[l] do update(a[i],a[x],a[y]);
    for i:=ll[r] to y-1 do update(a[i],a[x],a[y]);
    for i:=l+1 to r-1 do
    begin
      dec(ans,query(bit[i],a[x]-1));
      inc(ans,query(bit[i],a[y]-1));
      inc(ans,query(bit[i],tot)-query(bit[i],a[x]));
      dec(ans,query(bit[i],tot)-query(bit[i],a[y]));
    end;
  end else for i:=x+1 to y-1 do update(a[i],a[x],a[y]);
  if a[x]<a[y] then inc(ans) else if a[x]>a[y] then dec(ans);
  writeln(ans);
  modify(bit[l],a[x],-1);
  modify(bit[l],a[y],1);
  modify(bit[r],a[y],-1);
  modify(bit[r],a[x],1);
  swap(a[x],a[y]);
end;

begin
  readln(n);
  for i:=1 to n do
  begin
    read(t[i].x);
    t[i].id:=i;
  end;
  qsort(1,n);
  tot:=0;
  for i:=1 to n do
  begin
    if (i=1)or(t[i].x<>t[i-1].x) then inc(tot);
    a[t[i].id]:=tot;
  end;
  ans:=0;
  size:=trunc(sqrt(n));
  block:=n div size;
  for i:=1 to n do
  begin
    inc(ans,query(bit[0],tot)-query(bit[0],a[i]));
    modify(bit[0],a[i],1);
    modify(bit[(i-1)div size+1],a[i],1);
  end;
  writeln(ans);
  for i:=1 to block do
  begin
    ll[i]:=(i-1)*size+1;
    rr[i]:=i*size;
  end;
  if n mod size<>0 then
  begin
    inc(block);
    ll[block]:=rr[block-1]+1;
    rr[block]:=n;
  end;
  readln(m);
  for i:=1 to m do
  begin
    readln(x,y);
    solve;
  end;
end.