spinmry's Lab

绝赞摸鱼中Orz

Category

  • Algorithm
  • Hardware
  • Homelab
  • Programming
  • Retro
  • Software

Tags

  • 算法
  • OI
  • Linux
  • 数据结构
  • HardwareHacking
  • Homelab
  • VEX
  • 线段树
  • 机器人
  • Vintage
  • Nspire
  • QQBot
  • 离散化
  • 单片机
  • RobotC
  • 图论
  • Kruskal
  • 平衡树
  • ARM
  • 计算设备
  • 爬虫
  • 动态规划
  • Tarjan
  • Loongson
  • iLO
  • Python
  • STM32
  • Mac
  • 数论
  • CUDA
  • Mattermost
  • Wolfram
  • 网页
  • ACG
  • 分块
  • 树状数组

Recent replies

  • spinmry 发表于「在 macOS 上运行 iSCSI 无盘 Linux 虚拟机」
  • Mizu 发表于「在 macOS 上运行 iSCSI 无盘 Linux 虚拟机」
  • Prelina 发表于「在 macOS 上运行 iSCSI 无盘 Linux 虚拟机」
  • jiyouzhan 发表于「使用 Debian + libvirt + WebVirtCloud 作为 homelab 虚拟化平台」
  • jianchen 发表于「在 Loongson 2F 上编译 Common Desktop Environment」

友情链接

空白酱
Woshiluo
FlyGoat
BeyondLimits
Memo von EFS
Paizhang
Ntzyz
ZephRay
Polarnova
Tautcany
NekoDaemon
MaxAlex
Abyss Studio
EE Archeology 电子考古学
桜庭清夏的小站
欠陥電気の摸鱼小池
白玉楼製作所
naivekun's blog

娱乐向跑分

Coremark
Linpack
标签:离散化

NOIP 2013 火柴排队

2019 年 10 月 6 日分类:Algorithm#算法#OI#离散化#数据结构#树状数组

NOIP 2013 火柴排队

很经典的一道题了,然而以前一直懒得做Orz 离散化+树状数组求逆序对

MORE

BZOJ 1067 [SCOI2007]降雨量

2019 年 3 月 12 日分类:Algorithm#算法#数据结构#线段树#离散化

BZOJ 1067 [SCOI2007]降雨量

todolist清理计划--; 很久很久以前暑假留的作业= = 将年份离散化,用线段树简单的维护最值,然后依照提议判断就好。

    #include <iostream>
    #include <cstdio>
    #define MAYBE cout << "maybe" << endl
    #define TRUE cout << "true" << endl
    #define FALSE cout << "false" << endl
    using namespace std;
    
    //define
    const int maxn = 50000 + 5;
    int year[maxn], val[maxn], tree[maxn << 2];
    int n, m;
    
    void build(int rt, int l, int r){
        if(l == r){
            tree[rt] = val[l];return ;
        }
        int mid = l + r >> 1;
        build(rt << 1, l ,mid);
        build(rt << 1 | 1, mid + 1, r);
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }  
    
    int query(int rt, int l, int r, int ll, int rr){
        if(ll <= l && r <= rr){
            return tree[rt];
        }
        int mid = l + r >> 1;
        int ans = -1 * 0x7f7f7f7f;
        if(ll <= mid)ans = max(ans, query(rt << 1, l, mid, ll, rr));
        if(rr > mid)ans = max(ans, query(rt << 1 | 1, mid + 1, r, ll, rr));
        return ans;
    }
    
    int main(){
        ios::sync_with_stdio(false);
        cin >> n;
        for(register int i = 1; i <= n; ++i)cin >> year[i] >> val[i];
        build(1, 1, n);
        cin >> m;
        while(m--){
            int x,y,u,v;
            cin >> y >> x;
            if(y >= x) { FALSE; continue; }
            u=lower_bound(year+1, year+n+1, y) - year;
            v=lower_bound(year+1, year+n+1, x) - year;
            if(y == year[u] && x == year[v]){
                if(val[u] < val[v]) FALSE;
                else if(v == u+1){
                    if(x == y+1)TRUE;
                    else MAYBE;
                }
                else{
                    int w = query(1, 1, n, u+1, v-1);
                    if(w >= val[v])  FALSE; 
                    else{
                        if(x-y == v-u)TRUE;
                        else MAYBE;
                    }
                }
            }
            else if(y != year[u] && x == year[v]){
                if(u == v) MAYBE;
                else{
                    int w = query(1, 1, n, u, v-1);
                    if(w >= val[v]) FALSE;
                    else MAYBE;
                }
            }
            else if(y == year[u] && x != year[v]) {
                if(v == u+1) MAYBE;
                else{
                    int w = query(1, 1, n, u+1, v-1);
                    if(val[u] <= w) FALSE;
                    else MAYBE;
                }
            }
            else if(y != year[u] && x != year[v]) MAYBE;
        }
        return 0;
    }
  • «
  • 1
  • »
Copyright © 2019-2023 spinmry. All rights reserved.
Except where otherwise noted, content on this blog is licensed under CC BY-SA 4.0.