原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round6-I.html

题目传送门 – https://www.nowcoder.com/acm/contest/144/I

题意

　　给定 $n$ 条线段，第 $i$ 条线段覆盖区间 $[L_i,R_i]$ 。

　　接下来 $m$ 次操作，每次操作给出一个坐标 $x$ ，使得所有覆盖到坐标 $x$ 的区间都消失。（如果之前已经消失了，那么现在就不能让他再消失一次了）

　　对于每一次操作，输出这次操作使得多少线段消失了。

　　接下来对于每一个线段，输出它是在第几次操作消失的。如果它没有消失，那么输出 $0$ 。

　　强制在线。方式：对于每一次操作，输入的是一个数 $y$ ，$x = y\ {\rm XOR} \ lastans$ 。其中 $lastans$ 表示上一次操作时消失的线段的编号的乘积对于 $998244353$ 取模后的值；如果上一次没有使任何线段消失或者当前这次操作是第一次，则 $lastans=0$ 。

　　多组数据。共 $T$ 组。

　　$1\leq T\leq 5,1\leq n,m\leq 2\times 10^5,-10^9\leq L_i,R_i,x\leq 10^9 $

题解

　　线段树。

　　首先对于坐标离散化一下。然后，在线段树上面覆盖每一条线段，于是每一条线段会被拆成 $\log n$ 条，覆盖在线段树上。

　　具体地，在线段树上的操作就是对于每一个线段树节点开一个 vector , 然后把当前线段的编号扔进去。这个相当于线段树标记永久化。

　　我们还要支持快速查找覆盖一个点的所有线段。这个就相当于线段树单点查询。可以见得，在单点查询的时候，每遇到一个代表的区间包含当前位置的线段树节点，这个节点的 vector 的元素都会消失。但是一个线段被拆成了 log 个，当他消失的时候，我们似乎需要修改所有的 log 个。这样显然是不行的。解决的办法：我们只需要对于每一个线段，打一个标记，记录这条线段是否已经消失。于是，如果我们在单点查询的时候遇到了已经被标记删除的线段，那么我们就不将他加入当前的答案序列中。

　　再具体的看代码吧。

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

　　我比较懒，离散化的时候用了比较懒的办法。于是常数不大好。注意一下，在清空 vector 的时候从后往前访问并 pop_back 会快一下。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=200005,mod=998244353;
int read(){
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)&&ch!='-')
ch=getchar();
if (ch=='-')
f=-1,ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x*f;
}
int n,m;
int vis[N],L[N],R[N],ans[N];
int Ha[N*4],hs;
vector <int> t[N*4*4];
void build(int rt,int L,int R){
t[rt].clear();
if (L==R)
return;
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
build(ls,L,mid);
build(rs,mid+1,R);
}
void cover(int rt,int L,int R,int xL,int xR,int id){
if (xL>R||xR<L)
return;
if (xL<=L&&R<=xR){
t[rt].push_back(id);
return;
}
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
cover(ls,L,mid,xL,xR,id);
cover(rs,mid+1,R,xL,xR,id);
}
vector <int> res;
void Delete(int rt,int L,int R,int x){
while (!t[rt].empty()){
int id=t[rt].back();
t[rt].pop_back();
if (!vis[id])
vis[id]=1,res.push_back(id);
}
if (L==R)
return;
int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
if (x<=mid)
Delete(ls,L,mid,x);
else
Delete(rs,mid+1,R,x);
}
void solve(int Case){
n=read(),m=read();
hs=0;
for (int i=1;i<=n;i++){
L[i]=read(),R[i]=read();
Ha[++hs]=L[i],Ha[++hs]=L[i]-1;
Ha[++hs]=R[i],Ha[++hs]=R[i]-1;
}
Ha[++hs]=1e9+1;
sort(Ha+1,Ha+hs+1);
hs=unique(Ha+1,Ha+hs+1)-Ha-1;
build(1,1,hs);
for (int i=1;i<=n;i++){
vis[i]=ans[i]=0;
L[i]=lower_bound(Ha+1,Ha+hs+1,L[i])-Ha;
R[i]=lower_bound(Ha+1,Ha+hs+1,R[i])-Ha;
cover(1,1,hs,L[i],R[i],i);
}
printf("Case #%d:\n",Case);
int last_ans=0;
for (int k=1;k<=m;k++){
int x=read()^last_ans;
int p=lower_bound(Ha+1,Ha+hs+1,x)-Ha;
res.clear();
Delete(1,1,hs,p);
if (res.size()>0){
last_ans=1;
for (int i=0;i<res.size();i++){
int id=res[i];
ans[id]=k;
last_ans=1LL*last_ans*id%mod;
}
}
else
last_ans=0;
printf("%d\n",(int)res.size());
}
for (int i=1;i<n;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
int main(){
for (int T=read(),Case=1;T;T--,Case++)
solve(Case);
return 0;
}