spinmry's Lab

社会学研究 +6

Category

  • 单片机
  • 日常
  • 机器人竞赛
  • 算法竞赛

Tags

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

Recent replies

  • spinmry 发表于「QQ - Mattermost 双向转发机器人」
  • ilghar_kus 发表于「QQ - Mattermost 双向转发机器人」
  • polarnova 发表于「被历史遗忘的Linux PDA——Sharp Zaurus SL-5600评测 」
  • test 发表于「QQ - Mattermost 双向转发机器人」
  • Woshiluo 发表于「NOIP 2013 火柴排队」

友情链接

空白酱
Woshiluo
PolarBear
FlyGoat
BeyondLimits
Memo von EFS
Paizhang
Ntzyz
ZephRay
Polarnova
Tautcany
一之濑的小屋
NekoDaemon
MaxAlex
Abyss Studio
EE Archeology 电子考古学
桜庭清夏的小站
标签:数据结构

NOIP 2013 火柴排队

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

NOIP 2013 火柴排队

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

MORE

BZOJ 1858 [SCOI2010] 序列操作

2019 年 4 月 19 日分类:算法竞赛#算法#OI#数据结构#线段树

BZOJ 1858 [SCOI2010] 序列操作

本来想用线段树做,但是考虑到用线段树的话pushup,pushdown函数有点复杂... 看到题目有覆盖操作立刻想到了珂朵莉树,于是现学了一波然后改了一下模板A了这道题。 (珂学是个好东西) (刷这道题全程循环夢違科(珂)学世紀2333333)

MORE

BZOJ 1067 [SCOI2007]降雨量

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

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;
    }

Tyvj 1730 二逼平衡树

2019 年 2 月 20 日分类:算法竞赛#算法#OI#数据结构#平衡树#分块

Tyvj 1730 二逼平衡树

目前还没AC qaq

