首页 > 其他分享 >无限酒店 题解

无限酒店 题解

时间:2024-02-17 20:11:34浏览次数:23  
标签:酒店 return int 题解 间隔 起始 mid 无限 id

题目链接

由于间隔不变,对于下面 \(3\) 个操作,只需记录起始位置与间隔即可。

对于无数人到达酒店:所有位置的起始点 \(\times 2\),间隔 \(\times2\),新的团队起始点为 \(1\),间隔为 \(2\)。

对于 \(k\) 个人到达酒店:所有点的起始点 \(+k\) ,间隔不变,新的团队起始点为 \(0\),间隔为 \(1\)。

对于查询 \(g\) 团队的第 \(x\) 个人:找到起始点的坐标用间隔计算即可。

考虑如何实现查询位置 \(x\) 的所属团队。

从现在往前撤销加法或乘法操作。假设最后一个操作是乘法,那么如果位置 \(x\) 是奇数答案就是这个操作的团队编号。否则,撤销这个乘法操作,等价于将 \(x\) 除以 \(2\) 。现在最后是连续的一段加法操作,用前缀和 \(\mathcal O(1)\) 撤销这段操作即可。如果小于这个加法段,二分查找即可。发现每次撤销完连续加法操作,\(x\) 要么除以 \(2\) 要么退出循环,至多执行 \(30\) 次。

考场上本来过了这道题,但因为查询 \(g\) 团队的第 \(x\) 个人中的 \(g\) 可以为 \(0\),所以线段树要从 \(0\) 开始加而光荣爆 \(0\)。吐槽大样例没有这样的情况而数据全是这样的情况。

#define int ll
const int N = 3e5 + 5, p = 1e9 + 7;
struct segment_tree
{
    int add[N << 2], mul[N << 2], sum[N << 2];
    void pushup(int id) {
        sum[id] = sum[id << 1] + sum[id << 1 | 1];
    }
    void pushdown(int id, int l, int r, int mid) {
        if (mul[id] ^ 1) {
            mul[id << 1] *= mul[id], mul[id << 1 | 1] *= mul[id];
            mul[id << 1] %= p, mul[id << 1 | 1] %= p;
            add[id << 1] *= mul[id], add[id << 1 | 1] *= mul[id];
            add[id << 1] %= p, add[id << 1 | 1] %= p;
            sum[id << 1] *= mul[id], sum[id << 1 | 1] *= mul[id];
            sum[id << 1] %= p, sum[id << 1 | 1] %= p;
            mul[id] = 1;
        }
        if (add[id]) {
            sum[id << 1] += (mid - l + 1) * add[id], sum[id << 1 | 1] += (r - mid) * add[id];
            sum[id << 1] %= p, sum[id << 1 | 1] %= p;
            add[id << 1] += add[id], add[id << 1 | 1] += add[id];
            add[id << 1] %= p, add[id << 1 | 1] %= p;
            add[id] = 0;
        }
    }
    void tadd(int l, int r, int x, int y, int k, int id) {
        if (l > y || r < x) return ;
        if (l >= x && r <= y) return sum[id] += (r - l + 1) * k, add[id] += k, sum[id] %= p, void();
        int mid = l + r >> 1;
        pushdown(id, l, r, mid);
        tadd(l, mid, x, y, k, id << 1), tadd(mid + 1, r, x, y, k, id << 1 | 1);
        pushup(id);
    }
    void tmul(int l, int r, int x, int y, int k, int id) {
        if (l > y || r < x) return ;
        if (l >= x && r <= y) return add[id] *= k, mul[id] *= k, sum[id] *= k, add[id] %= p, mul[id] %= p, sum[id] %= p, void();
        int mid = l + r >> 1;
        pushdown(id, l, r, mid);
        tmul(l, mid, x, y, k, id << 1), tmul(mid + 1, r, x, y, k, id << 1 | 1);
        pushup(id);
    }
    int query(int l, int r, int x, int y, int id) {
        if (l > y || r < x) return 0;
        if (l >= x && r <= y) return sum[id];
        int mid = l + r >> 1;
        pushdown(id, l, r, mid);
        return (query(l, mid, x, y, id << 1) + query(mid + 1, r, x, y, id << 1 | 1)) % p;
    }
} T1, T2;
int Q, pos[N], tot, cnt, n, s[N];
signed main() 
{
    // freopen("ex_hotel2.in", "r", stdin);
    // freopen("my2.out", "w", stdout);
    read(Q);
    n = Q;
    // T1 : 起始点
    // T2 : 间隔
    T2.tadd(0, n, 0, 0, 1, 1);
    while (Q--)
    {
        int op, x, y;
        read(op, x);
        if (op == 1) 
        {
            ++tot;
            s[tot] = s[tot - 1] + x;
            if (x == 0)
            {
                pos[++cnt] = tot;
                T1.tmul(0, n, 0, tot - 1, 2, 1);
                T2.tmul(0, n, 0, tot - 1, 2, 1);
                T1.tadd(0, n, tot, tot, 1, 1);
                T2.tadd(0, n, tot, tot, 2, 1);
            }
            else
            {
                T1.tadd(0, n, 0, tot - 1, x, 1);
                T2.tadd(0, n, tot, tot, 1, 1);
            }
        }
        else if (op == 2)
        {
            read(y);
            int st = T1.query(0, n, x, x, 1); // 起始点
            int dis = T2.query(0, n, x, x, 1); // 间距
            write((st + (y - 1) * dis % p) % p), ptc('\n');
        }
        else
        {
            int now = tot;
            int k = x;
            bool flg = 0;
            for (int i = cnt; i >= 0; now = pos[i], --i)
            {
                int tmp = s[now] - s[pos[i]];
                // cout << tmp << endl;
                if (k >= tmp)
                {
                    k -= tmp;
                    if (k % 2 == 1) 
                    {
                        write(pos[i]), ptc('\n');
                        flg = 1;
                        break;
                    }
                    else
                    {
                        k /= 2;
                    }
                }
                else
                {
                    int l = pos[i], r = now;
                    // cout << l << ' ' << r << endl;
                    while (l < r)
                    {
                        int mid = l + r >> 1;
                        if (k < s[now] - s[mid]) l = mid + 1;
                        else r = mid;
                    }
                    write(l), ptc('\n');
                    flg = 1;
                    break;
                }
            }
            if (!flg) puts("0");
        }
    }
    return 0;
}

