题解 P3960 【列队】

观察发现每次变动有影响的点只有当前点，最后一行最后一列的点以及当前这一行的最后一个点。 所以可以用一个支持单点修改的线段树，建立n + 1棵，前n棵代表第n行前m - 1个答案，第n+1棵表示最后一列。 每次操作将当前点(x,y)记录输出并删除，然后加入第n+1的最后一个位置，然后把第n+1棵的x位置记录加入到第x行的最后一个位置， 注意如果x本身就在最后一列就不用管。 考虑q的范围，即最多有q个点加入，那么线段树的长度最长为 max(n,m) + q. 而n，m,q,的范围均在3e5的范围，所以需要动态开点，所以内存最多只有 3 \* log n \*q ，搞定 [蒟蒻noip题解传送门](http://tgotp.science/noip2017-%E9%A2%98%E8%A7%A3/) c++代码如下： ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #define rep(i,x,y) for(register int i = x;i <= y; ++ i) #define repd(i,x,y) for(register int i = x ;i >= y; -- i) #define abs(x) (x > 0 ? x : - (x)) using namespace std; typedef long long ll; template<class T>inline bool chkmax(T&x,T y) { return x < y ? x = y,1 : 0; } template<class T>inline bool chkmin(T&x,T y) { return x > y ? x = y,1 : 0; } template<typename T>inline void read(T&x) { x = 0;char c;int sign = 1; do { c = getchar();if(c == '-') sign = -1; }while(c < '0' || c > '9'); do { x = x * 10 + c - '0'; c = getchar(); }while(c <= '9' && c >= '0'); x *= sign; } inline void init(string name ) { string in = name + ".in",out = name + ".out"; freopen(in.c_str(),"r",stdin); freopen(out.c_str(),"w",stdout); } const int N = 3e5 + 500,M = 1e7; int n,m,now,o[N],q,root[N],SZ,sz[M],ls[M],rs[M];ll val[M]; inline int get_sz(int l,int r) { if(now == n + 1) { if(r <= n) return r - l + 1; if(l <= n) return n - l + 1; return 0; } if(r < m) return r - l + 1; if(l < m) return m - l ; return 0; } ll query(int&id,int x,int l,int r) { if(!id) { id = ++SZ; sz[id] = get_sz(l,r); if(l == r) { if(now <= n) val[id] = (ll)(now - 1) * m + l; else val[id] = (ll)l * m; } } sz[id]--; if(l == r) return val[id]; int mid = (l + r) >> 1; if((!ls[id] && x <= (mid - l + 1)) || x <= sz[ls[id]]) return query(ls[id],x,l,mid); else { if(!ls[id]) x -= (mid - l + 1); else x -= sz[ls[id]]; return query(rs[id],x,mid + 1,r); } } void update(int&id,int x,ll w,int l,int r) { if(!id) { id = ++SZ; sz[id] = get_sz(l,r); if(l == r) val[id] = w; } sz[id]++; if(l == r) return ; int mid = (l + r) >> 1; if(x <= mid) update(ls[id],x,w,l,mid); else update(rs[id],x,w,mid + 1,r); } int main() { init("phalanx"); int x,y; read(n); read(m); read(q); int p = max(m,n) + q ;ll z; rep(i,1,q) { read(x);read(y); if(y == m) now = n + 1,z = query(root[now],x,1,p); else now = x,z = query(root[now],y,1,p); printf("%lld\n",z); now = n + 1;update(root[n + 1],n + ( ++o[n+1] ),z,1,p); if(y != m) { now = n + 1;z = query(root[now],x,1,p); now = x;update(root[x],m - 1 + ( ++o[x] ),z,1,p); } } return 0; } ```