题目大意：
给定$n(10^5)$个线段$[l_i,r_i](1leq l_i,r_ileq n)$，有$q(qleq10^5)$组询问，每次给出$m_i(sum m_ileq n)$个点$x_{i,j}(1leq x_{i,j}leq n)$，问这些线段中有多少个线段覆盖了这些点中的奇数个点。
思路：
$q$比较小时，只需要对于每个位置$i$，处理位置$1sim i$的点数前缀和。然后即可$O(1)$判断每个线段覆盖的点数的奇偶性。单笔询问时间复杂度$O(n+m)$。
由于$sum m_i$有限制，所以当$q$比较大时，$m_i$就不会很大。可以用主席树记录对于$1sim i$之间的左端点，每个区间内的右端点有多少。询问时对$x_{i,j}$排序，$O(m^2)$枚举线段覆盖了哪些点，用主席树求出符合条件的线段数即可。时间复杂度$O(m^2log n)$。
因此对于每次询问不同的$m_i$，令较大的$m_i$执行$O(n+m)$的算法，令较小的$m_i$执行$O(m^2log n)$的算法即可。
1 #include<cstdio> 2 #include<cctype> 3 #include<algorithm> 4 inline int getint() { 5 register char ch; 6 while(!isdigit(ch=getchar())); 7 register int x=ch^'0'; 8 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9 return x; 10 } 11 const int N=1e5+1,M=1e5+2,logN=18; 12 int p[M],cnt[N]; 13 std::pair<int,int> seg[N]; 14 class FotileTree { 15 private: 16 struct Node { 17 int sum,left,right,vis; 18 }; 19 Node node[N*logN]; 20 int sz,new_node(const int &p,const int &id) { 21 node[++sz]=node[p]; 22 node[sz].vis=id; 23 return sz; 24 } 25 public: 26 int root[N]; 27 void modify(int &p,const int &b,const int &e,const int &x,const int &id) { 28 if(node[p].vis!=id) p=new_node(p,id); 29 node[p].sum++; 30 if(b==e) return; 31 const int mid=(b+e)>>1; 32 if(x<=mid) modify(node[p].left,b,mid,x,id); 33 if(x>mid) modify(node[p].right,mid+1,e,x,id); 34 } 35 int query(const int &p,const int &q,const int &b,const int &e,const int &l,const int &r) const { 36 if(b==l&&e==r) return node[q].sum-node[p].sum; 37 const int mid=(b+e)>>1; 38 int ret=0; 39 if(l<=mid) ret+=query(node[p].left,node[q].left,b,mid,l,std::min(mid,r)); 40 if(r>mid) ret+=query(node[p].right,node[q].right,mid+1,e,std::max(mid+1,l),r); 41 return ret; 42 } 43 void reset() { 44 sz=0; 45 } 46 }; 47 FotileTree t; 48 int main() { 49 for(register int T=getint();T;T--) { 50 t.reset(); 51 const int n=getint(); 52 for(register int i=1;i<=n;i++) { 53 const int l=getint(),r=getint(); 54 seg[i]=std::make_pair(l,r); 55 } 56 std::sort(&seg[1],&seg[n]+1); 57 for(register int i=1,j=1;i<=n;i++) { 58 t.root[i]=t.root[i-1]; 59 for(;j<=n&&seg[j].first==i;j++) { 60 t.modify(t.root[i],1,n,seg[j].second,i); 61 } 62 } 63 for(register int i=getint();i;i--) { 64 const int m=getint(); 65 for(register int i=1;i<=m;i++) p[i]=getint(); 66 int ans=0; 67 if(m<=50) { 68 p[m+1]=n+1; 69 std::sort(&p[1],&p[m]+1); 70 for(register int i=1;i<=m;i++) { 71 if(p[i]==p[i-1]) continue; 72 for(register int j=i;j<=m;j+=2) { 73 if(p[j]==p[j+1]) continue; 74 ans+=t.query(t.root[p[i-1]],t.root[p[i]],1,n,p[j],p[j+1]-1); 75 } 76 } 77 } else { 78 for(register int i=1;i<=n;i++) cnt[i]=0; 79 for(register int i=1;i<=m;i++) cnt[p[i]]++; 80 for(register int i=1;i<=n;i++) cnt[i]+=cnt[i-1]; 81 for(register int i=1;i<=n;i++) { 82 ans+=(cnt[seg[i].second]-cnt[seg[i].first-1])&1; 83 } 84 } 85 printf("%d ",ans); 86 } 87 } 88 return 0; 89 }