bzoj1901

最新推荐文章于 2019-10-10 22:58:54 发布

weixinding

最新推荐文章于 2019-10-10 22:58:54 发布

阅读量1.7k

点赞数

文章标签： insert div build input output 算法

本文链接：https://blog.csdn.net/weixinding/article/details/7538251

版权

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。Q i j k 或者 C i tQ i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。

Input

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Output

Sample Input

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output

3
6

HINT

20%的数据中，m,n≤100;
40%的数据中，m,n≤1000;
100%的数据中，m,n≤10000。

无限仰慕WJMZBMR。

看了他的集训队论文给了我很大的启发。

预祝WJMZBMR大神进入国家队。

这个是支持修改的区间第k大问题。

首先想不修改的区间第k大问题，由于权值线段树可以进行四则运算，所以可以由两棵线段树相减得到一颗描述区间的线段树，然后log查询。

这个本质是前缀和。

前缀和修改为O(n)，查询为O(1)，修改实在是非常慢，而且对空间要求非常大，所以我们希望将修改和查询的耗时进行平衡。

说到可修改的前缀和，容易想到树状数组，所以按修改树状数组的方式修改logn棵线段树，查询的时候访问logn棵线段树在权值线段树上查询，修改时间复杂度O(log^2)，所需空间复杂度O(log^2)，查询与其相同。

虽然学到了新算法，但是破灭了一个梦想觉得很不高兴。

你看啊，函数式编程不就像世界线吗……我可以从一个世界线不断前行，也可以用电话微波炉回到过去进入别的世界线……但是这样无法体现世界线的收敛，也就是即使发送dmail让世界线走到分叉也能回到注定的世界线，可是树状数组解决了这个问题，但是完全不能体现啊……………………………………………………超~不~爽。

program bzoj1901;
var
  len,all,tot,n,m,i,j,k:longint;
  s,root:array [0..10001] of longint;
  new,dl:array [0..20001] of longint;
  que:array [0..10001] of record
                            t:char;
                            i,j,k:longint;
                          end;
  left,right,sum:array [0..4000001] of longint;

procedure swap (var a,b:longint);inline;
begin
  if a=b then exit;
  b:=a xor b;
  a:=a xor b;
  b:=a xor b;
end;

procedure qsort (s,e:longint);
var
  i,j,k:longint;
begin
  if s>=e then exit;
  i:=s;
  j:=e;
  k:=dl[(s+e) div 2];
  while i<=j do
    begin
      while dl[i]<k do inc(i);
      while dl[j]>k do dec(j);
      if i>j then break;
      swap(dl[i],dl[j]);
      inc(i);
      dec(j);
    end;
  qsort(s,j);
  qsort(i,e);
end;

function convert (now:longint):longint;inline;
var
  mid,s,e:longint;
begin
  s:=1;
  e:=all;
  while s<>e do
    begin
      mid:=(s+e) div 2;
      if new[mid]<now then s:=mid+1
                      else e:=mid;
    end;
  exit(s);
end;

procedure build (s,e,now:longint);
var
  mid:longint;
begin
  if s=e then exit;
  mid:=(s+e) div 2;
  inc(tot);
  left[now]:=tot;
  build(s,mid,tot);
  inc(tot);
  right[now]:=tot;
  build(mid+1,e,tot);
end;

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

procedure insert (p,w,x:longint);inline;
var
  l,r,last,now,mid:longint;
begin
  while x<=n do
    begin
      l:=1;
      r:=all;
      last:=root[x];
      inc(tot);
      root[x]:=tot;
      now:=tot;
      repeat
        sum[now]:=sum[last]+p;
        if l=r then break;
        mid:=(l+r) div 2;
        inc(tot);
        if w<=mid then
          begin
            left[now]:=tot;
            right[now]:=right[last];
            now:=tot;
            last:=left[last];
            r:=mid;
          end
                  else
          begin
            left[now]:=left[last];
            right[now]:=tot;
            now:=tot;
            last:=right[last];
            l:=mid+1;
          end;
      until false;
      x:=x+lowbit(x);
    end;
end;

function find (i,j,k:longint):longint;
var
  o,x,now,l,r,mid:longint;
begin
  len:=0;
  dec(i);
  while i>0 do
    begin
      inc(len);
      dl[len]:=-root[i];
      i:=i-lowbit(i);
    end;
  while j>0 do
    begin
      inc(len);
      dl[len]:=root[j];
      j:=j-lowbit(j);
    end;
  l:=1;
  r:=all;
  while l<>r do
    begin
      mid:=(l+r) div 2;
      now:=0;
      for i:=1 to len do
        begin
          o:=dl[i] div abs(dl[i]);
          x:=abs(dl[i]);
          now:=now+o*sum[left[x]];
        end;
      if now<k then
        begin
          k:=k-now;
          for i:=1 to len do
            begin
              o:=dl[i] div abs(dl[i]);
              x:=abs(dl[i]);
              dl[i]:=right[x]*o;
            end;
          l:=mid+1;
        end
               else
        begin
          for i:=1 to len do
            begin
              o:=dl[i] div abs(dl[i]);
              x:=abs(dl[i]);
              dl[i]:=left[x]*o;
            end;
          r:=mid;
        end;
    end;
  exit(l);
end;

begin
  readln(n,m);
  for i:=1 to n do
    begin
      read(s[i]);
      dl[i]:=s[i];
    end;
  readln;
  tot:=n;
  for i:=1 to m do
    begin
      read(que[i].t);
      if que[i].t='Q' then
        read(que[i].i,que[i].j,que[i].k)
                      else
        begin
          read(que[i].i,que[i].j);
          inc(tot);
          dl[tot]:=que[i].j;
        end;
      readln;
    end;
  qsort(1,tot);
  i:=1;
  while i<=tot do
    begin
      inc(all);
      new[all]:=dl[i];
      while dl[i]=new[all] do inc(i);
    end;
  for i:=1 to n do
    s[i]:=convert(s[i]);
  for i:=1 to m do
    if que[i].t='C' then
      que[i].j:=convert(que[i].j);
  tot:=0;
  build(1,all,0);
  for i:=1 to n do
    insert(1,s[i],i);
  for i:=1 to m do
    if que[i].t='Q' then
      writeln(new[find(que[i].i,que[i].j,que[i].k)])
                    else
      begin
        insert(-1,s[que[i].i],que[i].i);
        insert(1,que[i].j,que[i].i);
        s[que[i].i]:=que[i].j
      end;
end.