首页 > 其他分享 >题解:[SCOI2016] 美味

题解:[SCOI2016] 美味

时间:2024-11-12 19:51:35浏览次数:1  
标签:10 le int 题解 线段 ans SCOI2016 美味

前置知识:可持久化线段树(主席树)

洛谷3293 [SCOI2016] 美味

问题

有一个长度为 \(n\) 的序列 \(a_1,a_2,...,a_n\)。每次询问给你 \(b\)、\(x\),你需要求出 \(\max\{a_i+x \bigoplus b\}\)。

\(1 \le l \le r \le n \le 2\times 10^5, 0 \le a_i,b,x < 10^5\)

首先,有 \(l,r\) 应该要可持久化。然后……01trie?行不通啊。

没有头绪的话,先来看一道比较经典的题。

经典の问题

有一个长度为 \(n\) 的数列 \(a_1,a_2,...,a_n\)。有 \(m\) 次询问,给你一个数 \(k\),求出 \(k \bigoplus a_i\) 最大的 \(a_i\)。
\(1 \le n,m,a_i \le 10^5\)

你肯定知道这是 01Trie 板子,但是我想介绍另一个东西——

Technology

还是考虑贪心,从高位往低位贪。

假设 \(w_x(i)\) 表示数 \(x\) 二进制下的第 \(i\) 位,当前的答案(即确定了前几位)是 \(ans\)。

以一个例子来说明:

  k:  01100100101
ans:  1010???????

假如我们当前已经考虑完了前 \(4\) 位(从高往低),那我们肯定想要让 \(w_{ans}(5) \ne w_k(5)\),即 \(w_{ans}(5) = 1\)。那我们怎么知道是否存在这样的 \(ans\)?显然,此时需要满足的是:\((10101000000)_2 \le ans \le (10101111111)_2\)。权值线段树上查即可。

那么再来看这个题大家就都会做了,把范围再缩小 \(x\) 就行。由于需要限制区间,将权值线段树可持久化即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define lson son[u][0]
#define rson son[u][1]
const int N = 2e5 + 5, ND = N << 6;
struct segtree
{
    int tot, son[ND][2], cnt[ND];
    void pushup(int u)
    {
        cnt[u] = cnt[lson] + cnt[rson];
    }
    int update(int v, int l, int r, int it)
    {
        int u = ++tot;
        if (l == r)
        {
            cnt[u] = cnt[v] + 1;
            return u;
        }
        lson = son[v][0], rson = son[v][1];
        int mid = (l + r) >> 1;
        if (it <= mid)
            lson = update(son[v][0], l, mid, it);
        else
            rson = update(son[v][1], mid + 1, r, it);
        pushup(u);
        return u;
    }
    int query(int u, int l, int r, int L, int R)
    {
        if (L <= l && r <= R)
            return cnt[u];
        if (R < l || r < L)
            return 0;
        int mid = (l + r) >> 1;
        return query(lson, l, mid, L, R) + query(rson, mid + 1, r, L, R);
    }
} t;
int n, Q, a[N], root[N];
/*
if b_i == 0
    a in [ans + (1 << i) - x, ans + (1 << i + 1) - 1 - x]
else
    a in [ans - x, ans + (1 << i) - 1 - x]
*/

int main()
{
#ifdef aquazhao
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    cin >> n >> Q;
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i), root[i] = t.update(root[i - 1], 0, 1e5, a[i]);
    int b, x, l, r;
    while (Q--)
    {
        scanf("%d%d%d%d", &b, &x, &l, &r);
        int ans = 0;
        for (int i = 17; i >= 0; i--)
        {
            int cnt;
            if (!(b & (1 << i)))
            {
                int L = max(0, ans + (1 << i) - x), R = min((int)1e5, ans + (1 << (i + 1)) - 1 - x);
                cnt = t.query(root[r], 0, 1e5, L, R) - t.query(root[l - 1], 0, 1e5, L, R);
                ans += cnt > 0 ? 1 << i : 0;
            }
            else
            {
                int L = max(0, ans - x), R = min((int)1e5, ans + (1 << i) - 1 - x);
                cnt = t.query(root[r], 0, 1e5, L, R) - t.query(root[l - 1], 0, 1e5, L, R);
                ans += cnt > 0 ? 0 : 1 << i;
            }
        }
        printf("%d\n", b ^ ans);
    }
    return 0;
}

