题解

题目类型：几何/映射建模 + 有序集合 + 隐式 Treap（可并堆式平衡树）+ 贪心（优先队列）

这题的实现非常“工程化”：先把平面上的点投影到矩形的“外层环”上，给每个点定义两条“射线”的出口（U[i] / D[i]），再在每个出口对应的有序序列中建立后继关系，把若干序列拼接成若干棵隐式 Treap。
通过在 Treap 上维护“从当前序列中第一个可见点起，连续可删除的段长”与其位置，借助大根堆贪心地每次取“当前全局最优的段”删除并动态维护，做 k 轮输出即可。整个流程靠一整套数据结构协作完成，时效与正确性均依赖这些结构的配合。

一、坐标映射与“出口”定义

设矩形高度为 n，对每个点 ((x,y)) 做如下两件事：

1. 横坐标规整
   代码中设 L = 2*(n-1)，将输入横坐标归一化到 [1..L] 周期：

   x = (x - 1) % L + 1;
   

2. 两条“镜面反射”射线的出口
   函数 jump(x,y,d)（d=0/1 表示向下/向上走“对角线”）模拟“在上下边界做镜面反射”的斜线运动，直到左边界 x==1 抵达外层环；返回值是该“落点”在外层环上的位置编号。

   • U[i] = jump(x, y, 1)：向“左上”方向走到环上的落点
   • D[i] = jump(x, y, 0)：向“右下”方向走到环上的落点

这样，每个点会被分配到两个“外层环位置”（U 与 D），下面要在这些位置下把点按 X 顺序排起来。

二、按出口分桶 + 在桶内按 X 建序列的“后继关系”

• P[t]：以环上位置 t 为 key 的有序集合，元素为同一出口下的所有点（按 X[i] 从小到大）。
  • 对每个点 i：若 y!=n，把 i 放入 P[U[i]]；若 y!=1，把其“行翻转对应”的编号 rev(i) 放入 P[D[i]]。
  • rev(i) 会把同一几何点在“上半/下半”的标号映射到另一份 m 偏移副本（详见代码 rev），方便区分“上/下半”的逻辑。
• 在同一 P[t] 内，每个点的后继就是 upper_bound((X[i],i)) 指向的点（如果存在）。
  于是所有点被若干条链串起来。多条链之间再通过不同 t 的交错关系“互相并”成若干棵树。

这一步用隐式 Treap实现：

• Treap 的键就是 X[i]（不存显式键，靠“拆/并”保持中序即 X 有序）；
• 通过 mrg（merge）把“i 的根”和“后继的根”合并；
• Treap 节点数组范围是 1..2m：前 m 对应原点，后 m 是 rev(i) 的那份镜像点。

三、每一行的“可见点”与多重计数

• 输入可能有同坐标的重复点。先用 mp/cnt 合并重复，cnt[i] 记录该点的重数；
• 每一行 y 用 Q[y] 这个 set 按 X 排序，**行内的“当前可见点”**定义为 Q[y].begin()->second；
• vis[p] 表示编号 p（注意包含 rev 后那一份）是否为其行的可见点；
• flg[p] 标识该节点属于“上半”或“下半”那一边（与 rev 配合使用，用来避免在同一格重复计数）。

要点：Treap 的状态只把“可见的那个点”视为“可被计入连续段”的候选，其它同一行的点要等前面的都被删干净后才会“露出来”。

四、Treap 维护的信息（psu）

对每个 Treap 结点 i 维护：

• siz[i]：子树大小（包含自身与子树节点的 cnt>0 的拷贝总数）；
• val[i] / pnt[i]：从当前子树的中序最左端开始，能连续“拿走”的合法点数与其起点编号。
  更新逻辑（伪解释）：
  • 若左子树 val 非 0，则
    val[i] = val[left] + siz[right] + 1，并把 pnt[i] = pnt[left]；
    这相当于“连续段横跨左子树 + 当前根（若可）+ 右子树的所有节点”，体现“从最左往右尽量拿”的思想；
  • 否则若当前结点 vis[i] && flg[i] 可计，则
    val[i] = siz[right] + 1，pnt[i] = i；
  • 否则若右子树 val 非 0，则 val[i] = val[right] 且 pnt[i] = pnt[right]；
  • 否则 val[i] = 0（这棵子树从最左起一个也拿不了）。

注意 siz 的参与：它把“从起点向右，直到子树末端”的整段长度一次性累进，正是我们要输出的“连续可删段长”。

每当某棵 Treap 的根发生变化（合并、旋转、split 后重组），就把（val[root], -Y[pnt[root]], pnt[root]）丢进大根堆 yzh，用于全局挑选最优段；-Y 仅用来同段长时优先行号大的（或代码作者需要的优先级）。

五、一次操作的整体流程

重头戏在 qry() + 删点的维护（tong-like 逻辑）：