先是写了线段树套splay,然而可耻的挂了.. 然后又写了分块,完美的tle了... 待更新

    
    //分块tle
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    //define
    const int maxn = 300 + 5;
    const int maxm = 5e5 + 5;
    const int inf = 0x7FFFFFFF;
    
    int chunk_len[maxn], chunk[maxn][maxn], a[maxm], n, m, cnt, len;
    
    void modify(int ck, int k){
        a[ck] = k;
        int tmp=(ck + len - 1) / len;
        for(register int i = 1; i <= chunk[tmp][0]; ++i)
            chunk[tmp][i] = a[(tmp - 1) * len + i];
        stable_sort(chunk[tmp] + 1,chunk[tmp] + chunk_len[tmp] + 1);
    }
    
    int __lower_bound(int aa[maxn], int k){
        int ll = 1, rr = aa[0];
        while(ll < rr){
            int mid = ll + rr >> 1;
            if(aa[mid] >= k)rr = mid;
            else ll = mid + 1;
        }
        if(aa[ll] >= k)return ll - 1;
        else return ll;
    }
    
    int __sub_search(int aa[maxn], int k){
        int ll = 1, rr = aa[0];
        while(ll < rr){
            int mid = ll + rr >> 1;
            if(aa[mid + 1] <= k)ll = mid + 1;
            else rr = mid;
        }
        if(aa[ll] <= k)return ll + 1;
        else return ll;
    }
    
    int pre(int l, int r, int k){
        int ll = (l + len - 1) / len;
        int rr = (r + len - 1) / len;
        int ans = -inf;
        if(ll != rr){
            for(register int i = l; i <= ll * len; ++i){
                if(a[i] < k) ans = max(ans, a[i]);
            }
            rr++;
            for(register int i = r; i >= (ll - 1) * len; --i){
                if(a[i] < k) ans = max(ans, a[i]);
            }
            for(register int i = ll; i < rr; ++i){
                if(int tmp = __lower_bound(chunk[i], k) != 0){
                    ans = max(chunk[i][tmp], ans);
                }
            }
        }else{
            for(register int i = l; i <= r; ++i){
                if(a[i] < k){
                    ans = max(ans, a[i]);
                }
            }
        }return ans;
    }
    
    int sub(int l, int r, int k){
        int ll = (l + len - 1) / len;
        int rr = (r + len - 1) / len;
        int ans = inf;
        if(ll != rr){
            for(register int i = l; i <= ll * len; ++i){
                if(a[i] > k) ans = min(ans, a[i]);
            }
            ll++;
            for(register int i = r; i >= (ll - 1) * len; --i){
                if(a[i] > k) ans = min(ans, a[i]);
            }
            for(register int i = ll; i < rr; ++i){
                if(int tmp = __sub_search(chunk[i], k) != chunk_len[i] + 1){
                    ans = min(chunk[i][tmp], ans);
                }
            }
        }else{
            for(register int i = l; i <= r; ++i){
                if(a[i] > k){
                    ans = min(ans, a[i]);
                }
            }
        }return ans;
    }
    
    int rnk(int l, int r, int k){
        int ll = (l + len - 1) / len;
        int rr = (r + len - 1) / len;
        int ans = 0;
        if(ll != rr){
            for(register int i = l; i <= ll * len; ++i){
                if(a[i] < k) ans++;
            }
            ll++;
            for(register int i = r; i >= (ll - 1) * len; --i){
                if(a[i] < k) ans++;
            }
            for(register int i = ll; i < rr; ++i){
                ans += __lower_bound(chunk[i], k);
            }
        }else{
            for(register int i = l; i <= r; ++i){
                if(a[i] < k){
                    ans++;
                }
            }
        }return ans+1;
    }
    
    int kth(int l, int r, int k){
        int ll = 0, rr = inf, ans = 0;
        while(ll < rr){
            int mid = ll + rr >> 1;
            if(rnk(l, r, mid) > k) rr = mid;
            else ll = mid+1, ans = mid;
        }return ans;
    }
    
    //main
    int main(){
        ios::sync_with_stdio(false);
        cin >> n >> m;
        for(register int i = 1; i <=n; ++i){
            cin >> a[i];
        }
        cnt = sqrt(n) + 2;len = cnt;
        for(register int i = 1; i <= cnt; ++i){
            for(register int j = 1; j <= len; ++j){
                chunk[i][j] = a[(i - 1) * len + j];
            }
            stable_sort(chunk[i] + 1, chunk[i] + len + 1);
            chunk_len[i] = len;
        }
        if(n % len != 0){
            cnt++;chunk_len[cnt] = n % len;
            for(register int i = 1; i <= chunk_len[cnt]; ++i){
                chunk[cnt][i] = a[(cnt - 1) * len + i];
            }
            stable_sort(chunk[cnt] + 1, chunk[cnt] + chunk_len[cnt] + 1);
        }
        int opt, x, y, z;
        while(m--){
            cin >> opt;
            if(opt == 1){
                cin >> x >> y >> z;
                cout << rnk(x, y, z) << endl;
            }
            else if(opt == 2){
                cin >> x >> y >> z;
                cout << kth(x, y, z) << endl;
            }
            else if(opt == 3){
                cin >> x >> y;
                modify(x, y);
            }
            else if(opt == 4){
                cin >> x >> y >> z;
                cout << pre(x, y, z) << endl;
            }else {
                cin >> x >> y >> z;
                cout << sub(x, y, z) << endl;
            }
        }
        return 0;
    }

Comments

BeyondLimits: tql%%%

Polarnova: 催更

BZOJ 3224 普通平衡树

2019 年 2 月 18 日分类:算法竞赛#OI#数据结构#平衡树#算法

BZOJ 3224 普通平衡树

