「SCOI2016」美味-可持久化线段树

一家餐厅有 $n$ 道菜，编号 $1,\dots,n$ ，大家对第 $i$ 道菜的评价值为 $a_i(1 \leq i \leq n)$。有 $m$ 位顾客，第 $i$ 位顾客的期望值为 $b_i$，而他的偏好值为 $x_i$ 。因此，第 $i$ 位顾客认为第 $j$ 道菜的美味度为 $b_i\ \text{XOR}\ (a_j+x_i)$ ，$\text{XOR}$ 表示异或运算。

第 $i$ 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 $l_i$ 道到第 $r_i$ 道中选择。请你帮助他们找出最美味的菜。

链接

Luogu P3293

题解

我们观察到区间限制，很容易让我们想到主席树，再观察到异或运算、最大，很容易联想到 0/1 Trie 树。

所以我们就按照主席树的方法建一颗 0/1 可持久化 Trie 树。

如果没有 $x_i$ 的运算，上面的解法就可以解决了。我们直接按照 $a_j$ 从高往低每位贪心取反即可，但我们注意到有了一个 $(a_j + x_i)$ 的限制。

这个问题中，我们需要建立一个权值线段树（可持久化），再每位贪心，但是我们需要再线段树上把那一段找出来，然后再走向左右区间。

时间复杂度是两个 $log$ ，因为其特殊性不能在线段树上直接二分，因此复杂度：$O(m \log^2 10^5 )$。

代码

 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
#include <bits/stdc++.h>
using namespace std;

const int MAX = 210000;
const int MAXN = 210000,logn = 19;
int n,m,a[MAXN],rt[MAXN];

namespace prSegTree{
  int sumn[MAXN*logn],ls[MAXN*logn],rs[MAXN*logn],cnt;
  #define mid ((l+r)>>1)
  void update(int &nown,int pre,int l,int r,int pos,int v){
    nown = ++cnt;ls[nown] = ls[pre],rs[nown] = rs[pre],sumn[nown] = sumn[pre];
    if(l == r)
      sumn[nown] += v;
    else{
      if(pos <= mid) update(ls[nown],ls[pre],l,mid,pos,v);
      if(pos >= mid+1) update(rs[nown],rs[pre],mid+1,r,pos,v);
      sumn[nown] = sumn[ls[nown]] + sumn[rs[nown]];
    }
  }  
  int query(int nown,int l,int r,int ql,int qr){
    if(!nown) return 0;
    if(ql <= l && r <= qr){
      return sumn[nown];
    }
    else{
      int ans = 0;
      if(ql <= mid) ans += query(ls[nown],l,mid,ql,qr);
      if(qr >= mid+1) ans += query(rs[nown],mid+1,r,ql,qr);
      return ans;
    }
  }
  int query(int lx,int rx,int ql,int qr){
    ql = max(1,ql),qr = min(qr,MAX);
    if(ql > qr) return 0;
    return query(rx,1,MAX,ql,qr) - query(lx,1,MAX,ql,qr);
  }
}

void init(){
  scanf("%d %d",&n,&m);
  for(int i = 1;i<=n;i++)
    scanf("%d",&a[i]);
  for(int i = 1;i<=n;i++)
    prSegTree::update(rt[i],rt[i-1],1,MAX,a[i],1);
}

int query(int b,int x,int l,int r){
  int ans = 0,tmp = 0;
  for(int i = 20;i>=0;i--){//该考虑 (1<<i) 的位置
    if(b&(1<<i)){
      if(prSegTree::query(rt[l-1],rt[r],tmp-x,tmp+(1<<i)-x-1) > 0)
        ans += (1<<i);
      else
        tmp += (1<<i);
    }
    else{
      if(prSegTree::query(rt[l-1],rt[r],tmp+(1<<i)-x,tmp+(1<<(i+1))-x-1) > 0) 
        ans += (1<<i),tmp += (1<<i);
    }
  }
  return ans;
}

void solve(){
  for(int i = 1;i<=m;i++){
    int b,x,l,r;
    scanf("%d %d %d %d",&b,&x,&l,&r);
    printf("%d\n",query(b,x,l,r));
  }
}

int main(){
  init();
  solve();
  return 0;
}

「SCOI2016」美味-可持久化线段树

链接

题解

代码

See Also

Comments