Codeforces #216 Div2. E. Valera and Queries

ノーヒントで解けなかったのでEditorialを少し見た。
http://codeforces.com/contest/369/problem/E

問題

数直線上で整数L[i]～R[i]を両端とするセグメントがN個与えられる。

また、ここでM個のクエリが与えられる。
各クエリは、C個の整数値P[i]からなる。
各クエリについて、P[i]のうちいずれか1個以上を含むセグメント数を答えよ。

解法

1つのセグメントが複数のP[i]を含んでいたりするので、包除原理で解けるかもしれないがちょっと面倒。
ここでは、N個のセグメントのうちP[i]を1個も含まないものを除く、というアプローチで行く。
つまり、0～(P[0]-1)、(P[0]+1)～(P[1]-1)、(P[1]+1)～(P[2]-1)、…、(P[C-1]+1)～1000001に含まれるセグメントを除けばよい。

これにはBITを用いて対応できる。
数xを1～1000000まで増やしていき：

• 途中x==R[i]となるセグメントがあれば、SegTree上でL[i]の位置を1インクリメントする。
• 途中x==P[j]となるクエリがあれば、SegTree上で(P[j-1]+1)～(P[j]-1)に含まれるL[i]の数をカウントする。

xを1～1000000までたどるのをクエリごとに行うとTLEするので、全クエリ分まとめて行うとよい。

template<class V, int ME> class BIT {
public:
	V bit[ME];
	BIT(){clear();};
	void clear() {ZERO(bit);};

	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) {
			s+=bit[entry-1];
			entry -= entry & -entry;
		}
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= ME) {
			bit[entry-1] += val;
			entry += entry & -entry;
		}
	}
};

BIT<ll,1<<21> bt;

int N,M;
vector<int> R[1000011];
vector<int> Q[1000011];
vector<int> RQ[1000011];
int NU[1000011];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		R[y].push_back(x);
	}
	
	FOR(i,M) {
		NU[i]=N;
		cin>>x;
		Q[i].push_back(0);
		FOR(j,x) {
			cin>>y;
			Q[i].push_back(y);
			RQ[y].push_back(i);
		}
		reverse(Q[i].begin(),Q[i].end());
	}
	for(x=1;x<=1000000;x++) {
		FOR(i,RQ[x].size()) {
			y=RQ[x][i];
			NU[y] -= bt.total(x-1)-bt.total(Q[y].back());
			Q[y].resize(Q[y].size()-1);
		}
		FOR(i,R[x].size()) bt.update(R[x][i],1);
	}
	FOR(y,M) NU[y] -= bt.total(1000001)-bt.total(Q[y].back());
	FOR(i,M) _P("%d\n",NU[i]);
	
}

まとめ

P[i]を含まないセグメントを列挙すればよい、ってのに気づけば簡単だった。
逆にそこになかなか気づけないのが経験不足だな…。