Chlience

【题解】[NOIP2017]列队 NOIP瞎搞系列
传送门 >ω<传送门 >ω<简要题意:一个 $n * m$ 的方阵,从 $(1 , 1)$ 到 $(n , m)$...
扫描右侧二维码阅读全文
18
2018/10

【题解】[NOIP2017]列队 NOIP瞎搞系列

传送门 >ω<
传送门 >ω<

简要题意:一个 $n * m$ 的方阵,从 $(1 , 1)$ 到 $(n , m)$ 用 $1 - nm$ 依次编号,每次取出一个点,然后右侧节点左移补上空位,最右侧一列上移补上空位,将点放在 $(n , m)$ ,求每次取出的点的编号

Solution

观察每个操作 $(x , y)$ ,只会影响第 $x$ 行和第 $y$ 列

需要能够从第 $x$ 行取出第 $y$ 个节点,加入第 $m$ 列末尾;从第 $m$ 列取出第 $x$ 个节点,加入第 $x$ 行末尾

看样子可以线段树维护
维护 $n$ 行的前 $m - 1$ 个位置并单独维护第 $m$ 列即可
然后搞出个动态加点线段树,将前 $m - 1$ 个点设为有点,后面的位置留给插入即可

注意,前面在开始时刻就存在的 $m - 1$ 个点的值只跟其在线段树中位置以及这是第几行相关,可以在取出时处理
如果是插入的点,线段树中保存的就是其正常编号

或者直接上 $Splay$ ?

我的实现是开了两个线段树,一个用来维护前面部分(仅仅删除),一个用来维护后面插入的部分(同样也要支持删除,同时支持插入)
看起来代码很长其实全是线段树....

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300010;
#define mid ((l + r) >> 1)
ll n , m , q;
struct tree1 {
    int cnt , rt[N];
    int node[N << 4] , lson[N << 4] , rson[N << 4];
    int siz(int x) {return node[rt[x]];}
    void newrt(int x , int l , int r) {rt[x] = newnode(l , r);}
    int newnode(int l , int r) {node[++ cnt] = r - l + 1; return cnt;}
    inline ll query(int x , int l , int r , int p) {
        if(l == r) return l;
        if(!lson[x]) lson[x] = newnode(l , mid);
        if(node[lson[x]] >= p) return query(lson[x] , l , mid , p);
        else {
            if(!rson[x]) rson[x] = newnode(mid + 1 , r);
            return query(rson[x] , mid + 1 , r , p - node[lson[x]]);
        }
    }
    inline void del(int x , int l , int r , int p) {
        node[x] --;
        if(l == r) return;
        if(!lson[x]) lson[x] = newnode(l , mid);
        if(node[lson[x]] >= p) del(lson[x] , l , mid , p);
        else {    
            if(!rson[x]) rson[x] = newnode(mid + 1 , r);
            del(rson[x] , mid + 1 , r , p - node[lson[x]]);
        }
    }
    inline ll get(int x , int y) {
        if(x != n + 1) {
            ll _ans = query(rt[x] , 1 , m - 1 , y);
            del(rt[x] , 1 , m - 1 , y);
            return _ans;
        }
        else {
            ll _ans = query(rt[x] , 1 , n , y);
            del(rt[x] , 1 , n , y);
            return _ans;
        }
    }
}t1;
struct tree2 {
    int cnt , rt[N] , in[N];
    ll num[N << 4];
    int node[N << 4] , lson[N << 4] , rson[N << 4];
    inline void newrt(int x) {rt[x] = ++ cnt;}
    inline void insert(int x , int l , int r , int p , ll q) {
        ++ node[x];
        if(l == r) {num[x] = q; return;}
        if(p <= mid) {
            if(!lson[x]) lson[x] = ++ cnt;
            insert(lson[x] , l , mid , p , q);
        }
        else {
            if(!rson[x]) rson[x] = ++ cnt;
            insert(rson[x] , mid + 1 , r , p , q);
        }
    }
    inline ll query(int x , int l , int r , int p) {
        if(l == r) return num[x];
        if(!lson[x]) lson[x] = ++ cnt;
        if(node[lson[x]] >= p) return query(lson[x] , l , mid , p);
        else {
            if(!rson[x]) rson[x] = ++ cnt;
            return query(rson[x] , mid + 1 , r , p - node[lson[x]]);
        }
    }
    inline void del(int x , int l , int r , int p) {
        node[x] --;
        if(l == r) return;
        if(!lson[x]) lson[x] = ++ cnt;
        if(node[lson[x]] >= p) del(lson[x] , l , mid , p);
        else {
            if(!rson[x]) rson[x] = ++ cnt;
            del(rson[x] , mid + 1 , r , p - node[lson[x]]);
        }
    }
    inline ll get(int x , int y) {
        ll _ans = query(rt[x] , 1 , q , y);
        del(rt[x] , 1 , q , y);
        return _ans;
    }
}t2;
ll read() {
    ll ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch=getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch=getchar();}
    return ans * flag;
}
void init() {n = read(); m = read(); q = read();}
void work() {
    for(ll i = 1 ; i <= q ; ++ i) {
        ll x = read() , y = read();
        if(y == m) {//假设是最后一列上的点,单独处理
            ll a;
            
            if(t1.rt[n + 1] == 0) t1.newrt(n + 1 , 1 , n);
            if(x <= t1.siz(n + 1)) a = t1.get(n + 1 , x) * m;
            else a = t2.get(n + 1 , x - t1.siz(n + 1));
            //取出第 x 个节点
            if(t2.rt[n + 1] == 0) t2.newrt(n + 1);
            t2.insert(t2.rt[n + 1] , 1 , q , ++ t2.in[n + 1] , a);
            //将节点 x 插入到线段树中
            printf("%lld\n" , a);
        }
        else {//要处理两列的节点(一列一行?)
            ll a , b;
            
            if(t1.rt[x] == 0) t1.newrt(x , 1 , m - 1);
            if(y <= t1.siz(x)) a = t1.get(x , y) + (x - 1) * m;
            else a = t2.get(x , y - t1.siz(x));
            //提取出第 x 行第 y 个元素
            if(t1.rt[n + 1] == 0) t1.newrt(n + 1 , 1 , n);
            if(x <= t1.siz(n + 1)) b = t1.get(n + 1 , x) * m;
            else b = t2.get(n + 1 , x - t1.siz(n + 1));
            //提取出第 m 列第 x 个元素
            if(t2.rt[x] == 0) t2.newrt(x);
            t2.insert(t2.rt[x] , 1 , q , ++ t2.in[x] , b);
            if(t2.rt[n + 1] == 0) t2.newrt(n + 1);
            t2.insert(t2.rt[n + 1] , 1 , q , ++ t2.in[n + 1] , a);
            //插入元素
            //相当于处理两次,分别为 rt[n + 1] - > rt[x] , rt[x] - > rt[n + 1]
            printf("%lld\n" , a);
        }
    }
}
int main() {
    init();
    work();
    return 0;
}
Last modification:October 18th, 2018 at 04:48 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment