题意

线段(segment)

【题目描述】

给定n条线段，第i条线段的左端点为\(l_i\)，右端点为\(r_i\)。第i条线段覆盖了点x当且仅当\(l_i ≤x ≤ r_i\)。

给定Q个询问，第i个询问给出了\(m_i\)个点。问有多少个线段覆盖了其中奇数个点。

【输入格式】

第一行一个正整数n，表示线段数量。

接下来n行，每行两个正整数\(l_i, r_i\)，描述一条线段。

接下来一行一个正整数Q，表示询问数量。

接下来Q行，每行描述一个询问。第一个正整数\(m_i\)表示询问的点数，接下来\(m_i\)个整数表示每个点的坐标。

【输出格式】

输出Q行，分别表示每个询问的答案。

【输入样例】

5

1 4

2 5

1 5

3 3

1 1

3

3 1 2 5

2 1 5

4 1 2 4 5

【输出样例】

2

3

3

【数据范围与约定】

对于 100%的数据，\(n, Q ≤ 10^5, 1 ≤ l_i ≤ r_i ≤ n, 1 ≤ x ≤ n, ∑m_i ≤ 10_i\)。

数据编号	n	Q	\(m_i\)
0-1	≤ 1000	≤ 1000	≤ 1000
2-3	\(≤ 10^5\)	≤ 200	\(≤ 10^5\)
4-6	\(≤ 10^5\)	\(≤ 10^5\)	≤ 50
7-9	\(≤ 10^5\)	\(≤ 10^5\)	\(≤ 10^5\)

考场20分

要覆盖奇数个点，想到xor和为1，所以想法维护xor值的和。考虑一个点\(p\)的贡献，发现把线段左右端点拆开后，把\(l_i\le p\)的线段xor 1，把\(p \le r_i\)的线段xor 1，那么最终将所有线段的异或值取反就是我们想要的结果。

用kdtree维护线段，期望复杂度\(O(\sum m_i \sqrt{n})\)。

然后我跑了2s，而时限是1s，所以只有20分。

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

    rg T data=0,w=1;rg char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}

    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();

    return data*w;

}

template<class T>il T read(rg T&x) {return x=read<T>();}

typedef long long ll;

using namespace std;

co int N=1e5+1;

int n,DIM,rt;

struct segment {int p[2];}sg[N];

il bool operator<(co segment&a,co segment&b) {return a.p[DIM]<b.p[DIM];}

struct node {int p[2],ch[2],mi[2],mx[2],siz,sum,val,tag,del;}tr[N];

#define lc tr[x].ch[0]

#define rc tr[x].ch[1]

il void up0(int x){

	for(int i=0;i<2;++i){

		tr[x].mi[i]=tr[x].mx[i]=tr[x].p[i];

		if(lc)

			tr[x].mi[i]=min(tr[x].mi[i],tr[lc].mi[i]),

			tr[x].mx[i]=max(tr[x].mx[i],tr[lc].mx[i]);

		if(rc)

			tr[x].mi[i]=min(tr[x].mi[i],tr[rc].mi[i]),

			tr[x].mx[i]=max(tr[x].mx[i],tr[rc].mx[i]);

	}

	tr[x].siz=tr[lc].siz+1+tr[rc].siz;

//	cerr<<x<<" mi0="<<tr[x].mi[0]<<" mx0="<<tr[x].mx[0]

//	<<" mi1="<<tr[x].mi[1]<<" mx1="<<tr[x].mx[1]<<endl;

}

int build(int l,int r,int dim){

	if(l>r) return 0;

	int x=l+r>>1;

	DIM=dim,nth_element(sg+l,sg+x,sg+r+1),copy(sg[x].p,sg[x].p+2,tr[x].p);

	lc=build(l,x-1,dim^1),rc=build(x+1,r,dim^1);

//	cerr<<x<<" p0="<<tr[x].p[0]<<" p1="<<tr[x].p[1]<<" lc="<<lc<<" rc="<<rc<<endl;

	return up0(x),x;

}

il void up(int x){

	tr[x].sum=tr[lc].sum+tr[x].val+tr[rc].sum;

//	cerr<<"x="<<x<<" lsum="<<tr[lc].sum<<" val="<<tr[x].val<<" rsum="<<tr[rc].sum<<endl;

}

il void down(int x){

	if(tr[x].del){

		if(lc)

			tr[lc].del=1,tr[lc].sum=tr[lc].val=tr[lc].tag=0;

		if(rc)

			tr[rc].del=1,tr[rc].sum=tr[rc].val=tr[rc].tag=0;

		tr[x].del=0;

	}

	if(tr[x].tag){

		if(lc)

			tr[lc].sum=tr[lc].siz-tr[lc].sum,tr[lc].val^=1,tr[lc].tag^=1;

		if(rc)

			tr[rc].sum=tr[rc].siz-tr[rc].sum,tr[rc].val^=1,tr[rc].tag^=1;

		tr[x].tag=0;

	}

}

