代码

// NOIP2017 列队 (noip17f), fast version.
//
// Model: row x owns private list A_x (cols 1..m-1) and the shared last column C.
//   event (x,y), y<m : v = A_x.remove(y); u = C.remove(x); A_x.push(u); C.push(v)
//   event (x,y), y==m: v = C.remove(x); C.push(v)
//   print v
//
// A_x = [initial positions 1..m-1 with holes] ++ [appended values].
// Whether event (x,y<m) deletes from the initial part or from the tail depends
// only on liveA (remaining initial elements) which depends only on the y's of
// that row => kind and tail-rank are known offline.  Initial deletions are
// resolved per row with one reusable Fenwick over [1,m-1]; the runtime tail is
// an append-only slot pool.  Both the last column and the slot pool use a
// bitset + word-Fenwick for cache-friendly order statistics.
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long u64;

struct Bits {
    vector<u64> w;
    vector<int> fw;
    int nw, tot;
    void init(int n){ nw=(n+63)>>6; if(nw<1) nw=1; w.assign(nw,0); fw.assign(nw+2,0); tot=0; }
    inline void add(int p,int v){
        int i=p>>6; u64 m=1ULL<<(p&63);
        if(v){
            if(!(w[i]&m)){ w[i]|=m; tot++; for(int j=i+1;j<=nw;j+=j&-j) fw[j]++; }
        } else {
            if(w[i]&m){ w[i]&=~m; tot--; for(int j=i+1;j<=nw;j+=j&-j) fw[j]--; }
        }
    }
    inline int countBefore(int p) const {
        int i=p>>6, s=0;
        for(int j=i;j>0;j-=j&-j) s+=fw[j];
        int off=p&63;
        if(off && i<nw) s+=__builtin_popcountll(w[i] & ((1ULL<<off)-1));
        return s;
    }
    inline int kth(int k) const {
        int pos=0, bit=1;
        while((bit<<1)<=nw) bit<<=1;
        for(; bit; bit>>=1){ int np=pos+bit; if(np<=nw && fw[np]<k){ pos=np; k-=fw[np]; } }
        int wi=pos; u64 x=w[wi];
        while(k>1){ x&=x-1; k--; }
        return (wi<<6)+__builtin_ctzll(x);
    }
};

static int n, m, q;
static vector<int> X, Y, rowStart, rowOps;
static vector<int> offs, iused;          // tail pool per row
static Bits tailBits;
static vector<ll>  tval;
static vector<ll>  preV;
static vector<char> kind;
static vector<int> krank;
static Bits colBits;
static vector<ll>  colTail;
static vector<ll> out;

