首页 > 其他分享 >2024.1.6做题纪要

2024.1.6做题纪要

时间：2024-01-07 09:23:06浏览次数：24  
标签：opt 2024.1 val int number tot 做题 ask 纪要

P4390 [BalkanOI2007] Mokia 摩基亚 / （离线）简单题

第一眼看题，emmm，跟分治有半毛钱关系啊！！！！这每次分治一次不直接复杂度爆炸？？

冷静下来后，我们发现对于一个点，对于区间产生贡献充要条件是他的 \(x\) 轴要在区间内。

所以。。。我们是不是可以离线下来对于 \(x\) 轴排一遍序，我们只有左半部分的点会对右半部分产生贡献。

而且我们可以对于一次询问的左下角和右上角拆成两个点，右上角的前缀和减去左下角的前缀和就是答案。

用之前三维偏序的方法处理 \(y\) 轴就行了。

HOI4 
#include <bits/stdc++.h>

class Ask {
public:
    int opt, x[2], y[2], a, id;
}number[200000];

int N, W, tot;
int flag[210000];
int answer[210000];

class Position1 {
public:
    int x, y, val;
}pos[210000];

class Position2 {
public:
    int x, y1, y2, id;
}temp[210000];

class Binary_indexed_tree {
    #define lowbit(x) (x & (-x))

public:
    int number[2100000];
    
    void Insert(int position, int val) {
        while (position <= W) {
            number[position] += val;
            position += lowbit(position);
        }
    }

    int Query(int position) {
        int result = 0;
        while (position) {
            result += number[position];
            position -= lowbit(position);
        }
        return result;
    }
}tree;

bool cmp1(const Position1 &a, const Position1 &b) {
    return a.x < b.x;
}

bool cmp2(const Position2 &a, const Position2 &b) {
    return a.x < b.x;
}

void CDQ(int l, int r) {
    if (l == r)
        return;
    
    int mid = (l + r) >> 1;

    CDQ(l, mid);
    CDQ(mid + 1, r);

    int top1 = 0, top2 = 0;
    for (int i = l; i <= mid; ++ i) 
        if (number[i].opt == 1) 
            pos[++ top1] = {number[i].x[0], number[i].y[0], number[i].a};
        
    for (int i = mid + 1; i <= r; ++ i) {
        if (number[i].opt == 2) {
            temp[++ top2] = {number[i].x[0] - 1, number[i].y[0], number[i].y[1], number[i].id};
            temp[++ top2] = {number[i].x[1], number[i].y[0], number[i].y[1], number[i].id};
        }
    }
    std::sort(pos + 1, pos + 1 + top1, cmp1);
    std::sort(temp + 1, temp + 1 + top2, cmp2);

    int I = 1, J = 1;

    while (I <= top1 && J <= top2) {
        if (pos[I].x <= temp[J].x) {
            tree.Insert(pos[I].y, pos[I].val);
            I ++;
        }
        else {
            int ID = temp[J].id;
            answer[ID] += flag[ID] * (tree.Query(temp[J].y2) - tree.Query(temp[J].y1 - 1));
            flag[ID] *= -1;
            J ++;
        }
    }
    while (J <= top2) {
        int ID = temp[J].id;
        answer[ID] += flag[ID] * (tree.Query(temp[J].y2) - tree.Query(temp[J].y1 - 1));
        flag[ID] *= -1;
        J ++;
    }

    for (int i = 1; i <= I - 1; ++ i)
        tree.Insert(pos[i].y, -pos[i].val);
}

int cnt;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    memset(flag, -1, sizeof(flag));
    std::cin >> W >> W;
    std::cin >> number[++ tot].opt;
    while (number[tot].opt != 3) {
        if (number[tot].opt == 1) {
            std::cin >> number[tot].x[0] >> number[tot].y[0] >> number[tot].a;
        }
        else {
            number[tot].id = ++ cnt;
            std::cin >> number[tot].x[0] >> number[tot].y[0] >> number[tot].x[1] >> number[tot].y[1];
        }
        std::cin >> number[++ tot].opt;
    }
    N = tot - 1;
    tot = 0;
    CDQ(1, N);
    for (int i = 1; i <= cnt; ++ i)
        std::cout << answer[i] << '\n';
    return 0;
}