void modify0(int x,int p){

	if(!x||tr[x].mi[0]>p) return;

//	cerr<<"x="<<x<<" p="<<p<<" mx0="<<tr[x].mx[0]<<endl;

	if(tr[x].mx[0]<=p)

		return tr[x].sum=tr[x].siz-tr[x].sum,tr[x].val^=1,tr[x].tag^=1,void();

	down(x);

	if(tr[x].p[0]<=p) tr[x].val^=1;

	modify0(lc,p),modify0(rc,p);

	return up(x);

}

void modify1(int x,int p){

	if(!x||tr[x].mx[1]<p) return;

	if(tr[x].mi[1]>=p)

		return tr[x].sum=tr[x].siz-tr[x].sum,tr[x].val^=1,tr[x].tag^=1,void();

	down(x);

	if(tr[x].p[1]>=p) tr[x].val^=1;

	modify1(lc,p),modify1(rc,p);

	return up(x);

}

int p[N];

int main(){

	freopen("segment.in","r",stdin),freopen("segment.out","w",stdout);

	read(n);

	for(int i=1;i<=n;++i) read(sg[i].p[0]),read(sg[i].p[1]);

	rt=build(1,n,0);

//	cerr<<"rt="<<rt<<endl;

	for(int Q=read<int>(),m;Q--;){

		read(m);

		for(int i=1;i<=m;++i)

			read(p[i]),modify0(rt,p[i]),modify1(rt,p[i]);

		printf("%d\n",m&1?tr[rt].siz-tr[rt].sum:tr[rt].sum);

		tr[rt].del=1,tr[rt].sum=tr[rt].val=tr[rt].tag=0;

	}

	return 0;

}

标解

树套树不能支持区间修改，这就是我打kdtree的原因。事实证明不能很好的维护。

那怎么办？按询问的点的个数分类暴力即可。

设一个块大小B，然后分两类：

对于点个数大于B的询问，我们用扫描的方式做。将所有点基数排序，做个横坐标的个数前缀和，然后扫描一遍所有的线段统计有多少段覆盖了奇数个点。复杂度\(O(m_i+n)\)
对于点个数小于B的询问，将点排序，因为要求覆盖了奇数个，所以枚举覆盖了哪奇数个，然后用主席树统计有多少线段刚好覆盖了这奇数个点。时间复杂度\(O(m_i^2\log n)\)。

然后块大小怎么分？造几组随机数据试一下就行了。\(B=0.8\sqrt{\frac n{\log n}}\)

#include <bits/stdc++.h>

using namespace std;

void gi(int &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}

void pi(int x) {if (x > 9) pi(x / 10); putchar(x % 10 + 48);}

//begin persistent segment tree

const int sz = 5000000;

int a[sz], l[sz], r[sz], N, tn;

int add(int x, int p, int s = tn) {

  int u = ++N; a[u] = a[x] + 1; l[u] = l[x]; r[u] = r[x];

  if (s == 1) return u;

  else if (p < (s >> 1)) l[u] = add(l[x], p, s >> 1);

  else r[u] = add(r[x], p - (s >> 1), s >> 1);

  return u;

}

int sum(int x, int p, int s = tn) {

  if (s == 1) return a[x];

  else if (p < (s >> 1)) return sum(l[x], p, s >> 1);

  else return a[l[x]] + sum(r[x], p - (s >> 1), s >> 1);

}

//end persistent segment tree

int n, q, cnt, x[233333], s[233333], root[233333];//x is query; s is used in brute force; root is the roots of persistent segment tree

pair <int, int> itv[233333];//intervals

#define L first

#define R second

int B;

//actually query (l1+1, r1, l2+1, r2)

int query(int l1, int r1, int l2, int r2) {

  return sum(root[r1], r2) + sum(root[l1], l2) - sum(root[l1], r2) - sum(root[r1], l2);

}

void doit() {

  int i, j, ans;

  N = 0; gi(n); for (tn = 1; tn <= n; tn <<= 1);

  for (i = 1; i <= n; i++) gi(itv[i].L), gi(itv[i].R);

  sort(itv + 1, itv + n + 1);

  for (i = j = 1; i <= n; i++) {

    root[i] = root[i - 1];

    for (; j <= n && itv[j].L <= i; j++)

      root[i] = add(root[i], itv[j].R);

  }

  B = int(sqrt(n / log(n)) * 0.8);

  gi(q);

  while (q--) {

    gi(cnt); ans = 0;

    for (i = 1; i <= cnt; i++) gi(x[i]);

    if (cnt <= B) {

      sort(x + 1, x + cnt + 1); x[cnt + 1] = n + 1;

      for (i = 1; i <= cnt; i++)

	for (j = i; j <= cnt; j += 2)

	  ans += query[i - 1], x[i], x[j] - 1, x[j + 1] - 1);

    } else {

      for (i = 1; i <= n; i++) s[i] = 0;

      for (i = 1; i <= cnt; i++) s[x[i]]++;

      for (i = 1; i <= n; i++) s[i] += s[i - 1];

      for (i = 1; i <= n; i++) ans += (1 & (s[itv[i].R] ^ s[itv[i].L - 1]));

    }

    pi(ans); putchar('\n');

  }

}

int main() {freopen("segment.in","r",stdin);freopen("segment.out","w",stdout); doit(); return 0;}

巴特西

test20190409 线段

题意