1. 取全局最优段
   不断从 yzh 顶弹出，若与当前 Treap 根的 val/pnt 不一致（因为懒更新），就继续弹，直到拿到仍然有效的顶。

   • 若堆空或顶的 val==0，输出 1 0（代码里用 (0,1) 封装）并跳过；
   • 否则记 p = pnt，q = val，输出 Y[p] q，并把 res += q。

2. 删除“从 X[p] 开始的右侧整段”
   做一次 Treap split：把 X <= X[p]-1 的放左边 l，其余放右边 r；
   对 r 做一次中序 DFS 收集节点序列 V，再把 l 与 r 合回去（保证结构不散）。
   对 V 里的每一个几何点（注意要成对考虑 i 与 rev(i) 的两个编号）：

   • cnt[id(x)]--，若仍 >0，说明重复点尚未清空，跳过即可；
   • 否则真删除：
     • 在该行 Q[y] 中擦掉 (X[i],i)；若它正是行首（可见点），则把 vis 从旧首置 0，并把新行首置 1；
     • 依据 y 是内层还是边界（y!=1 && y!=n），我们需要把 i 与 rev(i) 这两个点从其所在的 Treap 中各自切出来（两次 split），再按“跨出口”的方式做一次交叉合并：

       // 内点：两个 Treap 之间“剪断并拼接”
       split(root(i), X[i]-1 -> xl, xr); split(xr, X[i] -> _, xr);
       split(root(rev(i)), X[rev(i)]-1 -> yl, yr); split(yr, X[rev(i)] -> _, yr);
       merge(xl, yr);  // 一半拼到另一半
       merge(yl, xr);  // 另一半也拼回来
       

       这相当于把“经过这个点的两条链”在删除点后正确接续；
     • 若在上/下边界（y==1 或 y==n），只需在当前 Treap 里把该点拆掉并合回。

   每次合并出新的 Treap 根后，调用 ins(root) 把新的根的 (val,pnt) 放回堆里。

3. 最后再将包含 p 的那棵根 ins(rt(p)) 入堆，准备下一轮。

以上流程循环 k 次；每次输出 Y[p] q，最后再输出 res。

六、关键数据结构回顾

• Q[y]（行首管理）：每行一个 set，始终保持“行内最左的存活点”为可见点；
• P[t]（出口桶）：每个环上位置一个 set，按 X 排列，找“后继”用于搭 Treap 边；
• 隐式 Treap：维护“按 X 的中序序列”；支持 merge/split，并在节点信息里维护 siz / val / pnt 以一眼得到“从最左起的连续可删段长度与起点”；
• 大根堆 yzh：全局选“当前每棵 Treap 的最优段”中最大的那个；配合“堆懒标记校验”（qry() 会弹无效顶）。

七、复杂度

• 每个点在一生中经历有限次 split/merge 与 set 的插删；
• 单次 split/merge 均摊 (O(\log m))，行首 Q 与出口 P 的操作均为 (O(\log m))；
• 每轮弹堆、删段、重接的总复杂度近似 (O((\text{删掉的点数})\log m))。
• 总体能通过题目给定的 n ≤ 4e4, m ≤ 4e5, k 的数据范围。

八、实现细节小坑

• 重复点：用 mp / cnt 先合并计数；只有 cnt 降为 0 才在结构里真删除；
• 两份编号：同一几何点有 i 与 rev(i) 两个编号，分别落在“上下半边”的 Treap 中，删除时要对两边都做剪接；
• vis 与行首切换：删除行首时要把下一候选置为行首，及时更新对应 Treap 根的可见性（upd）并把根入堆；
• 堆顶合法性：qry() 会不断校验 val[root] 与 pnt[root] 是否与堆顶匹配，避免“脏值”误用。

九、代码（与题给一致）

#include<bits/stdc++.h>
using namespace std;

#define pr pair<int,int>
#define fi first
#define se second

const int N = 4e4 + 5,M = 4e5 + 5;

int n,m,k,L,X[M],Y[M],U[M],D[M],res;
bool vis[M],flg[M];
int lc[M],rc[M],fa[M],siz[M],pri[M],cnt[M],val[M],pnt[M];
set<pr> P[N],Q[N];
map<pr,int> mp;
basic_string<int> V;
priority_queue<tuple<int,int,int>> yzh;

void psu(int i){
	siz[i] = 1;
	if(lc[i]) fa[lc[i]] = i,siz[i] += siz[lc[i]];
	if(rc[i]) fa[rc[i]] = i,siz[i] += siz[rc[i]];
	val[i] = 0;
	if(val[lc[i]]) val[i] = val[lc[i]] + siz[rc[i]] + 1,pnt[i] = pnt[lc[i]];
	else if(vis[i] && flg[i]) val[i] = siz[rc[i]] + 1,pnt[i] = i;
	else if(val[rc[i]]) val[i] = val[rc[i]],pnt[i] = pnt[rc[i]];
} 

int mrg(int x,int y){
    if(!x || !y) return x + y;
    if(pri[x] < pri[y]) return rc[x] = mrg(rc[x],y),psu(x),x;
    return lc[y] = mrg(x,lc[y]),psu(y),y;
}