P4169 [Violet] 天使玩偶/SJY摆棋子

把绝对值拆成 \(4\) 部分，对于每一个询问都有左上，左下，右上，右下的点来维护。

好麻烦啊。。cdq都这么麻烦吗QAQ。

EU4 
#include <bits/stdc++.h>

const int end = 1e6 + 10;

int N, M, cnt;
int answer[501000];

class Position {
public:
    int x, y, opt, id;
}ask[1010000], pos[1010000];

class Binary_Inexed_Tree {
    #define lowbit(x) (x & (-x))

public:
    int min[2010000];
    Binary_Inexed_Tree() {
        for (int i = 1; i <= 2 * end + 10; ++ i)
            min[i] = 1e9;
    }
    void clear(int position) {
        position += end + 10;
        while (position <= 2 * end + 10) {
            if (min[position] == 1e9)
                return;
            min[position] = 1e9;
            position += lowbit(position);
        }
    }
    void Insert(int position, int val) {
        position += end + 10;
        while (position <= 2 * end + 10) {
            if (min[position] <= val)
                return;
            min[position] = std::min(min[position], val);
            position += lowbit(position);
        }
    }
    int Query(int position) {
        int result = 1e9;
        position += end + 10;

        while (position) {
            result = std::min(result, min[position]);
            position -= lowbit(position);
        }
        return result;
    }

    #undef lowbit(x)
}leftUp, leftDown;

bool cmp(const Position &a, const Position &b) {
    return a.x < b.x;
}

void CDQ(int l, int r) {
    if (l == r)
        return;

    int mid = (l + r) >> 1;
    int I = l, J = mid + 1;
    int beginToNow, endToNow, x, y, id;

    CDQ(l, mid);
    CDQ(mid + 1, r);

    while (I <= mid && J <= r) {
        if (pos[I].opt == 2) {
            I ++;
            continue;
        }
        if (pos[J].opt == 1) {
            J ++;
            continue;
        }
        if (pos[I].x <= pos[J].x) {
            beginToNow = pos[I].y;
            endToNow = end - pos[I].y + 1;
            x = pos[I].x, y = pos[I].y;
            
            leftUp.Insert(endToNow, -x + y);
            leftDown.Insert(beginToNow, -x - y);
            I ++;
        }
        else {
            beginToNow = pos[J].y;
            endToNow = end - pos[J].y + 1;
            x = pos[J].x, y = pos[J].y, id = pos[J].id;

            int temp = leftUp.Query(endToNow);
            if (temp != 1000000000ll) 
                answer[id] = std::min(answer[id], x - y + temp);
            temp = leftDown.Query(beginToNow);
            if (temp != 1000000000ll) 
                answer[id] = std::min(answer[id], x + y + temp);
            J ++;
        }
    }

    while (J <= r) {
        if (pos[J].opt == 1) {
            J ++;
            continue;
        }
        beginToNow = pos[J].y;
        endToNow = end - pos[J].y + 1;
        x = pos[J].x, y = pos[J].y, id = pos[J].id;
            
        int temp = leftUp.Query(endToNow);
        if (temp != 1000000000ll) 
            answer[id] = std::min(answer[id], x - y + temp);
        temp = leftDown.Query(beginToNow);
        if (temp != 1000000000ll) 
            answer[id] = std::min(answer[id], x + y + temp);
        J ++;
    }
    for (int i = l; i <= I; ++ i) {
        leftUp.clear(end - pos[i].y + 1);
        leftDown.clear(pos[i].y);
    }

    std::inplace_merge(pos + l, pos + mid + 1, pos + r + 1, cmp);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N >> M;
    for (int i = 1; i <= N; ++ i) {
        std::cin >> ask[i].x >> ask[i].y;
        ask[i].opt = 1;
    }
    for (int i = N + 1; i <= N + M; ++ i) {
        std::cin >> ask[i].opt;
        std::cin >> ask[i].x >> ask[i].y;
        if (ask[i].opt == 2) {
            ask[i].id = ++ cnt;
            answer[cnt] = 1e9;
        }
    }
    for (int i = 1; i <= N + M; ++ i) {
        pos[i].x = ask[i].x;
        pos[i].y = ask[i].y;
        pos[i].opt = ask[i].opt;
        pos[i].id = ask[i].id;
    }
    CDQ(1, N + M);
    for (int i = 1; i <= N + M; ++ i) {
        pos[i].x = end - ask[i].x;
        pos[i].y = end - ask[i].y;
        pos[i].opt = ask[i].opt;
        pos[i].id = ask[i].id;
    }
    CDQ(1, N + M);
    for (int i = 1; i <= cnt; ++ i) {
        std::cout << answer[i] << '\n';
    }
    return 0;
}
/*
2 3 
1 1 
2 3 
2 1 2 
1 3 3 
2 4 2
*/

