spinmry's Lab

绝赞摸鱼中Orz

Category

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

Tags

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

Recent replies

  • rantrism 发表于「解决 Linux Optimus 混合模式下独立显卡外接显示器卡顿的问题」
  • 千羽 发表于「在 Loongson 2F 上编译 Common Desktop Environment」
  • spinmry 发表于「QQ - Mattermost 双向转发机器人」
  • ilghar_kus 发表于「QQ - Mattermost 双向转发机器人」
  • polarnova 发表于「被历史遗忘的Linux PDA——Sharp Zaurus SL-5600评测 」

友情链接

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

娱乐向跑分

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-2022 spinmry. All rights reserved.
Except where otherwise noted, content on this blog is licensed under CC BY-SA 4.0.