void spl(int i,int k,int &x,int &y){
    if(!i) return void(x = y = 0);
    fa[i] = 0;
    if(X[i] <= k) x = i,spl(rc[i],k,rc[i],y);
    else y = i,spl(lc[i],k,x,lc[i]);
    psu(i);
}

int rt(int x){
	for(psu(x);fa[x];x = fa[x],psu(x));
	return x;
}

// <=n:U >n:D 

int jump(int x,int y,int d){ // 0:U 1:D
//	printf("jump %d %d %d\n",x,y,d);
    if(x == 1) return y + (y == 1 ? 0 : y == n ? 1 : !d) * (n - 2);
    if((y == 1 && d) || (y == n && !d)) return jump(x,y,!d);
    int t = d ? min(x,y) - 1 : min(x - 1,n - y);
    return jump(x - t,d ? y - t : y + t,d);
}

#define id(i) (i - (i > m) * m)

void dfs(int i){
	if(i) dfs(lc[i]),V += i,dfs(rc[i]);
}

int rev(int i){
	if(Y[i] == 1) return i <= m ? i : i - m;
	if(Y[i] == n) return i > m ? i : i + m;
	return i + (i <= m ? m : -m);
} 

void ins(int p){
	if(!fa[p] && val[p]) yzh.emplace(val[p],-Y[pnt[p]],pnt[p]);
}

void upd(int p,int x){
//	printf("upd %d %d\n",X[p],Y[p],x);
	vis[p] = x,ins(rt(p));
}

pr qry(){
	if(yzh.empty()) return pr(0,1);
	auto[x,_,p] = yzh.top(); yzh.pop();
//	printf("##### %d %d %d %d %d:\n",x,p,siz[rt(p)],val[rt(p)],cnt[id(p)]);
	int t = rt(p);
	return (vis[p] && flg[p] && val[t] == x && pnt[t] == p) ? pr(x,p) : qry();
}

int main(){
//    freopen("my.txt","w",stdout);
    scanf("%d%d%d",&n,&m,&k),L = 2 * (n - 1);
//    if(k==1)return puts("2 2\n2"),0;
    for(int i = 1,x,y;i <= m;++i){
        scanf("%d%d",&x,&y);
        if(mp[pr(x,y)]){ ++cnt[mp[pr(x,y)]]; continue; }
        cnt[mp[pr(x,y)] = i] = 1,X[i] = X[i + m] = x,Y[i] = Y[i + m] = y,x = (x - 1) % L + 1;
        Q[Y[i]].emplace(X[i],i);
		U[i] = jump(x,y,1),D[i] = jump(x,y,0);
        flg[i + (y > n / 2) * m] = 1;
        if(y != n) P[U[i]].emplace(X[i],i); else U[i] = 0;
        if(y != 1) P[D[i]].emplace(X[i],rev(i)); else D[i] = 0;
    }
    for(int i = 1;i <= 2 * m;++i) if(X[i])
    	siz[i] = 1,pri[i] = rand(),vis[i] = flg[i] && id(i) == Q[Y[i]].begin()->se,psu(i);
    for(int i = 1;i <= m;++i) if(X[i]){
        if(Y[i] != 1)
            if(auto I = P[D[i]].upper_bound(pr(X[i],rev(i)));I != end(P[D[i]]))
                mrg(rt(rev(i)),rt(rev(I->se)));
        if(Y[i] != n)
            if(auto I = P[U[i]].upper_bound(pr(X[i],i));I != end(P[U[i]]))
                mrg(rt(i),rt(rev(I->se)));
    }
    for(int i = 1;i <= 2 * m;++i) ins(i);
    for(int o = 1,l,r;o <= k;++o){
    	auto[q,p] = qry();
        printf("%d %d\n",q == 0 ? 1 : Y[p],q),res += q;
		if(!q) continue;
        V.clear(),spl(rt(p),X[p] - 1,l,r),dfs(r),mrg(l,r);
        for(int x,y,xl,xr,yl,yr,_;int x0 : V){
        	x = id(x0),y = rev(x);
        	if(--cnt[x] > 0) continue;
        	bool f = x == Q[Y[x]].begin()->se;
			Q[Y[x]].erase(pr(X[x],x));
        	if(f){
	        	upd(flg[x] ? x : x + m,0);
	        	if(Q[Y[x]].size()) _ = Q[Y[x]].begin()->se,assert(_!=x),upd(flg[_] ? _ : (_ + m),1);
			}
            if(Y[x] != 1 && Y[x] != n){
				spl(rt(x),X[x] - 1,xl,xr),spl(xr,X[x],_,xr);
				spl(rt(y),X[y] - 1,yl,yr),spl(yr,X[y],_,yr);
                ins(mrg(xl,yr)),ins(mrg(yl,xr));
            } else {
                spl(rt(x0),X[x0] - 1,xl,xr),spl(xr,X[x0],_,xr);
				ins(mrg(xl,xr)); 
            }
        }
        ins(rt(p));
    }
    printf("%d\n",res);
    return 0;
}