NOIP2017D2T3列队 动态开点线段树

题目描述
Sylvia 是一个热爱学习的女♂孩子。

前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有n \times mn×m 名学生，方阵的行数为 nn ，列数为 mm 。

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中 的学生从 1 到 n \times mn×m 编上了号码（参见后面的样例）。即：初始时，第 ii 行第 jj 列 的学生的编号是(i-1)\times m + j(i−1)×m+j 。

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天 中，一共发生了 q q 件这样的离队事件。每一次离队事件可以用数对(x,y) (1 \le x \le n, 1 \le y \le m)(x,y)(1≤x≤n,1≤y≤m) 描述，表示第 xx 行第 yy 列的学生离队。

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达 这样的两条指令：

向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条 指令之后，空位在第 xx 行第 mm 列。

向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条 指令之后，空位在第 nn 行第 mm 列。
教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后， 下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 nn 行 第 mm 列一个空位，这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学 的编号是多少。

注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后 方阵中同学的编号可能是乱序的。

题解：

感觉这道题是考场上没做的题目中最简单的了……考虑 n=1 $n=1$的暴力算法，用个线段树，长度开到 m+c $m+c$，前 m $m$位一开始的值为 1 $1$，然后每次就在线段树上二分，找到第 y $y$个 1 $1$，把它的值变为0，然后在后面再加上一个 1 $1$就行了，对于满分算法，只需要用 n+1 $n+1$棵线段树，分别维护 n $n$行和最后一列就可以了，然后动态开点。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int Maxn=600010;
const int inf=2147483647;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
LL num[Maxn*40];
int n,m,q,root[Maxn],lc[Maxn*40],rc[Maxn*40],c[Maxn*40],cnt,end[Maxn];
LL p(LL x,LL y){return (LL)(m)*(LL)(x-1)+(LL)(y);}
void build(int &u,int l,int r,int ll,int rr)
{
if(!u)u=++cnt;c[u]=rr-ll+1;
if(l==ll&&r==rr)return;
int mid=l+r>>1;
if(rr<=mid)build(lc[u],l,mid,ll,rr);
else if(ll>mid)build(rc[u],mid+1,r,ll,rr);
else build(lc[u],l,mid,ll,mid),build(rc[u],mid+1,r,mid+1,rr);
}
int type;//0最后一列 第type行 
LL del(int &u,int l,int r,int k)
{
if(!u)u=++cnt,c[u]=r-l+1;
    c[u]--;
if(l==r)
    {
if(num[u])return num[u];
if(!type)return p(l,m);
else return p(type,l);
    }
int mid=l+r>>1,ll;
if(!lc[u])ll=mid-l+1;
else ll=c[lc[u]];
if(k<=ll)return del(lc[u],l,mid,k);
else return del(rc[u],mid+1,r,k-ll);
}
LL tnum;
void ins(int &u,int l,int r,int p)
{
if(!u)u=++cnt;c[u]++;
if(l==r){num[u]=tnum;return;}
int mid=l+r>>1;
if(p<=mid)ins(lc[u],l,mid,p);
else ins(rc[u],mid+1,r,p);
}
int main()
{
    n=read(),m=read(),q=read();cnt=0;
for(int i=1;i<=n;i++)
    {
        build(root[i],1,600000,1,m-1);
        end[i]=m-1;
    }
    build(root[n+1],1,600000,1,n);
    end[n+1]=n;
while(q--)
    {
int x=read(),y=read();
if(y==m)
        {
            type=0;
            LL t=del(root[n+1],1,600000,x);
printf("%lld\n",t);
            end[n+1]++;
            tnum=t;
            ins(root[n+1],1,600000,end[n+1]);
        }
else
        {
            type=x;
            LL t1=del(root[x],1,600000,y);
printf("%lld\n",t1);
            type=0;
            LL t2=del(root[n+1],1,600000,x);
            end[n+1]++;
            tnum=t1;
            ins(root[n+1],1,600000,end[n+1]);
            end[x]++;
            tnum=t2;
            ins(root[x],1,600000,end[x]);
        }
    }
}