BZOJ

BZOJ 1901

不稳定的传送门

ZOJ传送门

想+写一上午，调一下午…关键是这题的离散化好恶心啊尼玛，一堆数组绕着绕着就晕了…QAQ

首先扯一个会MLE的解法

对于普通的不带修改的可持久化线段树，$root[i]$记载的是从$1$到$i$的所有更改

然后拿树状数组分组一下，让$root[i]$记载从$i-lowbit(i)$到$i$的所有更改，这样建树或修改的时间复杂度$O(n(\log_2n)^2)$

但是呢…这样的空间复杂度有点受不了…大概是$O(n(\log_2n)^2+m(\log_2n)^2)$，毫无疑问MLE 何况ZOJ卡了32M内存尼玛

正确的姿势是初始的建树按照正常的可持久化线段树建，然后每个修改再在树状数组套的可持久化线段树里改，这样的时间空间复杂度大概$O(n\log_2n+2m(\log_2n)^2)$，可以开得下了

如果开到最大情况大概是$6240000*3\approx 70M$，但实际的数据没出全是修改的情况，我只用$2240000$就够了…


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
program bzoj_1901;
var root,bit:array[0..50000]of longint;
    s:array[0..2240000]of record lc,rc,size:longint; end;
    q:array[1..10000]of record query:boolean; a,b,k:longint; end;
    a,p,b:array[1..60000]of longint;
    low:array[1..2,0..16]of longint;
    n,m,i,tot,len,l,lb:longint;
    c:char;

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

procedure calc_low(p,t:longint);
begin
  while p>0 do
  begin
    inc(low[t,0]);
    low[t,low[t,0]]:=bit[p];
    dec(p,lowbit(p));
  end;
end;

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

procedure modify(var t:longint;base,l,r,p,d:longint);
var mid:longint;
begin
  inc(tot);
  t:=tot;
  s[t]:=s[base];
  inc(s[t].size,d);
  if l=r then exit;
  mid:=(l+r)>>1;
  if p<=mid then modify(s[t].lc,s[base].lc,l,mid,p,d)
  else modify(s[t].rc,s[base].rc,mid+1,r,p,d);
end;

function query(a,b,l,r,k:longint):longint;
var i,t,mid:longint;
begin
  if l=r then exit(l);
  mid:=(l+r)>>1;
  t:=s[s[b].lc].size-s[s[a].lc].size;
  for i:=1 to low[1,0] do dec(t,s[s[low[1,i]].lc].size);
  for i:=1 to low[2,0] do inc(t,s[s[low[2,i]].lc].size);
  if t>=k then
  begin
    for i:=1 to low[1,0] do low[1,i]:=s[low[1,i]].lc;
    for i:=1 to low[2,0] do low[2,i]:=s[low[2,i]].lc;
    exit(query(s[a].lc,s[b].lc,l,mid,k));
  end else
  begin
    for i:=1 to low[1,0] do low[1,i]:=s[low[1,i]].rc;
    for i:=1 to low[2,0] do low[2,i]:=s[low[2,i]].rc;
    exit(query(s[a].rc,s[b].rc,mid+1,r,k-t));
  end;
end;

begin
  tot:=0;
  readln(n,m);
  for i:=1 to n do read(a[i]);
  readln;
  len:=n;
  for i:=1 to m do
  begin
    read(c);
    if c='Q' then readln(q[i].a,q[i].b,q[i].k) else
    begin
      readln(q[i].a,q[i].k);
      inc(len);
      a[len]:=q[i].k;
      q[i].b:=len;
    end;
    q[i].query:=(c='Q');
  end;
  for i:=1 to len do p[i]:=i;
  qsort(1,len);
  l:=0;
  for i:=1 to len do
  begin
    if (i=1)or(a[i]<>a[i-1]) then inc(l);
    b[p[i]]:=l;
    a[l]:=a[i];
  end;
  root[0]:=1;
  tot:=1;
  for i:=1 to n do modify(root[i],root[i-1],1,l,b[i],1);
  for i:=1 to m do if q[i].query then
  begin
    fillchar(low,sizeof(low),0);
    calc_low(q[i].a-1,1);
    calc_low(q[i].b,2);
    writeln(a[query(root[q[i].a-1],root[q[i].b],1,l,q[i].k)]);
  end else
  begin
    lb:=q[i].a;
    while lb<=n do
    begin
      modify(bit[lb],bit[lb],1,l,b[q[i].a],-1);
      modify(bit[lb],bit[lb],1,l,b[q[i].b],1);
      inc(lb,lowbit(lb));
    end;
    b[q[i].a]:=b[q[i].b];
  end;
end.

因为写裸题又被ZYK大爷D了 QAQ