标签:酒店,return,int,题解,间隔,起始,mid,无限,id
From: https://www.cnblogs.com/cyyhcyyh/p/18018302

相关文章

  • CF1365G Secure Password 题解
    Description本题是交互题。有一个固定的数组\(A\),同时通过数组\(A\)构造出数组\(P\),具体来讲,\(P_i\)是\(A\)中除\(A_i\)外的所有元素的按位或。你需要在最多\(13\)次询问中得到最后的\(P\)数组。\(2\leqn\leq1000\)。Solution首先有一个\(2\logn\)的是注......
  • 传纸条 题解
    题目描述小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排做成一个m行n列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵......
  • 2024.2.17模拟赛T1题解
    先考虑\(q=(1...n)\)的情况:发现如果设\(divcnt(p)\)表示将\(p\)划分为极小值域连续段的个数,那满足\(divcnt(p)\gem\)的排列都是合法的。那现在要求出有多少个排列符合条件可以先算出长度为\(i\),\(divnct\)为\(1\)的排列个数,这可以用dp解决然后再背包一下,就能求......
  • P2042 [NOI2005] 维护数列 题解
    题目链接:维护数列比较不好码的题,首先确保自己会一种文艺平衡树的书写,这点因人而异,比较推荐初学者学\(fhq\)平衡树,坑比较少,比较好码,写平衡树合并、持久化类的题时,也比较好写。注意到空间需求比较大,还涉及删除,我们的删除用各种树类数据结构中最常用的回收标记用于新的节点开辟。......
  • CF1929E 题解
    题意:给定一棵\(n\)个节点数和\(k\)条路径\((a_i,b_i)\),求至少将多少条边染色,使得给定路径都至少有一条染色的边。\(n\le10^5,k\le20\)。思路:好题。显然状压\(dp\),\(dp[S]\)表示至少染多少条边使得\(S\)中的路径都满足条件。正常思路是枚举子集转移,考虑\(T\s......
  • 整数划分 题解
    题目描述如何把一个正整数N(N长度<20)划分为M(M>1)个部分,使这M个部分的乘积最大。N、M从键盘输入,输出最大值及一种划分方式。输入格式第一行一个正整数T(T<=10000),表示有T组数据。接下来T行每行两个正整数N,M。输出格式对于每组数据第一行输出最大值。第二行输出划分方案,将N按......
  • 情书密码 题解
    题目描述有消息称:绝恋找到了自己的MissRight,正准备自己的表白。绝恋已经写好了情书,但为了避免其它人截获,他对情书进行加密。为了打探绝恋的私密,你冒着生命危险终于搞到了这封情书。原以为可以轻易将情书解密,结果竟然发现聪明的绝恋并没有直接写出加密用的密码,而是在那粉红色的......
  • CF484B题解
    朴素的办法是枚举每两个数然后更新取模的结果。时间复杂度为\(O(n^2)\)不能通过。这个朴素的过程可以看作枚举一个数然后找对其取模最大值的过程。我们可以枚举一个数,然后再枚举以它的倍数为两端的区间,找其中取模的最大值。找最大值的过程可以二分或双指针。值域很小,也可以......
  • 牛客小白87题解A-G
    A小苯的石子游戏本题贪心模拟即可B小苯的排序疑惑考虑到最简单的操作把n-1个数排好,最后一个看能否有序。即:a[1]<=min(a[2],a[3],a[4]..,a[n])||a[n]>=max(a[1],a[2],a[3]....,a[n-1])满足条件,反之易得不可能C&D小苯的IDE括号问题本题考察题意理解,简单版本我们可以只关注逻......
  • 0217-0224校赛部分题解
    SMUWinter2024Round#3(Div.2)对于自己比较有价值的题目是D题https://codeforces.com/gym/102897/problem/D?mobile=trueJ题https://codeforces.com/gym/102897/problem/JK题https://codeforces.com/gym/102897/problem/KE题https://codeforces.com/gym/102897/prob......