标签:10,le,int,题解,线段,ans,SCOI2016,美味
From: https://www.cnblogs.com/avalaunch/p/18542507

相关文章

  • AtCoder Beginner Contest 378 题解
    AtCoderBeginnerContest378题解比赛链接A-Pairing贪心#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidShowball(){vector<int>a(5);for(inti=0;i<4;i++){intx;cin>>x;a[x]++;......
  • 题解:[XIX Open Cup, Grand Prix of Korea] Dev, Please Add This!
    前置知识:2-SAT题意[XIXOpenCup,GrandPrixofKorea]Dev,PleaseAddThis!在一张网格上有以下几种物品:空地(.)墙(#)星星(*)一个球(O)现在你要玩一个游戏。你可以让球朝上下左右某一个方向移动,但是一旦移动就必须走到底,也就是说直到前面是墙或者边界才能停。另外,如果你走......
  • 【题解】洛谷P7286:「EZEC-5」人赢
    P7286「EZEC-5」人赢可以想到对于每个数要找到比他大的数中下标最大的数,我们按照数的大小排序,我们维护原序列的一个指针,对于每个数如果比指针大那么就左移指针,可以思考下为什么:指针上的数比现在这个数要小那比后面的数都小,于是我们左移指针直到大于这个数,可以发现我们也在一直......
  • 【题解】洛谷P8346:最澄澈的空与海
    【题解】洛谷P8346:最澄澈的空与海猜结论题,本身其实很简单,在纸上画个差不多就能想出来,我一开始想二分图最大匹配,但是还是太大了,不可以。当一个二分图有且仅有一种解时,必定有节点的入度为\(1\)。我们想到有多种匹配的情况,可以想到如果这是一个环的情况,一个左边的点将他右边的点......
  • MX-S5 T1~T2 题解
    MX-S5题解A.王国边缘题目链接见到循环结构,先把下标转成从\(0\)开始,以方便用同余描述位置。倍增。用二元组来表示位置:\((u,v)\)表示第\(u\)个循环节的第\(v\)个位置。设\(f(i,j)\)表示从位置\((0,i)\)开始跳\(2^j\)次以后的位置。假设已经可以初始化\(f(i,......
  • CF 705 题解
    CF705题解AHulk模拟即可.BSpiderMan打sg表可以发现,奇数个球先手必败(sg=0),偶数先手必胜(sg=1).多个组合只要把sg值异或起来就好.CThor暴力模拟就可以了,用队列模拟.DAntMan结论:按照编号由小到大加入链表,每次尽量让答案最小贪心就是对的.若原来是......
  • 题解:洛谷 P5180 【模板】支配树
    在图论模拟赛被T4的有向图必经点硬控了\(10^9+7s\),写篇题解纪念一下。其实,求有向图的必经点,通法就是支配树。一些定义:支配点:在确定起点\(S\)的情况下,对于一个点\(k\),若存在\(x\),使得删除\(x\)以及与\(x\)连接的边后,\(x\)与\(k\),不再强连通,那么就称\(k\)为\(x......
  • 【题解】洛谷P3118: Moovie Mooving G
    洛谷P3118:MoovieMoovingG看到数据范围考虑状压,题目要求看的电影最少那就维护时间最大,我们设\(f_{i}\)为\(i\)状态最多可以看多久的电影,对于不在集合的点我们枚举转移。我们每个开始时间都对应一个截至时间,问能加入这个点,每个点花费时间是固定的,我们又要不间断所以我们找......
  • CF785D 题解
    CF题目luogu题目题解似乎清一色是同一个做法,这里给一个容斥的做法。首先枚举一个位置\(i\),设\([1,i]\)的左括号个数为\(p\),\([i+1,n]\)的右括号个数为\(q\),那么以\(i\)这个位置为分界点的合法括号数有\(\sum_{i=1}^{\min(p,q)}C_p^iC_q^i\)个。通过范德蒙德卷......
  • CF 1325 题解
    CF1325题解AEhAbAnDgCd有\(\gcd(1,x)=1,\text{lcm}(1,x)=x\),因此输出\(1x\).BCopyCopyCopyCopyCopy要求严格上升子序列,那么答案的上界当然是去重后的元素个数.能否取到上界呢?当然可以,每一段内选一个你想要的就可以了.CEhabandPath-eticMEXs发现\(0,......