P3960

Aryper · 2021-11-18 17:46:43 · 个人记录

[NOIP2017 提高组] 列队

树状数组的代码基本一个也看不懂。。。

使用了动态开点线段树，常数略大，但感觉是非常实用的数据结构。

大概是给每行开一个线段树，最后一列单独开一个线段树，所以一开始每行存储的信息只有 [1,m-1]。

然后考虑插入删除之类的操作。

出列一个人，就是在第 x 棵线段树上二分找到第 y 个有值的点（无值的点已经被删了），然后把它删掉（即赋值为 0）。然后我们再将第 n+1 棵线段树的第 x 个有值的点删去并插入到第 x 棵线段树的末尾（直接插入，不需要考虑线段树上的值是紧凑的）。然后再在第 n+1 棵线段树末尾插入刚刚出列的人。

当然如果出列的人就在最后一列我们特判一下直接操作即可。

因为动态开点，所以空间只与有用的点有关（即 O(q\log n)），这题空间很松，所以可以做。

动态开点的时候就是初始状态的时候所以可以按照队列规律直接计算（感觉自己就是卡在这个点没想出来）。

时间复杂度 O(q\log n)。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=3e5;

ll n,m,q,tot,x,y,tmp1,tmp2;

struct dsgt{
    ll cnt,num,lc,rc;
    #define cnt(x) tree[x].cnt
    #define num(x) tree[x].num
    #define lc(x) tree[x].lc
    #define rc(x) tree[x].rc
}tree[N*40];

inline ll getcnt(ll i,ll l,ll r) {
    if(i<=n) r=min(r,m-1);
    else r=min(r,n);
    return r-l+1>0?r-l+1:0;
}

inline ll getnum(ll i,ll x) {
    if(i<=n) return (i-1)*m+x;
    return x*m;
}

inline ll query(ll i,ll p,ll l,ll r,ll k) {
    if(l==r) {
        cnt(p)=0;return num(p);
    }
    ll mid=(l+r)>>1;
    if(!lc(p)) {
        lc(p)=++tot;
        cnt(lc(p))=getcnt(i,l,mid);
        if(l==mid) num(lc(p))=getnum(i,l);
    }
    if(!rc(p)) {
        rc(p)=++tot;
        cnt(rc(p))=getcnt(i,mid+1,r);
        if(mid+1==r) num(rc(p))=getnum(i,mid+1);
    }
    ll res;
    if(cnt(lc(p))>=k) res=query(i,lc(p),l,mid,k);
    else res=query(i,rc(p),mid+1,r,k-cnt(lc(p)));
    cnt(p)=cnt(lc(p))+cnt(rc(p));
    return res;
}

void ins(ll i,ll p,ll l,ll r,ll x,ll y) {
    if(l==r) {
        cnt(p)=1;num(p)=y;return;
    }
    ll mid=(l+r)>>1;
    if(!lc(p)) {
        lc(p)=++tot;
        cnt(lc(p))=getcnt(i,l,mid);
        if(l==mid) num(lc(p))=getnum(i,l);
    }
    if(!rc(p)) {
        rc(p)=++tot;
        cnt(rc(p))=getcnt(i,mid+1,r);
        if(mid+1==r) num(rc(p))=getnum(i,mid+1);
    }
    if(x<=mid) ins(i,lc(p),l,mid,x,y);
    else ins(i,rc(p),mid+1,r,x,y);
    cnt(p)=cnt(lc(p))+cnt(rc(p));
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    n=read();m=read();q=read();tot=n+1;

    for(ll i=1;i<=q;i++) {
        x=read();y=read();
        if(y<m) {
            writeln(tmp1=query(x,x,1,N+N,y));
            tmp2=query(n+1,n+1,1,N+N,x);
            ins(x,x,1,N+N,N+i,tmp2);
            ins(n+1,n+1,1,N+N,N+i,tmp1);
        }
        else {
            writeln(tmp1=query(n+1,n+1,1,N+N,x));
            ins(n+1,n+1,1,N+N,N+i,tmp1);
        }
    }

    return 0;
}