[CQOI2011] 动态逆序对

这个还是比较好想的，我们可以处理出来每次删除点 \(i\) 时，前面还剩下的数有多少个数比 \(i\) 位置的数大，后面还剩下的数有多少个比 \(i\) 位置的小。

这样我们就能求出每次删除减少的逆序对了，然后就知道答案了。

Skyline 
#include <bits/stdc++.h>

int N, M;
int answer[51000];

class Ask {
public:
    int tim, pos, val;
}ask[51000], transfer[51000];

class Binary_indexed_Tree {
    #define lowbit(x) (x & (-x))

public: 
    int number[110000];

    void Add(int position, int val) {
        while (position <= N) {
            number[position] += val;
            position += lowbit(position);
        }
    }

    int Query(int position) {
        int result = 0;

        while (position) {
            result += number[position];
            position -= lowbit(position);
        }
        return result;
    }

    void clear(int position) {
        while (position <= N) {
            number[position] = 0;
            position += lowbit(position);
        }
    }
}tree;

int barrel[110000];

bool cmp(const Ask &a, const Ask &b) {
    return a.pos < b.pos;
}

void CDQ(int l, int r) {
    if (l == r)
        return;
    
    int mid = (l + r) >> 1;
    int I = l, J = mid + 1;
    
    CDQ(l, mid);
    CDQ(mid + 1, r);

    while (I <= mid && J <= r) {
        if (ask[I].pos <= ask[J].pos) {
            tree.Add(ask[I].val, 1);
            I ++;
        }
        else {
            answer[ask[J].tim] -= tree.Query(N) - tree.Query(ask[J].val);
            J ++;
        }
    }
    while (J <= r) {
        answer[ask[J].tim] -= tree.Query(N) - tree.Query(ask[J].val);
        J ++;
    }
    for (int i = l; i <= I - 1; ++ i)
        tree.clear(ask[i].val);
    std::inplace_merge(ask + l, ask + mid + 1, ask + r + 1, cmp);
}

int temp[110000], val[110000];
long long sum = 0;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N >> M;
    for (int i = 1; i <= N; ++ i) {
        std::cin >> val[i];
        barrel[val[i]] = i;
        tree.Add(val[i], 1);
        temp[i] += tree.Query(N) - tree.Query(val[i]);
        sum += temp[i];
    }
    for (int i = 1; i <= N; ++ i)
        tree.clear(i);
    for (int i = N; i >= 1; -- i) {
        temp[i] += tree.Query(val[i]);
        tree.Add(val[i], 1);
    }
    for (int i = 1; i <= N; ++ i)
        tree.clear(i);
    for (int i = 1; i <= M; ++ i) {
        std::cin >> transfer[i].val;
        transfer[i].tim = i;
        transfer[i].pos = barrel[transfer[i].val];
        answer[i] = temp[transfer[i].pos];
        ask[i] = transfer[i];
    }
    CDQ(1, M);
    for (int i = 1; i <= M; ++ i) {
        ask[i] = transfer[i];
        ask[i].pos = N - transfer[i].pos + 1;
        ask[i].val = N - ask[i].val + 1;
    }
    CDQ(1, M);
    for (int i = 1; i <= M; ++ i) {
        sum -= answer[i - 1];
        std::cout << sum << '\n';
    }
    return 0;
}

标签：opt,2024.1,val,int,number,tot,做题,ask,纪要
From： https://www.cnblogs.com/jueqingfeng/p/17948471

相关文章

  • 2024.1.6做题总结
    luogu2258[NOIP2014普及组]子矩阵本题乍一看数据范围很小，但是如果暴力的话时间复杂度为\(O(C^r_nC^c_m)\)，在最坏情况（\(r=\frac{1}{2}n,c=\frac{1}{2}m\)）下过不了。本题满足最优化，但是没得贪，二维好像不好跑dp啊。可以枚举哪些行，然后跑一维的dp。我们用一个dfs固定一下......
  • Solution Set【2024.1.5】
    明天再补。[POI2011]LightningConductor设\(f_i\)表示只考虑\(\left[1,i\right]\)的情况下\(i\)的答案，那么有：\[f_i=\max\limits_{j\lei}a_j-a_i+\sqrt{\left\lverti-j\right\rvert}\]发现其满足四边形不等式，于是使用分治优化即可。时间复杂度\(O(n\log......
  • 2024.1.5——每日总结
    学习所花时间（包括上课）：9h代码量（行）：0行博客量（篇）：1篇今天，上午学习，下午学习；我了解到的知识点：1.ERP明日计划：学习......
  • 南外集训 2024.1.5 T3
    非常简单的一道题。要好好反思为什么没有做出来。题意给定一棵点带权的树，强制在线询问一条链上取恰好\(m\)个数按位与的最大值。\(1\len\le10^6,1\leq\le10^5,1\lem\le10,0\leV<2^{62}\)。解法考虑一个暴力：取出树链上所有点权，二分答案\(x\)，则需要检查是否存在至......
  • 2024.1.1 Java学习
    1.前缀自增自减法：先进行自增或自减运算，在进行表达式运算2.后缀自增自减法：先进行表达式运算，再进行自增或自减运算3.位运算符，作用在所有的位上。&：如果相对应位都是1，结果为1|：相对应位有1位是1，结果为1^:相对应位不同，结果为1~:按位取反，0变1，1变0<<:左操作数按位左移右操作数指定......
  • 2024.1 NFLS 训练纪要
    其实没想好这篇博要怎么写。大概就还是写个solutionset之类的吧。这个要加入做题纪要合集吗？？目录2024.1.1T2BeautifulWorld(SDWC2021Day3T3美丽的世界)2024.1.1100/10/15,rank10/35怎么我这次来打的第一场又是没啥人打导致排名靠前，历史总是惊人的相似。但是打......
  • 做题记录：数据结构 I
    标*的题目是个人认为质量较高或比较符合个人喜好的题目。*I.P5278算术天才⑨与等差数列尝试寻找一个序列满足为等差数列的充分必要条件。显然需要有\(\max-\min=(r-l)k\)。直接要求等差的话，信息不好合并。但等差的限制有一个必要条件是，差分序列的\(\gcd\)为\(k......
  • rabbitmq 的一些简单纪要
    安装Erlang百度下载下载rabbitmq安装好rabbitmq-pluginsenablerabbitmq_management添加web界面http://localhost:15672/默认地址rabbitmq-serverstart启动mqrabbitmqctladd_userliujian123添加用户密码window11添加报错，通过guest添加用户rabbit......
  • 2023.12.31做题纪要
    TJOI2015弦论身为彩笔的我觉得这道题还不错？？？对于新学的我来说挺考验对\(SAM\)的理解？？要用一个类似洛谷\(SAM\)板子题的数组来记录每个节点的\(right(endpos)\)集合的大小。最后维护一下就行了。主要难在证明。晴天#include<bits/stdc++.h>constintMAXN=3*(5......
  • 2023.12.30做题纪要
    SAM模板评价：逆天纸糊串，学不会一点。#include<bits/stdc++.h>constintMAXN=3e6+100;intN;charch[MAXN];longlonganswer;classSuffix_Automaton{private:inttot,last,root;intchild[MAXN][26],link[MAXN],length[MAXN];longlongcnt......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99