splay板子,记录一下

    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    //define
    const int maxn=1e5+5;
    
    struct Splay{
        int ch[maxn<<1][2] ,par[maxn<<1] ,cnt[maxn<<1] ,size[maxn<<1] ,val[maxn<<1] ,ntot ,trt;
    
        int chk(int rt){return ch[par[rt]][1] == rt;}
    
        void pushup(int rt){size[rt] = size[ch[rt][0]] + size[ch[rt][1]] + cnt[rt];}
    
        void rotate(int rt){
            int y = par[rt];
            int z = par[y];
            int rnk = chk(rt);
            int w = ch[rt][rnk^1];
            ch[y][rnk] = w; par[w] = y;
            ch[z][chk(y)] = rt;par[rt] = z;
            ch[rt][rnk^1] = y;par[y] = rt;
            pushup(y); pushup(rt);
        }
    
        void splay(int rt,int g = 0){
            while(par[rt] != g){
                int y = par[rt] ,z = par[y];
                if(z != g){
                    if(chk(rt) == chk(y))rotate(y);
                    else rotate(rt);
                }
                rotate(rt);
            }
            if(!g) trt = rt;
        }
    
        void find(int rt){
            if(!trt) return ;
            int cur = trt;
            while(ch[cur][rt > val[cur]] && rt != val[cur]){
                cur = ch[cur][rt > val[cur]];
            }
            splay(cur);
        }
    
        void insert(int rt){
            int cur = trt ,p = 0;
            while(cur && val[cur] != rt){
                p = cur;
                cur = ch[cur][rt > val[cur]];
            }
            if(cur){
                cnt[cur]++;
            }
            else{
                cur = ++ntot;
                if(p) ch[p][rt > val[p]] = cur;
                ch[cur][0] = ch[cur][1] = 0;
                val[cur] = rt;
                par[cur] = p;
                cnt[cur] = size[cur] = 1;
            }
            splay(cur);
        }
    
        int kth(int k){
            int cur = trt;
            while(1){
                if(ch[cur][0] && k <= size[ch[cur][0]]){
                    cur = ch[cur][0];
                }
                else if(k > size[ch[cur][0]] + cnt[cur]){
                    k -= size[ch[cur][0]] + cnt[cur];
                    cur = ch[cur][1];
                }
                else{
                    return cur;
                }
            }
        }
    
        int pre(int rt){
            find(rt);
            if(val[trt] < rt)return trt;
            int cur = ch[trt][0];
            while(ch[cur][1]) cur = ch[cur][1];
            return cur;
        }
    
        int src(int rt){
            find(rt);
            if(val[trt] > rt)return trt;
            int cur = ch[trt][1];
            while(ch[cur][0]) cur = ch[cur][0];
            return cur;
        }
    
        void remove(int rt){
            int last = pre(rt) ,next = src(rt);
            splay(last); splay(next ,last);
            int del = ch[next][0];
            if(cnt[del] > 1){
                cnt[del]--;
                splay(del);
            }
            else ch[next][0] = 0;
        }
    
        int get_rt(){
            return size[ch[trt][0]];
        }
    
        int get_kth(int rt){
            return val[kth(rt+1)];
        }
    
        int get_pre(int rt){
            return val[pre(rt)];
        }
    
        int get_src(int rt){
            return val[src(rt)];
        }
    }tree;
    
    //main
    int main(){
        ios::sync_with_stdio(false);
        int n,op,x;
        cin>>n;
        tree.insert(0x3f3f3f3f);
        tree.insert(0xcfcfcfcf);
        while(n--){
            cin>>op>>x;
            if(op == 1){
                tree.insert(x);
            }
            if(op == 2){
                tree.remove(x);
            }
            if(op == 3){
                tree.find(x);
                cout<<tree.get_rt()<<endl;
            }
            if(op == 4){
                cout<<tree.get_kth(x)<<endl;
            }
            if(op == 5){
                cout<<tree.get_pre(x)<<endl;
            }
            if(op == 6){
                cout<<tree.get_src(x)<<endl;
            }
        }
        return 0;
    }
  • «
  • 1
  • »
Copyright © 2019-2020 spinmry. All rights reversed.
Except where otherwise noted, content on this blog is licensed under CC BY-NC-SA 4.0.