static void solve_fast(int nn,int mm,int qq, const vector<int>& Xi, const vector<int>& Yi){
    n=nn; m=mm; q=qq; X=Xi; Y=Yi;
    kind.assign(q,0); krank.assign(q,0); preV.assign(q,0);
    // ---- counting sort: ops grouped by row, time order preserved ----
    rowStart.assign(n+2,0);
    for(int i=0;i<q;i++) rowStart[X[i]+1]++;
    for(int x=1;x<=n+1;x++) rowStart[x]+=rowStart[x-1];
    rowOps.assign(q,0);
    {
        vector<int> pos(rowStart.begin(), rowStart.end());
        for(int i=0;i<q;i++) rowOps[pos[X[i]]++]=i;
    }
    // ---- per row: kind & rank of each deletion ----
    for(int x=1;x<=n;x++){
        int liveA = m-1;
        for(int t=rowStart[x]; t<rowStart[x+1]; t++){
            int i=rowOps[t];
            int y=Y[i];
            if(y>=m) continue;
            if(y<=liveA){ kind[i]=1; liveA--; }
            else { kind[i]=2; krank[i]=y-liveA; }
        }
    }
    // ---- resolve initial deletions per row with a reusable Fenwick over [1,m-1] ----
    if(m>=2){
        int FW2=m;                       // fenwick over positions 1..m-1
        vector<int> f2(FW2+2,0);
        for(int i=1;i<=m-1;i++) for(int j=i;j<=FW2;j+=j&-j) f2[j]++;
        int hb=1; while((hb<<1)<=FW2) hb<<=1;
        for(int x=1;x<=n;x++){
            for(int t=rowStart[x]; t<rowStart[x+1]; t++){
                int i=rowOps[t];
                if(kind[i]!=1) continue;
                int r=Y[i], pos=0;
                for(int bit=hb; bit; bit>>=1){ int np=pos+bit; if(np<=FW2 && f2[np]<r){ pos=np; r-=f2[np]; } }
                int p=pos+1;
                preV[i]=(ll)(x-1)*m + p;
                for(int j=p;j<=FW2;j+=j&-j) f2[j]--;
            }
            for(int t=rowStart[x]; t<rowStart[x+1]; t++){
                int i=rowOps[t];
                if(kind[i]!=1) continue;
                int p=(int)(preV[i]-(ll)(x-1)*m);
                for(int j=p;j<=FW2;j+=j&-j) f2[j]++;
            }
        }
    }
    // ---- tail slot pool ----
    offs.assign(n+1,0); iused.assign(n+1,0);
    int cur=0;
    for(int x=1;x<=n;x++){
        int c=0;
        for(int t=rowStart[x]; t<rowStart[x+1]; t++) if(Y[rowOps[t]]<m) c++;
        offs[x]=cur; cur += c+2;
    }
    tailBits.init(cur+2);
    tval.assign(cur+2,0);
    // ---- column ----
    colBits.init(n+q+2);
    for(int i=0;i<n;i++) colBits.add(i,1);
    colTail.clear(); colTail.reserve(q+2);
    out.clear(); out.reserve(q+2);
    for(int i=0;i<q;i++){
        int x=X[i], y=Y[i];
        ll v;
        if(y>=m){
            int cp0 = colBits.kth(x);          // 0-based slot
            colBits.add(cp0,0);
            v = (cp0<n) ? (ll)(cp0+1)*m : colTail[cp0-n];
        } else if(kind[i]==1){
            v = preV[i];
        } else {
            int j=krank[i];
            int gi = tailBits.kth(tailBits.countBefore(offs[x]) + j);
            v = tval[gi];
            tailBits.add(gi,0);
        }
        if(y<m){
            int cp0 = colBits.kth(x);
            colBits.add(cp0,0);
            ll u = (cp0<n) ? (ll)(cp0+1)*m : colTail[cp0-n];
            int slot = offs[x] + iused[x]++;
            tval[slot]=u;
            tailBits.add(slot,1);
        }
        colTail.push_back(v);
        colBits.add(n + (int)colTail.size() - 1, 1);
        out.push_back(v);
    }
}

static char inbuf[1<<24];
int main(){
    size_t got = fread(inbuf,1,sizeof(inbuf)-1,stdin);
    inbuf[got]=0;
    char* p=inbuf;
    #define RD(v) { while(*p && (*p<'0'||*p>'9')) p++; long long xx=0; while(*p>='0'&&*p<='9'){ xx=xx*10+(*p-'0'); p++; } v=xx; }
    long long a,b,c;
    RD(a); RD(b); RD(c);
    n=(int)a; m=(int)b; q=(int)c;
    X.resize(q); Y.resize(q);
    for(int i=0;i<q;i++){ long long u,vv; RD(u); RD(vv); X[i]=(int)u; Y[i]=(int)vv; }
    solve_fast(n,m,q,X,Y);
    {
        static char ob[1<<22];
        size_t o=0;
        for(size_t i=0;i<out.size();i++){
            ll t=out[i]; char tmp[24]; int tk=0;
            if(t==0) tmp[tk++]='0';
            while(t){ tmp[tk++]='0'+(int)(t%10); t/=10; }
            while(tk) ob[o++]=tmp[--tk];
            ob[o++]='\n';
            if(o+32>sizeof(ob)){ fwrite(ob,1,o,stdout); o=0; }
        }
        fwrite(ob,1,o,stdout);
    }
    return 0;
}

评测结果